欢迎您！东篱公司
退出
-
申报数据库
-
立项数据库
-
成果数据库
-
项目获奖数据库
中文摘要：
本文研究一类具有特殊工件的平行机在线排序问题，目标是最小化最大完工时间．此模型有两种工件：正常工件和特殊工件．正常工件能够在m台平行机的任何一台机器上加工，而特殊工件仅能够在它唯一被指定的机器上加工．文中所有特殊工件的指定机器为M1．我们提供了竞争比为（2m^2-2m＋1）／（m^2-m＋1）的在线近似算法．当m=2时，算法是最好可能的．当m=3时，算法的竞争比为13／7≈1．857，并且提供了竞争比的下界（1＋√33）／4≈1．686．
英文摘要：
In the parallel machine on-line scheduling with special jobs to minimize the makespan, we have two kinds of jobs, normal jobs and special jobs. The normal jobs can be processed on any one of the m identical parallel machines, while the special jobs can only be processed on specified machines, and each of the special jobs has its own unique specified machine. In this paper, all the special jobs are specified to be processed on machine M1. We provide a linear on-line algorithm with competitive ratio of （2m^2 - 2m ＋1 ）/（m^2 - m ＋ 1）. When m= 2, the algorithm is the best possible and has a competitive ratio of 5/3. When m = 3, the competitive ratio of the algorithm is 13/7 ≈ 1.857, and we also show that the considered problem has no on-line algorithm with competitive ratio less than （1 ＋ √3-3）/4 ≈ 1.686.
同期刊论文项目
同项目期刊论文
期刊信息
位置：