Using integer programming to solve the machine scheduling problem with a flexible maintenance activity

Abstract

This work addresses the single machine and parallel machine scheduling problems, where machine is flexibly maintained and mean flow time is used as a performance measure. Machine M_k should be stopped for maintenance for a constant time w_k in the schedule. The maintenance period [u_k , v_k ] is assumed to be set in advance, and the maintenance time w_k is assumed not to exceed the maintenance period (that is, w_k ≤ v_k – u_k ). The time u_k (v_k ) is the earliest (latest) time at which the machine M_k starts (stops) its maintenance. Two cases, resumable and unresumable, are considered in the single machine and parallel machine problems, respectively. Moreover, four integer programming models are developed optimally to solve the problem.

Keywords:

• Scheduling
• maintenance
• integer programming
• single machine
• parallel machine