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

作　　者：Kejia Chen Debiao Li Xiao Wang 

机构地区：[1]School of Economics and Management,Fuzhou University,Fuzhou 350116,China

出　　处：《Journal of Systems Science and Systems Engineering》2020年第4期400-411,共12页系统科学与系统工程学报（英文版）

基　　金：supported in part by the National Natural Sci-ence Foundation of China(NSFC)under Grant No.71801051.

摘　　要：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.

关 键 词：Two-machine flow-shop NO-WAIT unavailable interval Gilmore and Gomory Algorithm 

分 类 号：O22[理学—运筹学与控制论]