On the General Feasibility Test of Scheduling Lot Sizes for Several Products on One Machine
研究单机多产品经济批量调度问题，证明其受限版本也是NP难的，并给出一种隐式枚举程序来检验给定生产次数的调度是否可行，可绕过起始时间分析，聚焦生产运行的组合结构。
Given N products and a set of “basic data” for each product, e.g., production rate, demand rate, setup time, setup cost and holding cost, etc., the Economic Lot Scheduling Problem is to find a feasible schedule that allows cyclic production pattern for each product and such that the sum of the setup and inventory carrying costs for all products per unit time is minimized. The routine application of the economic lot size formula to each product separately, often leads to the phenomenon of “interference,” i.e., the machine will be required to produce two items at the same time, which is impossible. In this paper we show that even a very restricted version of the original problem becomes NP-hard. We also give an implicit enumeration procedure for testing the feasibility of a schedule in which product i is set up η i (integer) times per year. The main advantage of our procedure is that we can by-pass the tedious study of the start times and concentrate on the combinatorial structure of the production runs, which thus, theoretically cuts down the number of possible branchings in the enumeration.