Decomposition for scheduling flexible manufacturing systems

In some flexible manufacturing systems, tool magazine capacity naturally divides parts into families so that substantial setups occur only when switching production between families. For this situation (positive setup times and costs only between families), the authors show that the production planning problem decomposes into two simpler problems: an aggregate scheduling problem, and a disaggregation. First, they derive a disaggregation that determines the optimal intrafamily product schedules corresponding to a given family schedule in polynomial time. Second, the authors show how to aggregate so that the decomposition maintains optimality for family schedules satisfying the property that production does not begin until inventory is zero (the Zero-Switch rule).