Minimizing the number of tardy jobs for the single machine scheduling problem: MIP-based lower and upper bounds
- 1 January 2013
- journal article
- Published by EDP Sciences in RAIRO - Operations Research
- Vol. 47 (1) , 33-46
Abstract
This paper considers the problem of scheduling n jobs on a single machine. A fixed processing time and an execution interval are associated with each job. Preemption is not allowed. The objective is to find a feasible job sequence that minimizes the number of tardy jobs. On the basis of an original mathematical integer programming formulation, this paper shows how good-quality lower and upper bounds can be computed. Numerical experiments are provided for assessing the proposed approach.Keywords
This publication has 20 references indexed in Scilit:
- Minimizing the number of tardy jobs in a single-machine scheduling problem with periodic maintenanceComputers & Operations Research, 2012
- New solution methods for single machine bicriteria scheduling problem: Minimization of average flowtime and number of tardy jobsEuropean Journal of Operational Research, 2010
- An efficient ILP formulation for the single machine scheduling problemRAIRO - Operations Research, 2010
- A bicriteria approach to minimize number of tardy jobs and resource consumption in scheduling a single machineInternational Journal of Production Economics, 2009
- Single machine scheduling to minimize total weighted earliness subject to minimal number of tardy jobsEuropean Journal of Operational Research, 2009
- Minimizing the weighted number of tardy jobs on a single machine with release datesEuropean Journal of Operational Research, 2007
- An Exact Method to Minimize the Number of Tardy Jobs in Single Machine SchedulingJournal of Scheduling, 2004
- Minimizing the weighted number of tardy jobs on a single machineEuropean Journal of Operational Research, 2003
- A branch and bound to minimize the number of late jobs on a single machine with release time constraintsEuropean Journal of Operational Research, 2003
- Complexity of Machine Scheduling Problems1977