The Dynamic Line Allocation Problem

Consider a plant that has information about the arrival schedule of its "inputs" over a planning cycle. The plant has parallel production lines for processing multiple types of products. However, changeover cost and changeover time are incurred when a line changes from processing one type of products to a different type of products. We present a dynamic line allocation problem that determines an optimal line allocation so that the total relevant cost (changeover and waiting costs) is minimized. In this paper we analyze the complexity of the problem and develop three different heuristics for generating near-optimal allocations.