This paper surveys applications of queueing theory for semiconductor manufacturing systems (SMSs). Due to sophisticated tool specifications and process flows in semiconductor manufacturing, queueing models can be very complicated. Research efforts have been on the improvement of model assumptions and model input, mainly in the first moment (averages) and the second moment (variations). However, practices show that implementation of classical queueing theory in semiconductor industry has been unsatisfactory. In this paper, open problems on queueing modeling of SMS are discussed. A potential solution is also proposed by relaxing the independent assumptions in the classical queueing theory. Cycle time reduction has constantly been a key focus of semiconductor manufacturing. Compared with simulation, queueing theory-based analytical modeling is much faster in estimating manufacturing system performance and providing more insights for performance improvement. Therefore, queueing modeling attracts generous semiconductor research grants. Unfortunately, existing queueing models focus on simple extensions of the classical queueing theory and fail to question its applicability to the complicated SMS. Hence, related researches have not been employed widely in the semiconductor industry. In this paper, we conduct a survey on the important works and also present some open problems. We also propose a novel solution by relaxing a key assumption in the classical queueing theory. We are currently funded by Intel to explore this potential solution, and we hope it can foster an interesting research field for the years to come.

The 11 papers in this special issue focus on e-manufacturing in the semiconductor industry.

We propose a novel directory scheme for a large federation of databases where object migration is in response to manufacturing events. In our directory scheme, objects report their location to a directory server instead of the traditional method of the directory servers polling sites in the network. The directory is distributed among multiple servers to avoid bottlenecks during query processing. A distributed linear hashing algorithm is proposed for efficiently determining an appropriate server for an object. Finally, a stochastic dynamic programming model is proposed for minimizing the number of database transactions.

The polynomiality of nonlinear separable convex (concave) optimization problems, on linear constraints with a matrix with “small” subdeterminants, and the polynomiality of such integer problems, provided the inteter linear version of such problems ins polynomial, is proven. This paper presents a general-purpose algorithm for converting procedures that solves linear programming problems. The conversion is polynomial for constraint matrices with polynomially bounded subdeterminants. Among the important corollaries of the algorithm is the extension of the polynomial solvability of integer linear programming problems with totally unimodular constraint matrix, to integer-separable convex programming. An algorithm for finding a ε-accurate optimal continuous solution to the nonlinear problem that is polynomial in log(1/ε) and the input size and the largest subdeterminant of the constraint matrix is also presented. These developments are based on proximity results between the continuous and integral optimal solutions for problems with any nonlinear separable convex objective function. The practical feature of our algorithm is that is does not demand an explicit representation of the nonlinear function, only a polynomial number of function evaluations on a prespecified grid.

A flexible machine that processes a set of different part types is considered. Each part type has its own Poisson arrival process, general processing requirement, and a given delay (flow time) constraint. The problem is to find an optimal control that schedules the machine among the part types on a real-time basis in order to minimize a cost function of the flow times and meet all the constraints. The cost function is quite general, and it requires only that the marginal costs can be ordered among the part types. Based on polymatroid theory, an optimal control is identified that partitions the part types into several groups and applies a priority rule among the groups. Within each group, the optimal control is an appropriate randomization among priority rules. An efficient algorithm is developed to characterize the optimal control completely.>

The authors have developed and applied probabilistic tools to establish second-order stochastic properties such as convexity and concavity in the optimal design and control of queueing systems. Their approaches are based on constructing and comparing the dynamical sample paths of the stochastic processes under study. They present a tutorial on these notions and results in stochastic convexity/concavity. Many examples are discussed to illustrate the application of the results in parametric optimization of queues and queueing networks.>

Considered is a set of manufacturing cells that are jointly setup for production. Each cell is capable of producing a specific type of part family and periodically a joint setup is performed at each of these cells for production. We model the production process of each cell by a self-exciting point process. Using some structural properties of this process, an efficient algorithm is developed to obtain the optimal run quantity and the inter-setup time.

Discrete-time analysis of two schemes for multiplexing voice and data is presented. In each scheme voice and data are multiplexed using the movable boundary frame allocation scheme. In the first scheme, speech activity detectors (SAD's) are not used, and hence, the variations in the voice traffic are only due to the on/off characteristics of voice. In the second scheme, SAD's are employed so that talker silences can he utilized for transmission of additional voice and/or data. In this scheme, the multiplexer performs digital speech interpolation as well as movable boundary frame allocation. The performance measures considered are probability of loss for voice calls, probability of speech clipping, speech packet rejection ratio, and the expected data message delay. In the case of the multiplexer with SAD, a tradeoff exists between data message delay and speech interpolation advantage. Some numerical examples are presented which illustrate the performance of the two multiplexers.

Heines1recently analyzed the buffer behavior in computer communication system under: 1) Poisson arrivals, 2) periodic opportunities for service, 3) random blocking of service, and 4) averaging queue length and delay time observed at customer departure times. Heines' analysis revealed a different result to that of Hsu's [1]. This is because the probability distribution of the buffer content derived by Hsu corresponds to the epochs of "end of service intervals," while that in Heines' corresponds to the buffer content just after a customer departure. Using a (recently introduced) discrete state level crossing analysis [2], Heines' result can be derived from that of Hsu's. The intent of this letter, however, is to point out an alternate viewpoint of this model and to relate Heines' result to some previously published results. It was observed by Heines that if a data packet arrives when the system is idle, service to this data packet may be attempted only at the end of that service interval. This phenomenon may be interpreted as follows: every time the buffer becomes empty the output channel is closed for a length of a slot time. If no data packet arrives during this slot time, the channel is once again closed down for the following slot time. This is continued until at least one data packet arrives. Then the channel will be opened for service at the end of the slot time following the data packet arrival. This model is indeed an M/G/1 queue with geometric service times and "multiple server vacations." The results for this M/G/1 are easily obtained from that of Welch's [3] and are available in [4] and [5]. Using a straightforward translation of the results in [4] and [5] we get the Laplace Stieltjes transform W(s) of the waiting time distribution for this model as (see [6])$\tilde{W}(s) = {(f-\lambda) \exp (-s) (1- \exp (-s)) \over (\lambda - s + sf) \exp (-s)-(\lambda - s)}, \quad Re(s) > 0$where f = Pr {channel available during a slot time} and λ is the data packet arrival rate. Now one may use this viewpoint of this model and the level crossing analysis discussed in [5] to extent this model to accomodate bulk arrival with multitype of customers.

A discrete buffered system with infinite buffer size, multiple Poisson arrival streams, priority service, and random server interruptions is considered. The queueing times of the data packets of different priority classes are derived using the concepts of delayed busy cycle and level crossing analysis. The results of this study can be used as a guidelines for the buffer design in digital systems.