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: 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] Minimizing the number of late jobs on a single machine under due date uncertainty. J. Sched. 14 (2011) 351-360. | MR | Zbl

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

and ,[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] 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

, and ,[5] 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

, , and ,[6] An efficient ILP formulation for the single machine scheduling problem. RAIRO Oper. Res. 44 (2010) 61-71. | Numdam | MR | Zbl

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

,[8] A Note on scheduling equal-length jobs to maximize throughput. J. Sched. 9 (2006) 71-73. | MR | Zbl

, , , and ,[9] An exact method to minimize the number of tardy jobs in single machine scheduling. J. Sched. 7 (2004) 405-420. | MR | Zbl

and ,[10] 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

, , and ,[11] 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

, , and ,[12] Computers and intractability, a guide to the theory of NP-completeness. W. H. Freeman and Company (1979). | MR | Zbl

and ,[13] 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

and ,[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] A solvable case of the one-machine scheduling problem with ready and due times. Oper. Res. 26 (1978) 121-126. | MR | Zbl

, and ,[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] Complexity of machine scheduling problems. Ann. Discrete Math. 1 (1977) 343-362. | MR | Zbl

, and ,[20] Minimizing the weighted number of tardy jobs on a single machine with release dates. Eur. J. Oper. Res. 176 (2007) 727-744. | MR | Zbl

and ,[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] 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).

and[24] Single-machine multi-agent scheduling problems with a global objective function. J. Sched. 15 (2011) 311-321. | MR | Zbl

, and ,[25] 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.

, , and ,*Cited by Sources: *