×

A branch-and-bound algorithm to minimize total tardiness with different release dates. (English) Zbl 0762.90035

Summary: This article deals with the scheduling problem for minimizing total tardiness with unequal release dates. A set of jobs have to be scheduled on a machine able to perform only one job at a time. No preemptive job is allowed. This problem has been proven to be NP-hard. We prove some dominance properties, and provide a lower bound polynomially computed for this problem. On the basis of our previous results, we propose a branch- and-bound algorithm to solve the problem. This algorithm was tested on hard problems involving 30 jobs and also on relatively easy problems with up to 230 jobs. Detailed computational results are given.

MSC:

90B35 Deterministic scheduling theory in operations research
90-08 Computational methods for problems pertaining to operations research and mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Introduction to Sequencing and Scheduling, Wiley, New York, 1974.
[2] Baker, Journal of Operations Management 3 pp 37– (1982)
[3] Baker, Operations Research 26 pp 111– (1978)
[4] , and , ”A Branch and Bound Algorithm for Scheduling Jobs with Release Dates on a Single Machine to Minimize Total Weighted Completion Time”, Preprint No. OR14, Faculty of Mathematical Studies, University of Southampton (1989).
[5] and , ”Minimisation de la Somme des Retards pour les Problemes d’Ordonnancement à Une Machine”, Rapport de Recherche No. 1023, INRIA, France (1989).
[6] Chu, European Journal of Operational Research 56 (1991)
[7] , and , Theory of Scheduling, Addison-Wesley, Reading, MA, 1967.
[8] Du, Mathematics of Operations Research 15 pp 483– (1990)
[9] Emmons, Operations Research 17 pp 701– (1969)
[10] Fisher, Mathematical Programming 11 pp 229– (1976)
[11] Sequencing and Scheduling: An Introduction to the Mathematics of the Job-Shop, Ellis Horwood Ltd., 1982.
[12] Grabowski, European Journal of Operational Research 26 pp 278– (1986)
[13] Gupta, OMEGA International Journal of Management Science 15 pp 207– (1987)
[14] Hariri, Discrete Applied Mathematics 5 pp 99– (1983)
[15] Lawler, Annals of Discrete Mathematics 1 pp 331– (1977)
[16] Lawler, Operations Research Letters 1 pp 207– (1982)
[17] , , and , ”Sequencing and Scheduling: Algorithms and Complexity”, Report No. BS-R8909, Center for Mathematics and Computer Science, Amsterdam (1989).
[18] Mohan, Operations Research 35 pp 450– (1987)
[19] Potts, Operations Research Letters 1 pp 177– (1982)
[20] Potts, Operations Research 33 pp 363– (1985)
[21] Potts, European Journal of Operational Research 32 pp 405– (1987)
[22] Machine Sequencing Problems: Classification, Complexity and Computation, Nijhoff, The Hague, 1976.
[23] Schrage, Operations Research 16 pp 687– (1968)
[24] Smith, Naval Research Logistics Quarterly 3 pp 59– (1956)
[25] Srinivasan, Naval Research Logistics Quarterly 18 pp 317– (1971)
[26] Wilkerson, AIIE Transactions 3 pp 239– (1971) · doi:10.1080/05695557108974812
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.