Solving Project Scheduling Problems by Minimum Cut Computations

dc.contributor.authorMöhring, Rolf H.
dc.contributor.authorSchulz, Andreas S.
dc.contributor.authorStork, Frederik
dc.contributor.authorUetz, Marc
dc.date.accessioned2021-12-17T10:17:50Z
dc.date.available2021-12-17T10:17:50Z
dc.date.issued2000
dc.description.abstractIn project scheduling, a set of precedence-constrained jobs has to be scheduled so as to minimize a given objective. In resource-constrained project scheduling, the jobs additionally compete for scarce resources. Due to its universality, the latter problem has a variety of applications in manufacturing, production planning, project management, and elsewhere. It is one of the most intractable problems in operations research, and has therefore become a popular playground for the latest optimization techniques, including virtually all local search paradigms. We show that a somewhat more classical mathematical programming approach leads to both competitive feasible solutions and strong lower bounds, within quite reasonable computation times. The basic ingredients of our approach are the Lagrangian relaxation of a time-indexed integer programming formulation and relaxation-based list scheduling, enriched with a useful idea from recent approximation algorithms for machine scheduling problems. The efficiency of the algorithm results from the insight that the relaxed problem can be solved by computing a minimum cut in an appropriately defined directed graph. Our computational study covers different types of resource-constrained project scheduling problems, based on several, notoriously hard test sets, including practical problem instances from chemical production planning.en
dc.identifier.issn2197-8085
dc.identifier.urihttps://depositonce.tu-berlin.de/handle/11303/15959
dc.identifier.urihttp://dx.doi.org/10.14279/depositonce-14732
dc.language.isoenen
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subject.ddc510 Mathematiken
dc.subject.otherproject schedulingen
dc.subject.otherLagrangian relaxationen
dc.subject.otherlower boundsen
dc.subject.otherminimum cutsen
dc.subject.otherordering heuristicsen
dc.titleSolving Project Scheduling Problems by Minimum Cut Computationsen
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, 680en
tub.series.namePreprint-Reihe des Instituts für Mathematik, Technische Universität Berlinen
Files
Original bundle
Now showing 1 - 3 of 3
Loading…
Thumbnail Image
Name:
Report-680-2000.pdf
Size:
211.51 KB
Format:
Adobe Portable Document Format
Description:
Loading…
Thumbnail Image
Name:
Report-680-2000.ps.gz
Size:
94.83 KB
Format:
Unknown data format
Description:
Loading…
Thumbnail Image
Name:
Report-680-2000.ps
Size:
311.01 KB
Format:
Postscript Files
Description:
Collections