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

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 Mk should be scheduled for maintenance for a constant time, wk. It is assumed that the maintenance period [uk, vk] is set in advance and that the maintenance time, wk, does not exceed the maintenance period (i.e., wk ≤ vk − uk). The time uk (vk) is the earliest (or latest) time at which machine Mk 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.