Two models for a family of flowshop sequencing problems

This paper presents two mixed-integer linear programming (MILP) models (referred to as WST and SGST in the paper) for a family of four different M-machine, N-job flowshop sequencing problems. Each model may be used to solve the regular, no intermediate queues (NIQ), sequence-dependent setup times (SDST), and SDST/NIQ flowshop problems. The optimal job sequence, based on minimizing makespan, is achieved by a positional assignment approach in the WST model, and by pairs of disjunctive (either or) constraints in the SGST model. A 12-cell experimental design was used to compare the solution times of the two models for each of the four flowshop problems. The WST model used significantly less computer time than the SGST model for all problem sizes in the regular, NIQ, and SDST flowshop problems. Both models were competitive in the SDST/NIQ flowshop for N less than or equal to 7. but the WST model proved significantly better for N greater than or equal to 8. (C) 2002 Elsevier Science B.V. All rights reserved.