DISTRIBUTED SCHEDULING BASED ON DUE DATES AND BUFFER PRIORITIES

We are motivated by the problem of scheduling a large semiconductor manufacturing facility, where jobs of wafers, each with a desired due date, follow essentially the same route through the manufacturing system, returning several times to many of the service centers for the processing of successive layers. Neglecting the randomness introduced by yield, such a system can be modeled as a nonacyclic flow line. In such systems, it is important to reduce the mean delay, or equivalently the mean work-in-process, as well as the variance of the delay. We analyze several distributed scheduling policies. We show that for a single nonacyclic flow line the first buffer first serve policy (FBFS), which assigns priorities to buffers in the order that they are visited, is stable, whenever the arrival rate, allowing for some burstiness, is less than the system capacity. Similarly, the last buffer first serve policy (LBFS), where the priority ordering is reversed, is also stable. However, not all buffer priority policies are stable, as witnessed by a counterexample. The well known earliest due date policy (EDD), where priority is based on the due date of a part, as well as another due date based policy of interest called the least slack policy (LS), where priority is based on the "slack" of a part, defined as the due date minus an estimate of the remaining delay, are also proved to be stable. For systems with many part types following different routes, we exhibit stable extensions of these policies. We also present simulations which confirm our intuition that LBFS may well be the best policy for minimizing the mean delay at high load factors, while LS may well be the best policy for minimizing the variance of the delay. Finally, some open problems are posed.