文献类型：期刊文献

中文题名：自由作业稠密时间表的性能比上界

英文题名：Upper-bound of Performance Ratio of Dense Schedules for Open-shop

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

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

年份：2000

卷号：26

期号：6

起止页码：670

中文期刊名：华东理工大学学报（自然科学版）

外文期刊名：Journal of East China University of Science and Technology

收录：CSTPCD;;国家哲学社会科学学术期刊数据库;Scopus;北大核心:【北大核心1996】；CSCD:【CSCD2011_2012】；

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

语种：中文

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

外文关键词：open shop; makespan; dense schedule; performance ratio

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