Dynamic instabilities and stabilization methods in distributed real-time scheduling of manufacturing systems

The authors consider manufacturing systems consisting of many macnines and producing many types of parts. Each part-type requires processing for a specified length of time at each machine in a prescribed sequence of machines. Machines may require a set-up time when changing between part-types, and parts may incur a variable transportation delay when moving between machines. The goal is to dynamically schedule all the machines so that the part-types are produced at the desired rates while maintaining bounded buffer sizes at all machines. In this paper the authors study the interaction of two types of feedbacks, one caused by ‘cycles’ of material flow in nonacyclic manufacturing systems, and the other introduced by the employment of closed-loop scheduling algorithms. They examine the consequences of this interaction for the stability properties of the manufacturing system in terms of maintaining bounded buffer work levels. First, the authors resolve a previously open problem by exhibiting the instability of all ‘clearing policies’ for some nonacyclic manufacturing systems. Surprisingly, such instabilities can occur even when all set-up times are identically zero, and they are induced purely by starvation of machines. Simultanoeusly, however, there can exist certain exact sets of initial conditions for which a delicate stability does hold; however, it may not be robust. Second, the authors exhibit sufficient conditions on the system topology and processing and demand rates which ensure the stability of distributed clear-a-fraction policies. These conditions are easy to verify. Third, the authors study general supervisory machines which will stabilize any policy. One such universal stabilization mechanism requires only a supervisory level which truncates all excessively long production runs of any part-type, and maintains a separate priority queue for all part-types with large buffer levels. It is easily implementable in a distributed fashion at the machine, and the level of supervisory intervention can also be adjusted as desired.