Re-entrant lines

Traditionally, manufacturing systems have mainly been treated as either job shops or flow shops. In job shops, parts may arrive with random routes, with each route having a low volume. In flow shops, the routes are fixed and acyclic, as in assembly lines. With the advent of semiconductor manufacturing plants, and more recently, thin film lines, this dichotomy needs to be expanded to consider another class of systems, which we call re-entrant lines. The distinguishing feature of these manufacturing systems is that parts visit some machines more than once at different stages of processing.Scheduling problems arise because several parts at different stages of processing may be in contention with each other for service at the same machine. There may be uncertainties in the form of random service or set-up times, as well as random machine failures and repairs. The goal of scheduling is to improve performance measures such as mean sojourn time in the system, which is also known as the mean cycle-time, or the variance of the cycle-time.In this paper we provide a tutorial account of some recent results in this field. We describe several scheduling policies of interest, and provide some results concerning their stability and performance. Several open problems are suggested.The research reported here has been partially supported by the National Science Foundation under Grant No. ECS-90-25007, and the Joint Services Electronics Program under Contract No. N00014-84-C-0149.