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

Cyril Briand; Samia Ourari

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

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

Abstract

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

How to cite

top

Briand, 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. [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. [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. [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. [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. [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. [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. [7] J. Carlier, Problèmes d’ordonnancements à durées égales. QUESTIO 5(4) (1981) 219–228. Zbl0774.90043
  8. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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 ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.