自由作业稠密时间表的性能比上界

Upper-bound of Performance Ratio of Dense Schedules for Open-shop

对于自由作业问题 ,如果从初始时刻开始 ,逐步在每个机器安排任一可以加工的工件 ,避免不必要的空闲 ,所得的安排称为稠密时间表。其加工总长与最优值之比具有上界 2 - 1 /m(m为机器数 ) ,是一个尚未证明的猜想。本文引入了最后工件组及相关机器集的概念 ,证明了 m=5时该猜想是成立的。

For an open shop problem, if the principle of avoiding unnecessary idleness is applied to arrange available jobs for the schedule construction, a dense schedule is obtained. It is conjectured that the makespan of any dense schedule is at most 2-1/ m times the optimal makespan, where m is the number of machines. In this paper, we introduce the concepts of last job group and the related machines, and prove that the conjecture holds for m =5.