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.
Mots clés : single machine scheduling, tardy jobs, dominance conditions, mixed-integer programming
@article{RO_2013__47_1_33_0,
author = {Briand, Cyril and Ourari, Samia},
title = {Minimizing the number of tardy jobs for the single machine scheduling problem: {MIP-based} lower and upper bounds},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {33--46},
publisher = {EDP-Sciences},
volume = {47},
number = {1},
year = {2013},
doi = {10.1051/ro/2013025},
mrnumber = {3031098},
zbl = {1282.90065},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ro/2013025/}
}
TY - JOUR AU - Briand, Cyril AU - Ourari, Samia TI - Minimizing the number of tardy jobs for the single machine scheduling problem: MIP-based lower and upper bounds JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2013 SP - 33 EP - 46 VL - 47 IS - 1 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ro/2013025/ DO - 10.1051/ro/2013025 LA - en ID - RO_2013__47_1_33_0 ER -
%0 Journal Article %A Briand, Cyril %A Ourari, Samia %T Minimizing the number of tardy jobs for the single machine scheduling problem: MIP-based lower and upper bounds %J RAIRO - Operations Research - Recherche Opérationnelle %D 2013 %P 33-46 %V 47 %N 1 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ro/2013025/ %R 10.1051/ro/2013025 %G en %F RO_2013__47_1_33_0
Briand, Cyril; Ourari, Samia. Minimizing the number of tardy jobs for the single machine scheduling problem: MIP-based lower and upper bounds. RAIRO - Operations Research - Recherche Opérationnelle, Tome 47 (2013) no. 1, pp. 33-46. doi : 10.1051/ro/2013025. http://www.numdam.org/articles/10.1051/ro/2013025/
[1] , and , Minimizing the number of late jobs on a single machine under due date uncertainty. J. Sched. 14 (2011) 351-360. | MR | Zbl
[2] and , Complexity of one machine scheduling problems under scenario-based uncertainty. Oper. Res. Lett. 36 (2008) 338-342. | MR | Zbl
[3] , Polynomial time algorithms for minimizing the weighted number of late jobs on a single machine when processing times are equal. J. Sched. 2 (1999) 245-252. | MR | Zbl
[4] , and , A branch and bound to mininimze the number of late jobs on a single machine with release time constraints. Eur. J. Oper. Res. 144 (2003) 1-11. | MR | Zbl
[5] , , and , Sequencing a single machine with due dates and deadlines : an ILP-based approach to solve very large instances. J. Sched. 13 (2010) 39-47. | MR | Zbl
[6] , and , An efficient ILP formulation for the single machine scheduling problem. RAIRO Oper. Res. 44 (2010) 61-71. | Numdam | MR | Zbl
[7] , Problèmes d'ordonnancements à durées égales. QUESTIO 5(4) (1981) 219-228. | Zbl
[8] , , , and , A Note on scheduling equal-length jobs to maximize throughput. J. Sched. 9 (2006) 71-73. | MR | Zbl
[9] and , An exact method to minimize the number of tardy jobs in single machine scheduling. J. Sched. 7 (2004) 405-420. | MR | Zbl
[10] , , and , New solution methods for single machine bicriteria scheduling problem : Minimization of average flowtime and number of tardy jobs. Eur. J. Oper. Res. 201 (2010) 89-98. | MR | Zbl
[11] , , and , A new dominance concept in scheduling n jobs on a single machine with ready times and due dates. Oper. Res. 31 (1983) 114-127. | Zbl
[12] and , Computers and intractability, a guide to the theory of NP-completeness. W. H. Freeman and Company (1979). | MR | Zbl
[13] and , Single machine scheduling to minimize total weighted earliness subject to minimal number of tardy jobs. Eur. J. Oper. Res. 195 (2009) 89-97. | MR | Zbl
[14] , Reducibility among combinatorial problems. in Complexity of Computer Computations, edited by R.E. Miller and J.W. Thatcher. Plenum Press, New York (1972) 85-103. | MR | Zbl
[15] , and , A solvable case of the one-machine scheduling problem with ready and due times. Oper. Res. 26 (1978) 121-126. | MR | Zbl
[16] , Scheduling a single machine to minimize the number of late jobs. Preprint, Computer Science Division, University of California, Berkeley (1982).
[17] , A dynamic programming algorithm for preemptive scheduling of a single machine to minimize the number of late jobs. Ann. Oper. Res. 26 (1990) 125-133. | MR | Zbl
[18] , , Minimizing the number of tardy jobs in a single-machine scheduling problem with periodic maintenance. Comput. Oper. Res. 39 (2012) 2196-2205. | MR | Zbl
[19] , and , Complexity of machine scheduling problems. Ann. Discrete Math. 1 (1977) 343-362. | MR | Zbl
[20] and , Minimizing the weighted number of tardy jobs on a single machine with release dates. Eur. J. Oper. Res. 176 (2007) 727-744. | MR | Zbl
[21] , , Minimizing the weighted number of tardy jobs on a single machine. Eur. J. Oper. Res. 145 (2003) 45-56. | MR | Zbl
[22] , An n job, one machine sequencing algorithm for minimizing the number of late jobs. Manag. Sci. 15(1) (1968) 102-109. | Zbl
[23] and Conditions de dominance pour le problème à une machine avec minimisation des travaux en retard” 9ème Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF'08), Clermont-Ferrand (France) 351-352 (2008).
[24] , and , Single-machine multi-agent scheduling problems with a global objective function. J. Sched. 15 (2011) 311-321. | MR | Zbl
[25] , , and , A bicriteria approach to minimize number of tardy jobs and resource consumption in scheduling a single machine. Int. J. Product. Econom. 119 (2009) 298-307.
Cité par Sources :
