In this paper we study the time complexities of some two‐ and three‐stage no‐wait flowshop makespan scheduling problems where, in some stage, all the jobs require a constant processing time and the stage may consist of parallel identical machines. Polynomial time algorithms are presented for certain problems, while several others are proved to be strongly NP‐complete.
DuD.LamK., and WenJ. (1997a), Analysis of Heuristics for Scheduling Two‐stage Flow‐shop with No Wait, Technical Report, Institute of Applied Mathematics, Academia Sinica, Beijing, China.
2.
DuD.LamK., and WenJ. (1997b), No Wait Scheduling for 2‐stage Flow‐shop Scheduling with One Processor on the Second Stage and Two Identical Processors on the Second: a Heuristic, Technical Report, Institute of Applied Mathematics, Academia Sinica, Beijing, China.
3.
GareyM. R. and JohnsonD. S. (1979), Computers and Intractability: A Guide to the Theory of NP‐completeness, W. H. Freeman and Co., San Francisco.
4.
GilmoreP. C. and GomoryR. E. (1964), “Sequencing a One‐state Variable Machine: A Solvable Case of the Traveling Salesman Problem,Operations Research, 12, 655–679.
5.
GrahamR. L.LawlerE. L.LenstraJ. K., and Rinnooy KanA. H. G. (1979), “Optimization and Approximation in Deterministic Sequencing and Scheduling: A Survey,Annals of Discrete Mathematics, 5, 287–326.
6.
HallN. G.KamounH., and SriskandarajahC. (1997), “Scheduling in Robotic Cells: Classification, Two and Three Machine Cells,Operations Research, 45, 421–439.
7.
HallN. G.KamounH., and SriskandarajahC. (1998), “Scheduling in Robotic Cells: Complexity and Steady State Analysis,European Journal of Operational Research, 109, 43–65.
8.
HallN. G. and SriskandarajahC. (1996), “A Survey of Machine Scheduling Problems with Blocking and No‐wait in Process,Operations Research, 44, 510–524.
9.
HsuE. and SteinM. (1991), Anodizing Load Scheduling for Diamond Aluminum, Undergraduate Thesis, Department of Industrial Engineering, University of Toronto, Canada.
10.
KiseH.ShioyamaT., and IbarakiT. (1991), “Automated Two‐machine Flowshop Scheduling: A Solvable Case,IIE Transactions, 23, 10–16.
11.
RamudhinA. and RatliffH. D. (1991), Scheduling in Process Industry, Working Paper, Université du Québec à Trois‐Rivières, Québec, Canada.
12.
RockH. (1984), “The Three‐machine No‐wait Flowshop Problem is NP‐complete,” Journal of the Association of Computing Machinery, 33, 336–345.
13.
SalvadorM. S. (1973), “A Solution of a Special Class of Flowshop Scheduling Problems,” Proceedings of the Symposium on the Theory of Scheduling and Its Applications, Springer‐Verlag, Berlin, 83–91.
14.
SethiS. P.SriskandarajahC.SorgerG.BlazewiczJ., and KubiakW. (1992), “Sequencing of Parts and Robot Moves in a Robotic Cell,International Journal of Flexible Manufacturing Systems, 4, 331–358.
15.
SriskandarajahC.HallN. G., and KamounH. (1996), Scheduling Large Robotic Cells, Working Paper, Department of Industrial Engineering, University of Toronto, Canada.
16.
SriskandarajahC.HallN. G. and LadetP. (1986), “Some No‐wait Shops Scheduling Problems: Complexity Aspect,European Journal of Operational Research, 24, 424–438.
