Robust min–max regret scheduling to minimize the weighted number of late jobs with interval processing times

Abstract

We consider the robust version of single machine scheduling problem with the objective to minimize the weighted number of jobs completed after their due-dates. The jobs have uncertain processing times represented by intervals, and decision-maker must determine their execution sequence that minimizes the maximum regret. We develop an exact solution algorithm based on a specialized branch and bound method, using mixed-integer linear programming formulations for a common due-date and for job-dependent due-dates. Finally, we examine the solution algorithm in a series of computational experiments.