On the General Feasibility Test of Scheduling Lot Sizes for Several Products on One Machine

This paper shows that even a very restricted version of the Economic Lot Scheduling Problem becomes NP-hard, and gives an implicit enumeration procedure for testing the feasibility of a schedule in which product i is set up I·i integer times per year.

Abstract

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.