Minimizing the number of tardy jobs for the single machine scheduling problem: MIP-based lower and upper bounds
RAIRO - Operations Research - Recherche Opérationnelle, Volume 47 (2013) no. 1, pp. 33-46.

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.

DOI: 10.1051/ro/2013025
Classification: 90B35, 90C11
Keywords: 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://archive.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://archive.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://archive.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, Volume 47 (2013) no. 1, pp. 33-46. doi : 10.1051/ro/2013025. http://archive.numdam.org/articles/10.1051/ro/2013025/

[1] H. Aissi, M.A. Aloulou and M.Y. Kovalyov, Minimizing the number of late jobs on a single machine under due date uncertainty. J. Sched. 14 (2011) 351-360. | MR | Zbl

[2] M.A. Aloulou and F. Della-Croce, Complexity of one machine scheduling problems under scenario-based uncertainty. Oper. Res. Lett. 36 (2008) 338-342. | MR | Zbl

[3] P. Baptiste, 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] P. Baptiste, L. Peridy and E. Pinson, 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] P. Baptiste, F. Della Croce, A. Grosso and V. T'Kindt, 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] C. Briand, S. Ourari and B. Bouzouia, An efficient ILP formulation for the single machine scheduling problem. RAIRO Oper. Res. 44 (2010) 61-71. | Numdam | MR | Zbl

[7] J. Carlier, Problèmes d'ordonnancements à durées égales. QUESTIO 5(4) (1981) 219-228. | Zbl

[8] M. Chrobak, C. Dürr, W. Jawor, L. Kowalik and M. Kurowski, A Note on scheduling equal-length jobs to maximize throughput. J. Sched. 9 (2006) 71-73. | MR | Zbl

[9] S. Dauzère-Pérès and M. Sevaux, An exact method to minimize the number of tardy jobs in single machine scheduling. J. Sched. 7 (2004) 405-420. | MR | Zbl

[10] F.S. Erenay, I. Sabuncuoglu, A. Toptal and M.K. Tiwari, 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] J. Erschler, G. Fontan, C. Merce and F. Roubellat, 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] M.R. Garey and D.S. Johnson, Computers and intractability, a guide to the theory of NP-completeness. W. H. Freeman and Company (1979). | MR | Zbl

[13] W. Guohua and P.-C.Y. Benjamin, 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] R.M. Karp, 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] H. Kise, I. Toshihide and H. Mine, A solvable case of the one-machine scheduling problem with ready and due times. Oper. Res. 26 (1978) 121-126. | MR | Zbl

[16] E.L. Lawler, Scheduling a single machine to minimize the number of late jobs. Preprint, Computer Science Division, University of California, Berkeley (1982).

[17] E.L. Lawler, 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] J.Y. Lee, Y.D. Kim, 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] J.K. Lenstra, A.H.G. Rinnooy Han and P. Brucker, Complexity of machine scheduling problems. Ann. Discrete Math. 1 (1977) 343-362. | MR | Zbl

[20] R. M'Hallah and R.L. Bulfin, 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] R. M'Hallah, R.L. Bulfin, Minimizing the weighted number of tardy jobs on a single machine. Eur. J. Oper. Res. 145 (2003) 45-56. | MR | Zbl

[22] M.J. Moore, An n job, one machine sequencing algorithm for minimizing the number of late jobs. Manag. Sci. 15(1) (1968) 102-109. | Zbl

[23] S. Ourari and C. Briand 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] N.H. Tuong, A. Soukhal and J.-C. Billaut, Single-machine multi-agent scheduling problems with a global objective function. J. Sched. 15 (2011) 311-321. | MR | Zbl

[25] L. Yedidsion, D. Shabtay, E. Korach and M. Kaspi, 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.

Cited by Sources: