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

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

作　　者：陈秀宏[1] 俞文鮆[1] 

机构地区：[1]华东理工大学应用数学研究所,上海200237

出　　处：《华东理工大学学报（自然科学版）》2000年第6期670-673,677,共5页Journal of East China University of Science and Technology

基　　金：国家自然科学基金!资助项目 (197310 0 1)

摘　　要：对于自由作业问题 ,如果从初始时刻开始 ,逐步在每个机器安排任一可以加工的工件 ,避免不必要的空闲 ,所得的安排称为稠密时间表。其加工总长与最优值之比具有上界 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.

关 键 词：自由作业 加工总长 稠密时间表 性能比 最优值 

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