Unit-time scheduling problems with time dependent resources

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