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
Access Full Article
top
Abstract
topHow to cite
topKacem, 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- B. Alidaee and D. Rosa, Scheduling parallel machines to minimize total weighted and unweighted tardness. Comput. Oper. Res.24 (1979) 75–788.
- 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.
- M. Azizoglu and O. Kirka, Tardiness minimization on parallel machines. Int. J. Prod. Econ.55 (1998) 163–168.
- 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.
- 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.
- P. Baptiste, A. Jouglet and D. Savourey, Lower bounds for parallel machine scheduling problems. Int. J. Oper. Res.3 (2008) 643–664.
- 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.
- C. Chu, A branch and bound algorithm to minimise total flow time with unequal release dates. Nav. Res. Logist.39 (1992) 859–875.
- C. Chu, A branch and bound algorithm to minimize total tardiness with release dates. Nav. Res. Logist.39 (1992) 265–283.
- S.E. Elmaghraby and S.H. Park, Scheduling jobs on a number of identical machines. AIIE Trans.6 (1974) 1–13.
- H. Emmons, One machine sequencing to minimize certain functions of job tardiness. Oper. Res.17 (1969) 701–715.
- C. Koulamas, Polynomially solvable total tardiness problem : review and extensions. Int. J. Manage. Sci.25 (1997) 235–239.
- Y.H. Lee and M. Pinedo, Scheduling jobs on parallel machines with sequence-dependent times. Eur. J. Oper. Res.100 (1997) 464–474.
- 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.
- R. Nessah and C. Chu, An efficient branch and bound algorithm for the problem Pm | rj | ∑ Cj. Submitted manuscript.
- 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.
- A.H.G. Rinnooy Kan, Machine sequencing problem : classification, complexity and computaion. Nijhoff, The Hague (1976).
- S.-O. Shim and Y.-D. Kim, Scheduling on parallel identical machines to minimize total tardiness. Eur. J. Oper. Res.177 (2007) 135–146.
- 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.
- 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.
- 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.
- 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.
- F. Yalaoui and C. Chu, Parallel machines scheduling to minimize total tardiness. Int. J. Prod. Econ.76 (2002) 265–279.
- 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 ?
topYou 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.