Forcing Relations for AND/OR Precedence Constraints

dc.contributor.authorMöhring, Rolf H.
dc.contributor.authorSkutella, Martin
dc.contributor.authorStork, Frederik
dc.date.accessioned2021-12-17T10:16:40Z
dc.date.available2021-12-17T10:16:40Z
dc.date.issued1999
dc.description.abstractA natural generalization of ordinary precedence constraints are so-called AND/ OR precedence constraints. In an AND constraint, a job must wait for all its predecessors while in an OR constraint, a job has to wait for at least one of its predecessors. We provide a linear-time algorithm for deducing additional AND/ OR precedence constraints that are implied by the given ones. We show that this algorithm can also be used to verify feasibility of the given constraints. Besides their theoretical value, these results have significant impact in practical applications such as scheduling and assembly sequencing; we show how to use our algorithm to improve solution procedures for resource-constrained project scheduling problems. Finally, we prove that for a related, more general model, the problems under consideration are strongly NP-complete.en
dc.identifier.issn2197-8085
dc.identifier.urihttps://depositonce.tu-berlin.de/handle/11303/15935
dc.identifier.urihttp://dx.doi.org/10.14279/depositonce-14708
dc.language.isoenen
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subject.ddc510 Mathematiken
dc.subject.otherprecedence constraintsen
dc.subject.otherAND/ORen
dc.subject.otherrelationsen
dc.subject.otherAND constrainten
dc.subject.otherOR constraintsen
dc.titleForcing Relations for AND/OR Precedence Constraintsen
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.issuenumber1999, 646en
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-646-1999.pdf
Size:
166.57 KB
Format:
Adobe Portable Document Format
No Thumbnail Available
Name:
Report-646-1999.ps.gz
Size:
68.15 KB
Format:
Unknown data format

Collections