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

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

作　　者：陈荣军[1] 黄婉珍 唐国春[3] 

机构地区：[1]常州工学院数学系,常州213002 [2]加拿大湖首大学数学系科学系,加拿大P785E1 [3]上海第二工业大学管理工程研究所,上海201209

出　　处：《运筹学学报》2010年第2期1-10,共10页Operations Research Transactions

基　　金：supported by the National Natural Science Foundation of China(20710015);the Natural Sciences and Engineering Research Council of Canada

摘　　要：对于自由作业问题,在安排工件时避免不必要空闲所得的时间表称为稠密时间表.稠密时间表的加工总长不超过最优值的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.

关 键 词：运筹学 排序论 自由作业 稠密时间表 性能比 加工总长 

分 类 号：O224[理学—运筹学与控制论]