Optimization models for the machine scheduling problem with a single flexible maintenance activity

Abstract

The majority of machine scheduling literature assumes that machines are available at all times. However, this assumption is inappropriate in certain real world situations. This study addresses the single machine and parallel machine scheduling problems, where machines are flexibly maintained and total tardiness is used as a performance measure. Machine M _k should be scheduled for maintenance for a constant time, w _k . It is assumed that the maintenance period [u _k , v _k ] is set in advance and that the maintenance time, w _k , does not exceed the maintenance period (i.e., w _k ≤v _k −u _k ). The time u _k (v _k ) is the earliest (or latest) time at which machine M _k starts (or stops) its maintenance. Two cases, resumable and unresumable, are considered in the single machine and parallel machine problems. Eight mixed binary integer programming models are developed to derive the optimal schedule for the problem, and size complexity and computer solution times are provided to demonstrate the models' efficiency.

Keywords:

• Scheduling
• Integer programming
• Single machine
• Parallel machine

Acknowledgements

This research was partially supported by the National Science Council of Taiwan, Republic of China, under contract NSC93-2213-E-269-003.

Additional information

Notes on contributors

Jen-Shiang Chen

Email: [email protected] or [email protected]