Briskorn, Dirk Choi, Byung-Cheon Lee, Kangbok Leung, Joseph Pinedo, Michael
Year of Publication:
Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel No. 640
Universität Kiel, Institut für Betriebswirtschaftslehre, Kiel
This paper studies inventory constraints in a machine scheduling environment. Jobs can add and remove items of different types to the inventory and from the inventory, respectively. Jobs removing items cannot be processed if the required amount of items is not available. We first have a look at general models and determine the computational status of these problems. Since it turns out that general models are strongly NP-hard except for makespan minimization on one machine we have a look at special cases in the following. We determine the computational complexity of all considered special cases for objection functions ∑Cj and Lmax and several special cases for objective functions ∑wjCj and ∑Uj.