Openshop scheduling under linear resources constraints
研究了在资源可用量和工位消耗能力随时间变化的情况下，如何分配线性资源以最小化开放车间的调度长度，并给出了多项式算法和NP困难性证明。
Consider n jobs (J1, …, Jn), m working stations (M1, …, Mm) and λ linear resources (R1, …, Rλ). Job Ji consists of m operations (Oi1, …, Oim). Operation Oij requires Pk(i, j) units of resource Rk to be realized in an Mj. The availability of resource Rk and the ability of the working station Mh to consume resource Rk, vary over time. An operation involving more than one resource consumes them in constant proportions equal to those in which they are required. The order in which operations are realized is immaterial. We seek an allocation of the resources such that the schedule length is minimized. In this paper, polynomial algorithms are developed for several problems, while NP-hardness is demonstrated for several others. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 51–66, 1998