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.  Zbl0893.90083
  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.  Zbl1140.90390
  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.  Zbl1056.90054
  6. P. Baptiste, A. Jouglet and D. Savourey, Lower bounds for parallel machine scheduling problems. Int. J. Oper. Res.3 (2008) 643–664.  Zbl1144.90376
  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.  Zbl0949.90583
  8. C. Chu, A branch and bound algorithm to minimise total flow time with unequal release dates. Nav. Res. Logist.39 (1992) 859–875.  Zbl0766.90039
  9. C. Chu, A branch and bound algorithm to minimize total tardiness with release dates. Nav. Res. Logist.39 (1992) 265–283.  Zbl0762.90035
  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.  Zbl0176.50005
  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.  Zbl0917.90193
  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.  Zbl1048.90107
  15. R. Nessah and C. Chu, An efficient branch and bound algorithm for the problem Pm | rj |  ∑ Cj. Submitted manuscript.  Zbl1206.90046
  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.  Zbl0566.90046
  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.  Zbl1111.90046
  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.  Zbl0711.65046
  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.  Zbl1146.90425
  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.  Zbl1062.90030
  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.

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.