A branch and bound algorithm for a single-machine scheduling problem with positive and negative time-lags

Autor(en): Brucker, P
Hilbig, T
Hurink, J
Stichwörter: branch and bound; COMPLEXITY; Mathematics; Mathematics, Applied; multi-processor tasks; multi-purpose machines; MULTIPROCESSOR TASKS; NETWORKS; scheduling; SHOP PROBLEM; shop problems; time-lags
Erscheinungsdatum: 1999
Herausgeber: ELSEVIER SCIENCE BV
Journal: DISCRETE APPLIED MATHEMATICS
Volumen: 94
Ausgabe: 1-3
Startseite: 77
Seitenende: 99
Zusammenfassung: 
Positive and negative time-lags are general timing restrictions between the starting times of jobs which have been introduced by Roy in connection with the Metra Potential Method. They allow the consideration of positive and negative time-lags between the starting times of jobs. It is shown that complex scheduling problems like general shop problems, problems with multi-processor tasks, problems with multi-purpose machines, and problems with changeover times can be reduced to single-machine problems with positive and negative time-lags between jobs. Furthermore, a branch and bound algorithm is developed for solving such single-machine scheduling problems. The reductions can be used to construct test problems for this algorithm. Computational results for randomly generated single-machine problems and for shop scheduling problems (without time-lags) are reported. (C) 1999 Elsevier Science B.V. All rights reserved.
Beschreibung: 
3th International Conference on Graphs and Optimization (GO-III Meeting), LEUKERBAD, SWITZERLAND, AUG 27-30, 1998
ISSN: 0166218X
DOI: 10.1016/S0166-218X(99)00015-3

Show full item record

Page view(s)

5
Last Week
0
Last month
3
checked on Feb 21, 2024

Google ScholarTM

Check

Altmetric