Dynamic instabilities and stabilization methods in distributed real-time scheduling of manufacturing systems Academic Article uri icon

abstract

  • We consider manufacturing systems consisting of many machines 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 setup 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 all the part-types are produced at the desired rates while maintaining bounded buffer sizes at all machines. In this paper we 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. We examine the consequences of this interaction for the stability properties of the manufacturing system in terms of maintaining bounded buffer levels. First, we 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 setup times are identically zero, and they are induced purely by starvation of machines. Simultaneously, however, there can exist certain exact sets of initial conditions for which a delicate stability does hold; however, it may not be robust. Second, we 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, we study general supervisory mechanisms 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. © 1990 IEEE

altmetric score

  • 3

author list (cited authors)

  • Kumar, P. R., & Seidman, T. I

citation count

  • 236

complete list of authors

  • Kumar, PR||Seidman, TI

publication date

  • March 1990