Branch-and-bound algorithm for total weighted tardiness minimization on parallel machines under release dates assumptions

Imed Kacem; Nizar Souayah; Mohamed Haouari

RAIRO - Operations Research (2012)

  • Volume: 46, Issue: 2, page 125-147
  • ISSN: 0399-0559

Abstract

top
This paper deals with the parallel-machine scheduling problem with the aim of minimizing the total (weighted) tardiness under the assumption of different release dates. This problem has been proven to be NP-hard. We introduce some new lower and upper bounds based on different approaches. We propose a branch-and-bound algorithm to solve the weighted and unweighted total tardiness. Computational experiments were performed on a large set of instances and the obtained results showed that our algorithms are efficient.

How to cite

top

Kacem, Imed, Souayah, Nizar, and Haouari, Mohamed. "Branch-and-bound algorithm for total weighted tardiness minimization on parallel machines under release dates assumptions." RAIRO - Operations Research 46.2 (2012): 125-147. <http://eudml.org/doc/276395>.

@article{Kacem2012,
abstract = {This paper deals with the parallel-machine scheduling problem with the aim of minimizing the total (weighted) tardiness under the assumption of different release dates. This problem has been proven to be NP-hard. We introduce some new lower and upper bounds based on different approaches. We propose a branch-and-bound algorithm to solve the weighted and unweighted total tardiness. Computational experiments were performed on a large set of instances and the obtained results showed that our algorithms are efficient.},
author = {Kacem, Imed, Souayah, Nizar, Haouari, Mohamed},
journal = {RAIRO - Operations Research},
keywords = {Scheduling; weighted tardiness; parallel machines; branch-and-boun; scheduling},
language = {eng},
month = {7},
number = {2},
pages = {125-147},
publisher = {EDP Sciences},
title = {Branch-and-bound algorithm for total weighted tardiness minimization on parallel machines under release dates assumptions},
url = {http://eudml.org/doc/276395},
volume = {46},
year = {2012},
}

TY - JOUR
AU - Kacem, Imed
AU - Souayah, Nizar
AU - Haouari, Mohamed
TI - Branch-and-bound algorithm for total weighted tardiness minimization on parallel machines under release dates assumptions
JO - RAIRO - Operations Research
DA - 2012/7//
PB - EDP Sciences
VL - 46
IS - 2
SP - 125
EP - 147
AB - This paper deals with the parallel-machine scheduling problem with the aim of minimizing the total (weighted) tardiness under the assumption of different release dates. This problem has been proven to be NP-hard. We introduce some new lower and upper bounds based on different approaches. We propose a branch-and-bound algorithm to solve the weighted and unweighted total tardiness. Computational experiments were performed on a large set of instances and the obtained results showed that our algorithms are efficient.
LA - eng
KW - Scheduling; weighted tardiness; parallel machines; branch-and-boun; scheduling
UR - http://eudml.org/doc/276395
ER -

References

top
  1. B. Alidaee and D. Rosa, Scheduling parallel machines to minimize total weighted and unweighted tardness. Comput. Oper. Res.24 (1979) 75–788.  
  2. E.J. Anderson and J.C. Nyirenda, Two new rules to minimize tardiness in a job shop. Int. J. Prod. Res.28 (1990) 2277–2292.  
  3. M. Azizoglu and O. Kirka, Tardiness minimization on parallel machines. Int. J. Prod. Econ.55 (1998) 163–168.  
  4. P. Baptiste and C. Le Pape,Scheduling a single machine to minimize a regular objective function under setup constraints. Discrete Optim.2 (2005) 83–99.  
  5. P. Baptiste, C. Carlier and J. Antoine, A branch, bound procedure to minimze total tardiness on one machine with arbitrary release dates. Eur. J. Oper. Res.158 (2004) 595–608.  
  6. P. Baptiste, A. Jouglet and D. Savourey, Lower bounds for parallel machine scheduling problems. Int. J. Oper. Res.3 (2008) 643–664.  
  7. S.J. Chen and L. Lin, Reducing total tardiness cost in manufacturing cell scheduling by a multi-factor priority rule. Int. J. Prod. Res.37 (1999) 2939–2956.  
  8. C. Chu, A branch and bound algorithm to minimise total flow time with unequal release dates. Nav. Res. Logist.39 (1992) 859–875.  
  9. C. Chu, A branch and bound algorithm to minimize total tardiness with release dates. Nav. Res. Logist.39 (1992) 265–283.  
  10. S.E. Elmaghraby and S.H. Park, Scheduling jobs on a number of identical machines. AIIE Trans.6 (1974) 1–13.  
  11. H. Emmons, One machine sequencing to minimize certain functions of job tardiness. Oper. Res.17 (1969) 701–715.  
  12. C. Koulamas, Polynomially solvable total tardiness problem : review and extensions. Int. J. Manage. Sci.25 (1997) 235–239.  
  13. Y.H. Lee and M. Pinedo, Scheduling jobs on parallel machines with sequence-dependent times. Eur. J. Oper. Res.100 (1997) 464–474.  
  14. G. Mosheiov and D. Oron, A note on the SPT heuristic for solving scheduling problems with generalized due dates. Comput. Oper. Res.31 (2004) 645–655.  
  15. R. Nessah and C. Chu, An efficient branch and bound algorithm for the problem Pm | rj |  ∑ Cj. Submitted manuscript.  
  16. C.N. Potts and L.N. Van Wassenhove, A branch and bound algorithm for the total weighted tardiness problem. Oper. Res.33 (1985) 363–377.  
  17. A.H.G. Rinnooy Kan, Machine sequencing problem : classification, complexity and computaion. Nijhoff, The Hague (1976).  
  18. S.-O. Shim and Y.-D. Kim, Scheduling on parallel identical machines to minimize total tardiness. Eur. J. Oper. Res.177 (2007) 135–146.  
  19. H.D. Sherali and O. Ulular, Conjugate gradient methods using quasi-Newton updates with inexact line searches. J. Math. Anal. Appl.150 (1990) 359–377.  
  20. N. Souayah, I. Kacem, M. Haouari and C. Chu Scheduling on parallel identical machines to minimise the total weighted tardiness. Int. J. Adv. Oper. Manage.1 (2009) 30–69.  
  21. L.-H. Su and C.-J. Chen, Minimizing totla tardiness on a single machine with unequal release dates. Eur. J. Oper. Res.186 (2008) 496–503.  
  22. Z.J. Tian, C.T. Ng and T.C.E. Cheng, On the single machine total tardiness problem. Eur. J. Oper. Res.165 (2005) 843–846.  
  23. F. Yalaoui and C. Chu, Parallel machines scheduling to minimize total tardiness. Int. J. Prod. Econ.76 (2002) 265–279.  
  24. F. Yalaoui and C. Chu, New exact method to solve the Pm | rj | ∑ Cj schedule problem. Int. J. Prod. Econ.100 (2005) 168–179. 

NotesEmbed ?

top

You must be logged in to post comments.