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

DC FieldValueLanguage
dc.contributor.authorBrucker, P
dc.contributor.authorHilbig, T
dc.contributor.authorHurink, J
dc.date.accessioned2021-12-23T16:04:50Z-
dc.date.available2021-12-23T16:04:50Z-
dc.date.issued1999
dc.identifier.issn0166218X
dc.identifier.urihttps://osnascholar.ub.uni-osnabrueck.de/handle/unios/6624-
dc.description3th International Conference on Graphs and Optimization (GO-III Meeting), LEUKERBAD, SWITZERLAND, AUG 27-30, 1998
dc.description.abstractPositive 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.
dc.language.isoen
dc.publisherELSEVIER SCIENCE BV
dc.relation.ispartofDISCRETE APPLIED MATHEMATICS
dc.subjectbranch and bound
dc.subjectCOMPLEXITY
dc.subjectMathematics
dc.subjectMathematics, Applied
dc.subjectmulti-processor tasks
dc.subjectmulti-purpose machines
dc.subjectMULTIPROCESSOR TASKS
dc.subjectNETWORKS
dc.subjectscheduling
dc.subjectSHOP PROBLEM
dc.subjectshop problems
dc.subjecttime-lags
dc.titleA branch and bound algorithm for a single-machine scheduling problem with positive and negative time-lags
dc.typeconference paper
dc.identifier.doi10.1016/S0166-218X(99)00015-3
dc.identifier.isiISI:000081062200006
dc.description.volume94
dc.description.issue1-3
dc.description.startpage77
dc.description.endpage99
dc.contributor.orcid0000-0001-6986-5633
dc.contributor.researcheridI-4491-2019
dc.publisher.placePO BOX 211, 1000 AE AMSTERDAM, NETHERLANDS
dcterms.isPartOf.abbreviationDiscret Appl. Math.
dcterms.oaStatusBronze, Green Submitted
Show simple item record

Page view(s)

5
Last Week
0
Last month
0
checked on Apr 23, 2024

Google ScholarTM

Check

Altmetric