Robust scheduling to minimize the weighted number of late jobs with interval due-date uncertainty

2017/08/08 by Drwal, Maciej
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1708.03252

Abstract

We consider the class of single machine scheduling problems with the objective to minimize the weighted number of late jobs, under the assumption that completion due-dates are not known precisely at the time when decision-maker must provide a schedule. It is assumed that only the intervals to which the due-dates belong are known. The concept of maximum regret is used to define robust solution. A polynomial time algorithm is given for the case when weights of jobs are all equal. A mixed-integer linear programming formulation is provided for the general case, and computational experiments are reported.

Related

• Min-Max Regret Scheduling To Minimize the Total Weight of Late Jobs With Interval Uncertainty
• Robust unrelated parallel machine scheduling problem with interval release dates
• Investigating the Recoverable Robust Single Machine Scheduling Problem Under Interval Uncertainty
• The robust single machine scheduling problem with uncertain release and processing times
• New Algorithms for Minimizing the Weighted Number of Tardy Jobs On a Single Machine