最后完工机器至多两个空闲的自由作业稠密时间表(英文)

Dense Schedule for Open Shop Problems with Two Idle Intervals at Most on the Last Complete Machine

对于自由作业问题,在安排工件时避免不必要空闲所得的时间表称为稠密时间表.稠密时间表的加工总长不超过最优值的2-1/m倍,是一个在机器数m>6时尚未被证明的猜想.本文通过引入工件与机器特征函数及机器关于工件非间断等概念,研究当最后完工机器至多有两个空闲区间时,性能比猜想成立的充分条件.

For open shop problem, if the principle of avoiding unnecessary machine idleness is applied when arranging jobs, 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 of the problem, where m is the number of machines. The conjecture remains unproved when the number of machine is greater than six. In this paper, by introducing characteristic functions of jobs and machines and non-interruption of machines about jobs, we propose sufficient conditions under which the conjecture is true for general number of machines, provided that the last complete machine in the dense schedule has no more than two idle intervals.