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

摘要

Manufacturing systems consisting of many machines and producingmany types of parts are considered. Each part type requires processingfor a specified length of time at each machine in a prescribed sequenceof machines. Machines may require a setup time when changing betweenpart types, and parts may incur a variable transportation delay whenmoving between machines. The goal is to schedule all the machinesdynamically so that all the part types are produced at the desired rateswhile maintaining bounded buffer sizes at all machines. A previouslyopen problem is resolved by exhibiting the instability of all clearingpolicies for some nonacyclic manufacturing systems. Surprisingly, suchinstabilities can occur even when all setup times are identically zero,and they are induced purely by starvation of machines. Sufficientconditions on the system topology and processing and demand rates whichensure the stability of distributed clear-a-fraction policies are shown.A general distributed supervisory mechanism which will stabilize anypolicy is studied