Unit-time scheduling problems with time dependent resources

T. Tautenhahn, G. Woeginger

    Research output: Contribution to journalArticleAcademicpeer-review

    5 Citations (Scopus)

    Abstract

    We investigate the computational complexity of scheduling problems, where the operations consume certain amounts of renewable resources which are available in time-dependent quantities. In particular, we consider unit-time open shop problems and unit-time scheduling problems with identical parallel processors. For the case where the number of machines, the number of resources and the demand for every resource are all bounded by a constant, we derive polynomial time results for several objective functions. Furthermore, we establish a borderline between hard and easy variants of such problems by proving NP-hardness of most remaining cases. Wir untersuchen die Komplexität einiger Reihenfolgeprobleme, in denen die Abarbeitung der Operationen das Vorhandensein von gewissen Mengen erneuerbarer Ressourcen verlangt, die in zeitabhängigen Mengen verfügbar sind. Wir betrachten Open-Shop Systeme und Systeme mit parallelen Prozessoren mit Einheits-Zeit Operationen. Für den Fall, daß die Anzahl der Maschinen, die Anzahl der Ressourcen und der Ressourcenbedarf jeder Operation durch eine Konstante nach oben beschränkt sind, leiten wir polynomiale Algorithmen für einige Zielfunktionen her. Außerdem ziehen wir eine Grenzlinie zwischen einfachen und schwierigen Varianten, indem wir die NP-vollständigkeit der meisten übrigen Problemvarianten beweisen.
    Original languageEnglish
    Pages (from-to)97-111
    Number of pages15
    JournalComputing
    Volume58
    Issue number2
    DOIs
    Publication statusPublished - 1997

    Fingerprint Dive into the research topics of 'Unit-time scheduling problems with time dependent resources'. Together they form a unique fingerprint.

    Cite this