Abstract
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.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
S.C. Graves, A review of production scheduling, Math. Oper. Res. 29 (1981) 646–675.
F. Baskett, K.M. Chandy, R.R. Muntz and F.G. Palacios, Open, closed and mixed networks of queues with different classes of customers, J. ACM 22 (1975) 248–260.
F.P. Kelly,Reversibility and Stochastic Networks (Wiley, New York, 1979).
S. Lippman, Applying a new device in the optimization of exponential queueing systems, Math. Oper. Res. 23 (1975) 687–710.
S.P. Meyn, private communication (1991).
S.P. Meyn and D. Down, Stability of generalized Jackson networks, submitted for publication (1991).
R. Weber, P. Varaiya and J. Walrand, Scheduling jobs with stochastically ordered processing times on parallel machines to minimize expected flowtime, J. Appl. Prob. 23 (1986) 841–847.
G.P. Klimov, Time-sharing service systems I, Theory Prob. Appl. 19 (1974) 532–551.
G.P. Klimov, Time-sharing service systems II, Theory Prob. Appl. 23 (1978) 314–321.
T.L. Lai and Z. Ying, Open bandit processes and optimal scheduling of queueing networks, Tech. Rep., Stanford University (1989).
B. Simon, Priority queues with feedback, J. ACM 31 (1984) 134–149.
R.L. Cruz, A calculus for network delay, part I: Network elements in isolation, IEEE Trans. Inf. Theory IT-37 (1991) 114–131.
S.H. Lu and P.R. Kumar, Distributed scheduling based on due dates and buffer priorities, IEEE Trans. Auto. Control AC-36 (1991) 1406–1416.
Z.B. Tang and L.Y. Shi, Note on distributed scheduling based on due dates and buffer priorities, by S. Lu and P.R. Kumar, Preprint (1991).
A.P.J. Vepsalainen and T.E. Morton, Improving local priority rules with global lead-time estimates: A simulation study, J. Manuf. Oper. Manag., 1 (1988) 102–118.
K.R. Baker, Sequencing rules and due-date assignments in a job shop, Manag. Sci. 30 (1984) 1093–1104.
S.H. Lu and P.R. Kumar, Control policies for scheduling of semiconductor manufacturing plants, in:Proc. 1992 American Control Conf. (June 1992), to appear.
L.M. Wein, Scheduling networks of queues: Heavy traffic analysis of a multistation network with controllable inputs, Preprint (June 1989).
L.M. Wein, Reducing the variance of sojourn times in multi-class queueing systems, Preprint (November 1989).
J. Kimemia and S.B. Gershwin, An algorithm for the computer control of a flexible manufacturing system, IIETrans. 15 (1983) 353–362.
R. Akella and P.R. Kumar, Optimal control of production rate in a failure prone manufacturing system, IEEE Trans. Auto. Control AC-31 (1986) 116–126.
T. Bielecki and P.R. Kumar, Optimality of zero-inventory policies for unreliable manufacturing systems, Oper. Res. 36 (1988) 532–541.
A. Sharifnia, Production control of a manufacturing system with multiple machine states, IEEE Trans. Auto. Control AC-33 (1988) 600–626.
J. Lehoczky, S. Sethi, H.M. Soner and M. Taksar, An asymptotic analysis of hierarchical control of manufacturing systems under uncertainty, Math. Oper. Res. (1990), to appear.
D. Mitra, Stochastic theory of a fluid model of producers and consumers coupled by a buffer, Adv. Appl. Prob. 20 (1988) 646–676.
H. Chen and D.D. Yao, A fluid model for systems with random disruptions, Preprint (1990).
J. Lim, S.M. Meerkov and F. Top, Homogeneous asymptotically reliable serial production lines: Theory and a case study, IEEE Trans. Auto. Control AC-35 (1990) 524–534.
B.A. Sevastyanov, Influence of storage bin capacity on the standstill time of a production line, Theory Prob. Appl. 7 (1962) 429–438.
J. Lim, S.M. Meerkov and F. Top, Analysis and synthesis of asynchronous asymptotically reliable, asymptotically controllable serial production lines, in:Proc. 28th Conf. on Decision and Control, Tampa, FL, vol. 1 (1989) pp. 60–64.
C. Lozinski and C.R. Glassey, Bottleneck starvation indicators for shop floor control, IEEE Trans. Semicond. Manuf. SM-1 (1988) 147–153.
S.B. Gershwin, Stochastic scheduling and setups in manufacturing systems, in:Proc. 2nd ORSA/TIMS Conf. on Flexible Manufacturing Systems: Operations Research Models and Applications, ed. K.E. Stecke (Elsevier, Amsterdam, 1986) pp. 431–442.
S. Elmaghraby, The economic lot scheduling problem (ELSP): Review and extensions, Manag. Sci. 24 (1978) 587–598.
J.R. Perkins and P.R. Kumar, Stable distributed real-time scheduling of flexible manufacturing/assembly/disassembly systems, IEEE Trans. Auto. Control AC-34 (1989) 139–148.
C.J. Chase and P.J. Ramadge, On the real time control of flexible manufacturing systems, in:Proc. 28th Conf. on Decision and Control, Tampa, FL (1989) pp. 2026–2027.
P.R. Kumar and T.I. Seidman, Dynamic instabilities and stabilization methods in distributed real-time scheduling of manufacturing systems, IEEE Trans. Auto. Control AC-35 (1990) 289–298.
C. Chase, Manufacturing networks and stability, Preprint (1989).
C. Humes Jr., A naive stabilization schema: Kumar-Seidman revisited, Preprint, Instituto de Matimatica et Estatistica-Universidade de S. Paulo, S. Paulo, Brazil (December 1990).
Author information
Authors and Affiliations
Additional information
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.
Rights and permissions
About this article
Cite this article
Kumar, P.R. Re-entrant lines. Queueing Syst 13, 87–110 (1993). https://doi.org/10.1007/BF01158930
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01158930