THE MIXED SHOP SCHEDULING PROBLEM

被引：29

作者：

MASUDA, T ^{[1
]}

ISHII, H ^{[1
]}

NISHIDA, T ^{[1
]}

机构：

[1] OSAKA UNIV,FAC ENGN,DEPT APPL PHYS,OSAKA,JAPAN

来源：

DISCRETE APPLIED MATHEMATICS | 1985年 / 11卷 / 02期

关键词：

SCHEDULING;

D O I：

10.1016/S0166-218X(85)80007-X

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

The authors consider a two-machine shop scheduling problem consisting of two disjoint job subsets F and O. F is a set of the flow shop type jobs, while O is a set of the open shop type jobs. Our objective is to find the schedule minimizing the maximimum completion time. For the case that O is empty, this problem reduces to a two-machine flow shop scheduling problem for which S. M. Johnson developed an optimal algorithm. Also for the case that F is empty, the problem reduces to a two-machine open shop scheduling problem for which there is an optimal algorithm developed by T. Gonzalez and S. Sahni. While for the case that both F and O are not empty, the situation is complicated in the sense that the preceding two cases are not extensible to the present case. The optimal algorithm for the authors' nontrivial case is given.

引用

页码：175 / 186

页数：12