Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
  Scheduling with AND/OR Precedence Constraints

Moehring, R. H., Skutella, M., & Stork, F. (2004). Scheduling with AND/OR Precedence Constraints. SIAM Journal on Computing, 33, 393-415.

Item is

Dateien

einblenden: Dateien
ausblenden: Dateien
:
SICOMP.pdf (Verlagsversion), 245KB
 
Datei-Permalink:
-
Name:
SICOMP.pdf
Beschreibung:
-
OA-Status:
Sichtbarkeit:
Privat
MIME-Typ / Prüfsumme:
application/pdf
Technische Metadaten:
Copyright Datum:
-
Copyright Info:
-
Lizenz:
-

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Moehring, Rolf H., Autor
Skutella, Martin1, Autor           
Stork, Frederik, Autor
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: In many scheduling applications it is required that the processing of some job must be postponed until some other job, which can be chosen from a pre-given set of alternatives, has been completed. The traditional concept of precedence constraints fails to model such restrictions. Therefore, the concept has been generalized to so-called AND/OR precedence constraints which can cope with this kind of requirement. In the context of traditional precedence constraints, feasibility, transitivity, as well as the computation of earliest start times for jobs are fundamental, well-studied problems. The purpose of this paper is to provide efficient algorithms for these tasks for the more general and complex model of AND/OR precedence constraints. We show that feasibility as well as many questions related to transitivity can be solved by applying essentially the same linear-time algorithm. In order to compute earliest start times we propose two polynomial-time algorithms to cope with different classes of time distances between jobs.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2005-06-092004
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: Expertenbegutachtung
 Identifikatoren: eDoc: 231969
Anderer: Local-ID: C1256428004B93B8-868BC741D92B006FC1256E470040FF56-MoehringSkutellaStork2004
 Art des Abschluß: -

Veranstaltung

einblenden:

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: SIAM Journal on Computing
Genre der Quelle: Zeitschrift
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: 33 Artikelnummer: - Start- / Endseite: 393 - 415 Identifikator: ISSN: 0097-5397