Robust single machine scheduling with external-party jobs

Abstract In this paper we address a problem arising in a manufacturing environment in which the owner of a machining resource, besides its own jobs, must process also jobs belonging to an external party. Due to contract commitments, the jobs of the external party must be processed within a certain due date, that can be considered as a deadline. Moreover, these jobs have a given release date corresponding to their actual availability in the manufacturing system. The external party jobs arrive with an estimate of their durations and the owner of the machining resource, when planning the schedule of its jobs, must take into account possible deviations from the nominal values of the external processing times. It is therefore important to determine a schedule which is robust to any possible changes in the durations of the external jobs. We consider the total completion time objective for the owner of the machining resource. However, due to the uncertainty on the external jobs processing times, we seek for a solution minimizing the maximum absolute deviation from an optimal schedule. We derive some properties of such robust schedules and evaluate the performance two mixed integer linear programming formulations.