본문 바로가기
HOME> 논문 > 논문 검색상세

논문 상세정보

작업이 일반적인 자격을 갖는 상황에서 3대의 기계와 4대의 기계의 온라인 스케줄링 문제에 대한 소고
A Note on Online Scheduling Problem of Three and Four Machines Under General Eligibility

박종호    (포항공과대학교 산업경영공학부   ); 장수영    (포항공과대학교 산업경영공학부   ); 임경국    (포항공과대학교 산업경영공학부  );
  • 초록

    We consider the online scheduling problems of three and four machines under eligibility constraint. Respectively for the cases of three and four machines, we prove that AW algorithm has competitive ratios of $\frac{5}{2}$ and 3 which are shown to be optimal. Also, we show that the same results hold for the semi-online cases with prior knowledge of the total and the largest processing time.


  • 주제어

    Online .   General Eligibility .   Three Machines .   Four Machines.  

  • 참고문헌 (9)

    1. Graham, R. L. (1966), Bounds for certain multiprocessor anomalies, Bell System Technical Journal, 45, 1563-1581 
    2. He, Y. and Zhang, G. C. (1999), Semi online scheduling on two identical machines, Computing, 62, 179-187 
    3. Kellerer, H. Kotov, V. Speranza, M. G., and Tuza, Z. (1997), Semi-online algorithms for the partitioning problem, Operations Research Letters, 21, 235-242 
    4. Sleator, D. and Tarjan, R. E. (1985), Amorized efficiency of list update and paging rules, Communications of the ACM, 28, 202-208 
    5. Tan, Z. and He, Y. (2002), Semi-online problems on two identical machines with combined partial information, Operations Research Letters, 30, 408-414 
    6. Angelelli, E., Speranza, M. G., and Tuza, Zs. (2007), Semi on-line scheduling on three processors with known sum of the tasks, Journal of Scheduling, 10, 263-269 
    7. Hwang, H. C. Chang, S. Y., and Hong, Y. (2004), A Posterior Competitiveness for List Scheduling Algorithm on Machines with Eligibility Constraints, Asia-Pacific Journal of Operational Research, 21, 117-125 
    8. Park, J. Chang, S. and Lee K. (2006), Online and semi-online scheduling of two machines under a grade of service provision, Operations Research Letters, 34, 692-696 
    9. Azar, Y. Naor, J. and Rom, R. (1995), The competitiveness of online assignments, Journal of Algorithms, 18, 221-237 

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

무료다운로드
  • NDSL :
유료다운로드

유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.

원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.

NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.

이 논문과 함께 출판된 논문 + 더보기