| Queueing networks are used to model manufacturing systems, communication networks, and other such systems. Our special focus is on the problems of semiconductor manufacturing. The process flow in wafer fabs follows a "re-entrant" path where each lot of wafers returns several times to many stations.; Motivated by such re-entrant lines, as well as other manufacturing and communication networks, we obtain new linear programming performance bounds for queueing networks. They exploit the fact that for discrete-time Markov chains with translation invariant transition probabilities on polyhedra, an inequality relaxation of the average cost equation has a fixed form on such polyhedra. Proposing certain simple functions to serve as surrogates for the differential cost function allows for the development of linear programming performance bounds. The general theory is readily applicable to queueing networks operating under affine index policies, a class of scheduling policies subsuming many policies of interest. The approach allows for the natural development of functional bound linear programs, as well as for the incorporation of batch tools and setups---two features important in semiconductor manufacturing plants.; For open re-entrant lines, a baseline model for the study of semiconductor manufacturing plants, the new linear programming performance bounds we obtain are provably tighter than previous bounds for the class of buffer priority policies and the class of all nonidling policies. We also obtain new linear programming performance bounds for closed re-entrant networks which are provably tighter than previous bounds for the same classes of scheduling policies. In addition, for two-station closed re-entrant networks, we provide a counterexample to a conjectured form for the asymptotic loss via explicit solution of the equilibrium probability distribution.; We show how the performance bounds can be used to design wafer fabs. Specifically, one may formulate the problem as one of maximizing the performance subject to a capital cost constraint. Software has been developed both for performance bounds (called BoundFab) and for design (called DesignFab). |
