Scheduling flexible flow shops with sequence-dependent setup effects

This paper presents a Lagrangian relaxation-based approach for production scheduling of flexible flow shops (PSFFS) where sequence-dependent setup effects are significant. PSPFS is first formulated as a separable integer programming problem with synchronization constraints between production and machine usage. Lagrangian relaxation is then applied, and the scheduling is decomposed into part production and machine scheduling. In these subproblems, there are network flow structures in the equality constraints describing machine status change and production flow balance. Our iterative algorithm applies a minimum cost network flow algorithm to individual subproblems and adopts an efficient surrogate subgradient method to optimize Lagrangian multipliers. A machine availability-searching heuristic finally adjusts the solution to satisfy all synchronization constraints by exploiting the network structure, economic interpretation of Lagrangian multipliers, and the slack time policy. Numerical results of 16 cases, each having 20 test problems, demonstrate that differences between the schedules obtained by our approach and the true optima are on average within 15%, CPU times spent are all less than 17 min on a Pentium-II personal computer. Among the problem dimension factors, the number of part types has the most significant effect on both optimality and computation efficiency. Application of the methodology to daily scheduling of a realistic integrated circuit testing facility of 30 machines takes about 6 min of CPU time to generate a near-optimal solution