An Empirical Analysis on Queue Network Models of Production Techniques

Job shops are complex manufacturing systems which process a wide variety of products in low volumes. Two dominant characteristics of job shops are complex flows through the shop, and long queues of jobs in front of machines. It is not uncommon for a job to spend more than 90% of the time in the facility waiting for machines to become available. The challenge of managing day to day operations in this environment has stimulated an enormous interest in sequencing and scheduling problems. In comparison less attention has been paid to tactical and strategic problems such as choice of equipment, capacity planning, allocation of products to different plants, and determination of lead times. To properly address these issues we need models that provide good estimates of the medium to long term performance of manufacturing systems. Over the last two decades there has been a renewed interest in open queue network models, and major advances have been made in their (approximate) analysis. These studies were in part motivated by applications in manufacturing settings. In this paper we review open queue network models of job shops, with primary emphasis on models that facilitate the design of job-shop-like manufacturing systems. Open queue network models have been applied in many domains including computer science, communication engineering, and manufacturing and service operations, resulting in a large body of literature. Thus to provide an exhaustive review of the developments in the study of open queue networks is a task of a magnitude well beyond the scope of this paper. An attempt to provide such an overview will also be repetitious of excellent surveys done by Lemoine, Disney and Konig, and Buzacott and Yao. To minimize the overlap with these surveys we concentrate on recent developments in open queue network models that incorporate aspects such as general service times, and deterministic product routings, features that are common to manufacturing systems. With these features in place exact analysis has not been possible. However researchers have been very successful in developing good approximation procedures.

In what follows we describe a set of the problems associated with job shops, that are best addressed by queue network models. We partition the problems into three categories: strategic, tactical and operational problems.

1. STRATEGIC ISSUES :

One of the objectives of strategic planning is to identify long term goals of the company. To achieve these goals the strategic plan determines the resources that are to be utilized, and the policies that govern the use of these resources (Anthony 65). An important component of the strategic plan is the design of the manufacturing system. System design different plants,(iv) choice of location, and (v) design of the distribution systems. For the purpose on hand we restrict the scope of the design problem to the first three factors. The design of a plant is a major constraint under which the operating manager makes decisions. For instance, if several machine centers operate at or near their capacities and there is considerable diversity in the processing requirements of the products assigned to that plant, then queues at machine centers are likely to be very long and, more importantly, the variance of the time a job spends in the system is also likely to be very high. Among the primary tasks of the operating manager are to assign and predict completion times for jobs, control the flow of jobs through the facility, so that due dates are not violated, control the work-in-process inventory levels, respond to unanticipated loss of capacity due to factors such as uncertain yields and machine failures, and strive to improve the processes and products. Since most scheduling, sequencing and routing problems are known to be extremely difficult to solve the system should be designed so that simple real time control rules are adequate to obtain good performance. Clearly the performance of the system depends not only on the equipment selected, but also on the control rules employed to manage the day-to-day operations. However, since the system must be designed for the long term requirements of the firm, the design decisions are based on imprecise long term forecasts. The forecasts lack details in terms of the timing of the demand, and estimate demands for product families rather than individual products. Consequently at this level of decision making it may be adequate to assume that the shop is operated using very simple rules such as processing the jobs in the sequence in which they arrive at the machine center. This is a concern that the modeler must resolve in all strategic and tactical problems.

2. TACTICAL ISSUES :

The planning horizon for the tactical plan is shorter than the horizon for the strategic plan. The actual horizon length will depend on the specific problem being addressed. Since the horizon is shorter, the level of detail and the accuracy of the information available for tactical plans is higher. The level of uncertainty in the information is lower. Typically, managers responsible for the tactical plan are likely to report to those responsible for the strategic plan. As a result, the scope of the tactical plan may be restricted to one plant, and the capital that can be expended in acquiring machinery is significantly less than that considered by the strategic planners. Tactical plans are constrained to a large extent by the available physical assets, and the set of products that are produced in each plant can not be changed significantly. To simplify the discussion, and without acquire new machines nor change the set of products that are produced in the facility.

3. OPERATIONAL DECISIONS :

After determining the system design and making aggregate allocations of the resources, it is necessary to manage the day-to-day operations of the facility. The operational decisions, belonging to the lowest level of the hierarchy, must take into account the decisions made at the higher levels, and the current status of the facility. At this level there is very little opportunity to either increase the available productive resources, or change the mix of jobs to be processed during a time period. Typical decisions made at this level are: (i) the sequence of machine visitations for each job, that is the route the job will follow through the shop. (ii) the sequence in which the jobs are processed at each machine center, (iii) tracking of jobs through the facility, expediting, and releasing jobs into the facility. Thus at the operational level detailed sequencing and scheduling decisions are to be made so that orders are completed on time utilizing the resources available. The class of detailed scheduling and sequencing problems that arise in general job shops are extremely difficult to solve exactly. Hence several approximation procedures have been proposed. Readers are referred to Graves 81, Conway Maxwell and Miller 67, and references there in for details of these scheduling rules. The bulk of the scheduling literature assumes that the production environment is deterministic and static over a specified finite horizon. These environments have been called static job shops.

