Single-Machine Scheduling with Fixed or Flexible Maintenance

Abstract This paper studies the integrated optimization of production planning and preventative maintenance scheduling on a single machine. Preventative maintenance can be conducted following either fixed or flexible maintenance schemes. The time interval between two consecutive maintenance activities in the fixed maintenance scheme is constant while maintenances can be implemented earlier in the flexible scheme. Both makespan and total flow time are considered as performance metrics during scheduling. Six models based on the bin packing problem are presented for the two schemes and two objectives. The first four models are formulated without allowing to change the job-to-bin assignment for a shorter total flow time. The last two models are formulated to improve the total flow time by allowing repacking jobs in bins from the bin packing problem. Heuristic or exact-solution approaches are developed for addressing the computational challenge. Numerical experiments are conducted to illustrate the effectiveness of the developed algorithms and demonstrate the advantage of flexible maintenance.