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