Resource-Constrained Project Scheduling: From a Lagrangian Relaxation to Competitive Solutions

dc.contributor.authorStork, Frederik
dc.contributor.authorUetz, Marc
dc.date.accessioned2021-12-17T10:18:21Z
dc.date.available2021-12-17T10:18:21Z
dc.date.issued2000
dc.description.abstractList scheduling belongs to the classical and widely used algorithms for scheduling problems, but for resource-constrained project scheduling problems most standard priority lists do not capture enough of the problem structure, often resulting in poor performance. We use a well-known Lagrangian relaxation to first compute schedules which do not necessarily respect the resource constraints. We then apply list scheduling in the order of so-called α-completion times of jobs. Embedded into a standard subgradient optimization, our computational results show that the schedules compare to those obtained by state-of-the-art local search algorithms. In contrast to purely primal heuristics, however, the Lagrangian relaxation also provides powerful lower bounds, thus the deviation between lower and upper bounds can be drastically reduced by this approach.en
dc.identifier.issn2197-8085
dc.identifier.urihttps://depositonce.tu-berlin.de/handle/11303/15970
dc.identifier.urihttp://dx.doi.org/10.14279/depositonce-14743
dc.language.isoenen
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subject.ddc510 Mathematiken
dc.subject.otherschedulingen
dc.subject.otherproject schedulingen
dc.subject.otherLagrangian relaxationen
dc.subject.otherlist schedulingen
dc.titleResource-Constrained Project Scheduling: From a Lagrangian Relaxation to Competitive Solutionsen
dc.typeResearch Paperen
dc.type.versionsubmittedVersionen
tub.accessrights.dnbfreeen
tub.affiliationFak. 2 Mathematik und Naturwissenschaften::Inst. Mathematikde
tub.affiliation.facultyFak. 2 Mathematik und Naturwissenschaftende
tub.affiliation.instituteInst. Mathematikde
tub.publisher.universityorinstitutionTechnische Universität Berlinen
tub.series.issuenumber2000, 661en
tub.series.namePreprint-Reihe des Instituts für Mathematik, Technische Universität Berlinen

Files

Original bundle
Now showing 1 - 2 of 2
Loading…
Thumbnail Image
Name:
Report-661-2000.pdf
Size:
88.46 KB
Format:
Adobe Portable Document Format
No Thumbnail Available
Name:
Report-661-2000.ps.gz
Size:
87.32 KB
Format:
Unknown data format

Collections