Inventory constrained scheduling on a single machine - Dirk Briskorn; Byung-Cheon Choi; Kangbok Lee; Joseph Leung; Michael Pinedo (Universität Kiel, Institut für Betriebswirtschaftslehre, 2008)
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.
Keywords: 650; Machine scheduling; inventory constraints; computational complexity; Scheduling-Verfahren; Lagerhaltungsmodell; Theorie