# Minimizing the number of tardy jobs for the single machine scheduling problem: MIP-based lower and upper bounds

RAIRO - Operations Research - Recherche Opérationnelle (2013)

- Volume: 47, Issue: 1, page 33-46
- ISSN: 0399-0559

## Access Full Article

top## Abstract

top## How to cite

topBriand, Cyril, and 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 47.1 (2013): 33-46. <http://eudml.org/doc/275096>.

@article{Briand2013,

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.},

author = {Briand, Cyril, Ourari, Samia},

journal = {RAIRO - Operations Research - Recherche Opérationnelle},

keywords = {single machine scheduling; tardy jobs; dominance conditions; mixed-integer programming},

language = {eng},

number = {1},

pages = {33-46},

publisher = {EDP-Sciences},

title = {Minimizing the number of tardy jobs for the single machine scheduling problem: MIP-based lower and upper bounds},

url = {http://eudml.org/doc/275096},

volume = {47},

year = {2013},

}

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

PB - EDP-Sciences

VL - 47

IS - 1

SP - 33

EP - 46

AB - 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.

LA - eng

KW - single machine scheduling; tardy jobs; dominance conditions; mixed-integer programming

UR - http://eudml.org/doc/275096

ER -

## References

top- [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. Zbl1229.90053MR2818763
- [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. Zbl1151.90390MR2424458
- [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. Zbl0971.90026MR1989823
- [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. Zbl1037.90022MR1940074
- [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. Zbl1185.90065MR2593100
- [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. Zbl1183.90161MR2642916
- [7] J. Carlier, Problèmes d’ordonnancements à durées égales. QUESTIO 5(4) (1981) 219–228. Zbl0774.90043
- [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. Zbl1154.90430MR2201238
- [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. Zbl1154.90437MR2108383
- [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. Zbl1177.90154MR2573331
- [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. Zbl0495.90046
- [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). Zbl0411.68039MR519066
- [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. Zbl1161.90008MR2474143
- [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. Zbl0366.68041MR378476
- [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. Zbl0377.90054MR462552
- [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. Zbl0709.90064MR1087819
- [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. Zbl1251.90162MR2880072
- [19] J.K. Lenstra, A.H.G. Rinnooy Han and P. Brucker, Complexity of machine scheduling problems. Ann. Discrete Math.1 (1977) 343–362. Zbl0353.68067MR456421
- [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. Zbl1103.90045MR2267438
- [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. Zbl1012.90009MR1947155
- [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. Zbl0164.20002
- [23] S. Ourari and C. BriandConditions 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. Zbl1280.90074MR2925022
- [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.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.