On Real-time Scheduling Policies for Flexible Manufacturing Systems

We consider a model recently proposed by Perkins and Kumar for real-time control of flexible manufacturing systems. In this model, a machine can process a finite number of part types at specified rates, but only one part type can be processed at any given time. To process multiple part types the machine uses a feedback rule to switch, from time to time, from one part type to another. Such switches incur a setup time of δ time units during which no parts are processed. By introducing the notion of idling, we derive a new lower bound on the performance, as measured by average buffer size, of any stable feedback scheduling policy for a single machine.