科研之友
微信
新浪微博
Facebook
分享链接
摘要
We consider a semi-online multiprocessor scheduling problem with a given a set of identical machines and a sequence of jobs, the sum of whose processing times is known in advance. The jobs are to be assigned online to one of the machines and the objective is to minimize the makespan. The best known algorithm for this problem achieves a competitive ratio 1.6 (Cheng et al. in Theor Comput Sci 337:134-146, 2005). The best known lower bound is approximately 1.585 (Albers and Hellwig in Theor Comput Sci 443:1-9, 2012) if the number of machines tends to infinity. We present an elementary algorithm with competitive ratio equal to this lower bound. Thus, the algorithm is best possible if the number of machines tends to infinity.
- 出版日期2015-12
