Robust scheduling to minimize the weighted number of late jobs with interval due-date uncertainty
Author:
Preprint
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.Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- Complexity of interval minmax regret scheduling on parallel identical machines with total completion time criterionOperations Research Letters, 2016
- Robust single machine scheduling for minimizing total flow time in the presence of uncertain processing timesComputers & Industrial Engineering, 2014
- Minimizing the number of late jobs on a single machine under due date uncertaintyJournal of Scheduling, 2010
- Minimizing total weighted flow time of a set of jobs with interval processing timesMathematical and Computer Modelling, 2009
- Complexity of single machine scheduling problems under scenario-based uncertaintyOperations Research Letters, 2008
- Complexity of minimizing the total flow time with interval data and minmax regret criterionDiscrete Applied Mathematics, 2006
- A Mixed Integer Programming Formulation for the Total Flow Time Single Machine Robust Scheduling Problem with Interval DataJournal of Mathematical Modelling and Algorithms, 2006
- Minimizing maximal regret in the single machine sequencing problem with maximum lateness criterionOperations Research Letters, 2004
- An improved algorithm for selecting p items with uncertain returns according to the minmax-regret criterionMathematical Programming, 2004
- On the complexity of a class of combinatorial optimization problems with uncertaintyMathematical Programming, 2001