【摘要】 研究了已知工件最大加工时间,目标为极小化最大机器负载的半在线平行机排序问题.证明了对于一般的m(>6)台机器,任意的半在线算法的竞争比至少是(33+3)/6.同时还设计了一个半在线算法,算法的竞争比为2-1/(m-1).更多还原

【Abstract】 A semi-online multiprocessor scheduling problem with the longest given processing time is studied,and the objective is to minimize the makespan,i.e.the maximum completion time on the processors.It is shown that the lower bound of the problem is at least(33+3)/6 when the number of machine is greater than 6,and a semi-online algorithm is presented which has a competitive ratio at most 2-1/(m-1) for any number of processors.更多还原