文献类型：期刊文献

中文题名：关于工件组的两机自由作业时间表问题

英文题名：Scheduling Groups of Jobs in Two-machine Open Shop

作者：刘朝晖[1];俞文鮆[1]

机构：[1]华东理工大学数学系,上海200237

年份：2000

卷号：26

期号：6

起止页码：665

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

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

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

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

语种：中文

中文关键词：时间表;工件组;自由作业;加工全长;算法;NP困难

外文关键词：scheduling; job group; open shop; makespan; algorithm

摘要：讨论关于工件组的两机自由作业时间表的加工全长问题。无论是对于成组加工情形还是分组情形 ,该问题都可以被证明是 NP困难的。对于成组加工的情形 ,设计了一个性能比为 5/4的近似算法 ,该算法生成的时间表作为分组情形的解 ,性能比仍能保持为 5/4。此外 ,还讨论了如何最优地求解只有一个工件组的情形。
This paper is concerned with the makespan problem of scheduling groups of jobs in two machine open shop. The problem is known as NP hard no matter whether group sub lotting is admissible or not. We obtain an approximation algorithm which generates a GT schedule (in which no group is split) with the worst case performance ratio 5/4, even when the GT schedule is used as a solution to the group sub lotting case. Besides, we give a polynomial algorithm to solve the one group case to optimality.