Makespan Minimization in Two-Machine Flow-Shop Scheduling under No-wait and Deterministic Unavailable Interval Constraints

Abstract

This paper systematically studies the two-machine flow-shop scheduling problems with no-wait and deterministic unavailable interval constraints. To minimize the makespan, three integer programming mathematical models are formulated for two-machine flow-shop with no-wait constraint, two-machine flow-shop with resumable unavailable interval constraint, and two-machine flow-shop with no-wait and non-resumable unavailable interval constraints problems, respectively. The optimal conditions of solving the two-machine flow-shop with no-wait constraint problem by the permutation schedules, the two-machine flow-shop with resumable unavailable interval constraint problem by the Johnson algorithm, and two-machine flow-shop with no-wait and non-resumable unavailable interval constraints problem by the Gilmore and Gomory Algorithm (GGA) are presented, respectively. And the tight worst-case performance bounds of Johnson and GGA algorithms for these problems are also proved to be 2. Several instances are generated to demonstrate the proposed theorems. Based on the experimental results, GGA obtains the optimal solution for the two-machine flow-shop with no-wait constraint problem. Although it cannot reach the optimal solution for the two-machine flow-shop with resumable unavailable interval constraint problem, the optimal gap is 0.18% on average when the number of jobs is 100. Moreover, under some special conditions, it yields the optimal solution for the two-machine flow-shop with no-wait and non-resumable unavailable interval constraints problem. Therefore, GGA is an efficient heuristic to solve these problems.

Keywords

Two-machine flow-shop / no-wait / unavailable interval / Gilmore and Gomory Algorithm

References

[1] Allaoui H, Artiba A, Elmaghraby S E, Riane F. Scheduling of a two-machine flowshop with availability constraints on the first machine. International Journal of Production Economics, 2006, 99(1–2): 16-27.

[2] Allaoui H, Artiba A H. Johnson’s algorithm: A key to solve optimally or approximately flow shop scheduling problems with unavailability periods. International Journal of Production Economics, 2009, 121(1): 81-87.

[3] Allaoui H, Lamouri S, Artiba A, Aghezzaf E. Simultaneously scheduling n jobs and the preventive maintenance on the two-machine flow shop to minimize the makespan. International Journal of Production Economics, 2008, 112(1): 161-167.

[4] Breit J. An improved approximation algorithm for two-machine flow shop scheduling with an availability constraint. Information Processing Letters, 2004, 90(6): 273-278.

[5] Cheng T C E, Wang G. Improved heuristic for two-machine flowshop scheduling with an availability constraint. Operations Research Letters, 2000, 26(5): 223-229.

[6] Chihaoui F, Kacem I, Hadj-Alouane A, Dridi N, Rezg N. No-wait scheduling of a two-machine flow-shop to minimize the makespan under non-availability constraints and different release dates. International Journal of Production Research, 2011, 49(21): 6273-6286.

[7] Cui W, Lu Z, Zhou B, Li C, Han X (2018). A hybrid genetic algorithm for non-permutation flow shop scheduling problems with unavailability constraints. International Journal of Computer Integrated Manufacturing: 273–278.

[8] Gao F, Liu M, Wang J, Lu Y. No-wait two-machine permutation flow shop scheduling problem with learning effect, common due date and controllable job processing times. International Journal of Production Research, 2018, 56(6): 2361-2369.

[9] Gilmore P C, Gomory R E. Sequencing a one-state variable machine: A solvable case of the traveling salesman problem. Operations Research, 1964, 12: 655-679.

[10] Grabowski J, Pempera J. Some local search algorithms for no-wait flow-shop problem with makespan criterion. Computers & Operations Research, 2005, 32(8): 2197-2212.

[11] Hadda H. A polynomial-time approximation scheme for the two machine flow shop problem with several availability constraints. Optimization Letters, 2012, 6(3): 559-569.

[12] Hadda H, Dridi N, Hajri-Gabouj S. An improved heuristic for two-machine flow shop scheduling with an availability constraint and nonresumable jobs. 4OR, 2010, 8(1): 87-99.

[13] Joo B J, Kim Y D. A branch-and-bound algorithm for a two-machine flowshop scheduling problem with limited waiting time constraints. Journal of the Operational Research Society, 2009, 60(4): 572-582.

[14] Kubzin Mikhail A, Strusevich Vitaly A. Two-machine flow shop no-wait scheduling with a nonavailability interval. Naval Research Logistics, 2004, 51(4): 613-631.

[15] Lee C Y. Minimizing the makespan in the two-machine flowshop scheduling problem with an availability constraint. Operations Research Letters, 1997, 20(3): 129-139.

[16] Lee C Y. Two-machine flowshop scheduling with availability constraints. European Journal of Operational Research, 1997, 114(2): 420-429.

[17] Li D, Chen K, Wang X. Properties of two-machine no-wait flow-shop scheduling with a nonresumable unavailable interval. Journal of Industrial and Production Engineering, 2017, 34(3): 232-238.

[18] Su Ling H. A hybrid two-stage flowshop with limited waiting time constraints. Computers & Industrial Engineering, 2003, 44(3): 409-424.

[19] Su Ling H, Lee Yuan Y. The two-machine flow-shop no-wait scheduling problem with a single server to minimize the total completion time. Computers & Operations Research, 2008, 35(9): 2952-2963.

[20] Wang X, Cheng T C E. An approximation scheme for two-machine flowshop scheduling with setup times and an availability constraint. Computers & Operations Research, 2007, 34(10): 2894-2901.

[21] Yang Dar L, Hsub Chou J, Kuo Wen H. A two-machine flowshop scheduling problem with a separated maintenance constraint. Computers & Operations Research, 2008, 35(3): 876-883.

[22] Zhao C, Tang H. A note on two-machine no-wait flow shop scheduling with deteriorating jobs and machine availability constraints. Optimization Letters, 2011, 5(1): 183-190.