Robust single machine scheduling with a flexible maintenance activity

In this paper, we address a problem arising in a manufacturing environment concerning the joint scheduling of multiple jobs and a maintenance activity on a single machine. Such activity must be processed within a given time window and its non-deterministic duration takes values in a given interval. We seek job schedules which are robust to any possible changes in the maintenance activity duration. We consider makespan and total completion time objectives under four different robustness criteria. We discuss a few properties and the complexity of finding robust schedules for the resulting eight problem scenarios. For the case of total completion time objective and maximum absolute regret criterion, we design and test exact and heuristic algorithms. The results of an extensive computational campaign, performed for assessing the performance of the proposed solution approaches, are reported.