A Parallel Machine Scheduling Problem That Takes Periodical Maintenance Period Into Account

The problem of machine scheduling is a typical combinatorial optimization problem and has received extensive attention.In the actual production activities,there are often cases where the machine is not available due to unexpected breakdowns or maintenance activities.Therefore,it is very important to study the scheduling problem that considers the machine unavailability time period.In this context,this paper studies the parallel machine scheduling problem with machine maintenance period,and studies and analyzes the two cases of fixed machine maintenance duration and unfixed machine maintenance duration respectively.For the case that the machine has a fixed maintenance duration,this paper studies the issue of minimizing makespan.Based on the improvement of the classic LPT(Longest Processing Time First)and FFD(First Fit Decreasing)rules,an MFFD-LPT algorithm is proposed.The theory proves that the worst error bound of this algorithm is 9v/5u.At the same time,the correction algorithm DA of MFFD-LPT algorithm is proposed.Large-scale random data experiments have proved that the correction rate of the DA algorithm for the solution obtained by MFFD-LPT algorithm is between 20% and 30%,which shows a very good correction effect.Then,considering a more general situation,this paper studies parallel machine scheduling problems with unfixed maintenance duration.The goal of scheduling is also to minimizing makespan.Based on the study of the fixed maintenance duration of the machine,the MFFD-LPT' algorithm is proposed.Through mathematical analysis,the worst error bound of the MFFD-LPT' algorithm is proved to be 9r/5l,then the initial scheduling scheme is modified by the simulated annealing algorithm.Finally,large-scale computer simulation experiments are conducted to verify the effectiveness of the algorithm.