On the Representation of Resource Constraints in Project Scheduling

dc.contributor.authorStork, Frederik
dc.contributor.authorUetz, Marc
dc.date.accessioned2021-12-17T10:17:35Z
dc.date.available2021-12-17T10:17:35Z
dc.date.issued2000
dc.description.abstractIn project scheduling, resource constraints are usually defined via resource consumption and -availability. Many algorithmic approaches, however, are based on the concept of minimal forbidden sets to represent the resource constraints. Jobs of a forbidden set can be scheduled simultaneously with respect to the precedence constraints, however, they consume more resources than available. Forbidden sets are usually not given explicitly, and by definition even the number of inclusion-minimal forbidden sets may be exponential in the number of jobs. In this paper, we propose a simple branch-and-bound type algorithm to efficiently compute and represent all minimal forbidden sets for a given instance. We evaluate the algorithm on well established test sets of the project scheduling problem library PSPLIB. In addition, we exhibit intimite relations between the different representations of resource constraints and threshold hypergraphs.en
dc.identifier.issn2197-8085
dc.identifier.urihttps://depositonce.tu-berlin.de/handle/11303/15954
dc.identifier.urihttp://dx.doi.org/10.14279/depositonce-14727
dc.language.isoenen
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subject.ddc510 Mathematiken
dc.subject.otherproject schedulingen
dc.subject.otherresource constraintsen
dc.subject.otherforbidden setsen
dc.subject.otherthreshold hypergraphsen
dc.subject.otherthreshold dimensionen
dc.subject.otherminmal cover inequalitiesen
dc.titleOn the Representation of Resource Constraints in Project Schedulingen
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, 693en
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-693-2000.pdf
Size:
205.33 KB
Format:
Adobe Portable Document Format
Description:
Loading…
Thumbnail Image
Name:
Report-693-2000.ps
Size:
466.9 KB
Format:
Postscript Files
Description:
Collections