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

摘要

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 solv-ing 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.