The study of networks of queues was initially motivated by applications in the telephone industry (Erlang 17). However the pursuit of these problems received a significant boost from two seminal papers by J.R. Jackson. Jackson's work interestingly, was motivated by job shops. Since the publications of those papers significant theoretical insights have been gained into the properties of queue networks. In particular, in the last two decades spurred by applications in computer science, telecommunications, and flexible manufacturing systems, there has been a flurry of activity in this area. Unfortunately exact analysis for open queue networks with finite number of servers

(1) Exponential service time distributions. (2) Service requirement at each station are independent of the product family. If the service times are allowed to depend on the product family then exact analysis is possible with a preemptive resume, last come first served discipline. (3) Priority discipline at each queue is independent of the product family. (4) Arrival process to the network is a Poisson process. For general job shops the assumptions underlying reversible networks are very restrictive. For instance work by Bitran and Tirupati suggests that the exponential distributions overstate the variability in the service times found in many manufacturing operations, and distributions with squared coefficient of variation (scv) less than one are more appropriate. Since exact analysis has not been possible when the assumption of exponential service times is relaxed, the focus has been on approximation procedures. The approximation schemes can be classified into four categories: decomposition methods, diffusion approximations, mean value analysis, and operational analysis. The procedure that has been employed with considerable success to analyze models of manufacturing systems is the decomposition approach. Only recently diffusion models have been utilized to study scheduling and operational control problems arising in manufacturing. Operational analysis has been applied primarily to computer system models, and mean value analysis is concerned with closed queue networks. Hence we will restrict our attention to the decomposition methods, and applications of diffusion models to manufacturing problems.

As stated several times in earlier sections, the actual performance of a system is inextricably linked to the control rules employed to operate the system. It is therefore tempting to require algorithms that determine optimal system configuration to simultaneously determine the optimal control policies. Such a monolithic approach has so far eluded analysis. Considerations such as the detailed data requirements of operational control rules also diminishes the practical appeal of the monolithic approach. The optimization procedures developed for open queue networks can be partitioned into two categories determine the optimal operational rules for an existing system. Given the bias of this paper our focus will be on the first set of models. In recent years based on the developments in the theory of dynamic control for Brownian networks, researchers have proposed control rules for job shops. The second part of this section contains a brief review of this literature. Optimal design of computer systems and communication networks based on queue network models have been studied for several years. Emergence of flexible manufacturing systems has also motivated developments in design of queue networks (Buzacott and Yao 86b). Much of this work is concerned with closed queue networks. It is only recently that open queue network models have been proposed for designing job shops (Bitran and Tirupati 89a,b). We now turn our attention to the second class of optimization problems that determine control rules for a predetermined system. Here the network layout, the product mix, throughputs, and capacities are predetermined. The objective of the optimization problem is to control the flow of jobs or customers through the system. Under the hierarchical framework developed in section III, the class of queueing problems discussed in this sub-section address operational problems. There is a large body literature concerning the optimal scheduling of multiclass queueing systems, where the scheduling decisions are to dynamically decide which class of customers to serve. Although the theory for single-station systems is well developed, no papers exist on the optimal scheduling of a multiclass queue network, which appears to be mathematically intractable by the standard semi-Markov decision process approach. However, Harrison has shown how to approximate a queuing network scheduling problem by a dynamic control problem for Brownian motion. This heavy traffic approximation assumes that each station in the network is busy the great majority of the time, and thus focuses on the bottleneck, or most heavily loaded stations in the network. Fortunately, this is where most of the congestion and queueing occurs, and where scheduling can have its biggest impact.

In this paper we reviewed manufacturing problems that can be modelled as open queue networks. Over the last decade three major developments have occurred in this area : (i) approximation techniques that provide good estimates of the performance of open queue networks with general service times and deterministic routings, (ii) empirical discovery that some of the optimal network design problems can be through networks using Brownian control models.

• Albin, S.L. (1981), "Approximating queues with superposition arrival processes, "PhD dissertation, Dept of IE and OR, Columbia University, New York.

• Avriel, M. (1976) Nonlinear Programming, Analyses and Methods, Prentice Hall, Englewood Cliffs, N.J.

• Berman, M. and M. Westcott(1983), " On queueing systems with renewal departure processes," Advances in Applied Probability, 15, 657-673.

• Bitran, G.R. and D. Sarkar (1990), "Throughput analysis in manufacturing networks," Working paper, Sloan School of Management, M.I.T.

• Chen, H., J.M. Harrison, A. Mandelbaum, A.A. Ackere and L.M. Wein (1988), "Empirical evaluation of a queueing network model for semiconductor wafer fabrication," 36, 202-215.

• Friedman, H.D. (1965) "Reduction methods for tandem queueing systems," Operations Research, 13, 121-131

• Garey, M.R., D.S. Johnson and R. Sethi (1976), "Complexity of flow shop and job shop scheduling algorithms," Operations Research, 24, 117 – 129

• Harrison, J.M. and L.M. Wein (1990a), "Scheduling networks of queues: Heavy traffic analysis of a simple open network," Queueing Systems, 5, 265-280.

• Kelly, F.P. (1975), "Networks of queues with customers of different types, " Journal of Applied Probability, 12, 542-554.

• Nemhauser, G.L. and L.A. Wolsey (1988), Integer and Combinatorial Optimization, John Wiley and sons, New York.

• Page, E. (1972), Queueing Theory in O.R., Operational Research Series, Edited by K.B.Haley

 Wein, L.M. (1990a), " Capacity allocation in Generalized Jackson Networks," Operations Research Letters, 8, 143-146.