The Multiproduct Lot Scheduling Problem

Abstract

An NP-hard problem of considerable practical interest is the multi-product lot scheduling problem. In its simplest form there are P products to be scheduled on a single machine over a finite interval (0, T). Associated with each product i is a demand schedule D_t , a per unit time holding cost h_t , and a changeover cost vector c_ji which is the cost of starting production on i if the machine previously produced product j. In practical problems one might wish to treat the D_t as random variables, although this feature is typically disregarded by solution procedures. Example situations might be a television manufacturer who produces several different styles and sizes of televisions on a single line or a chemical processor who produces several different chemicals in batches on a single expensive machine. We briefly summarize previous approaches to this problem starting with the work of Manne, Dzielinski, Gomory, Lasdon and Terjung and then analyze LP-like approximations to this model and provide bounds on the closeness of the LP solution to the exact IP solution as the problem size gets large.