Partial Pooling in Tandem Lines with Cooperation and Blocking

For a tandem line of finite, single-server queues operating under the production blocking mechanism, we study the effects of pooling several adjacent stations and the associated servers into a single station with a single team of servers. We assume that the servers are cross-trained (so that they can work at several different stations) and that two or more servers can cooperate on the same job. For such a system, we provide sufficient conditions on the service times and sizes of the input and output buffers at the pooled station under which pooling will decrease the departure time of each job from the system (and hence increase the system throughput). We also show that pooling decreases the total number of jobs in the system at any given time and the sojourn time of each job in the system if the departure time of each job from the system is decreased by pooling and there is an arrival stream at the first station. Moreover, we provide sufficient conditions under which pooling will improve the holding cost of each job in the system incurred before any given time, and extend our results to closed tandem lines and to queueing networks with either a more general blocking mechanism or probabilistic routing. Finally, we present a numerical study aimed at quantifying the improvements in system performance obtained through pooling and at understanding which stations should be pooled to achieve the maximum benefit. Our results suggest that the improvements gained by pooling may be substantial and that the bottleneck station should be among the pooled stations in order to obtain the greatest benefit. AMS subject classification: 90B22     

Pooling in tandem queueing networks with non-collaborative servers

This paper considers pooling several adjacent stations in a tandem network of single-server stations with finite buffers. When stations are pooled, we assume that the tasks at those stations are pooled but the servers are not. More specifically, each server at the pooled station picks a job from the incoming buffer of the pooled station and conducts all tasks required for that job at the pooled station before that job is placed in the outgoing buffer. For such a system, we provide sufficient conditions on the buffer capacities and service times under which pooling increases the system throughput by means of sample-path comparisons. Our numerical results suggest that pooling in a tandem line generally improves the system throughput—substantially in many cases. Finally, our analytical and numerical results suggest that pooling servers in addition to tasks results in even larger throughput when service rates are additive and the two systems have the same total number of storage spaces.     

An Operational Research Approach to Allocation of Clients to a Certain Class of Service Institutions

A model is developed to explain the allocation of clients to different locations of a certain class of service institutions. It can be used for all types of allocation-problems which have the features: clients are travelling from their home locations to the service places. They can choose among several locations of the institution all of which offer the same services. The clients need constant travelling times or costs, and they cause different waiting times or costs at each location, which are a function of the number of clients choosing that service station. The objective of the individual client is to minimize the total time or cost required.Since exact alogrithms cannot be used because of the large number of variables and the non-linearity of the problem, a special approximation algorithm is developed.The paper presents the results of a study concerning the allocation of cars, which must periodically be checked for traffic safety at official test stations.     

The multiple server effect: Optimal allocation of servers to stations with different service‐time distributions in tandem queueing networks

Traditionally, studies on tandem queueing networks concentrate on systems with infinite buffers, exponential service times, and/or single servers where solutions are more tractable. Less research can be found on more general, less tractable systems. We examine multipleserver systems with finite buffers and nonexponential service times, studying the effects of coefficient of variation (cv) of the servicetime distribution on the throughput of these systems, where cv differs among stations.Starting with the single station, we examine the effects of cv and the number of servers at the station on the distribution of interdeparture times. This insight helps explain the differences in throughput seen in the single (fast) server vs. multiple (slow) server problem. These results, in turn, shed light on the server allocation problem when cv differs among stations. We present some observations, as well as the intuition behind them.     

Order restoration in queues

We examine a class of problems in queueing networks which arise when customers enter a bank of parallel servers in a given order and lose their place in the sequence due to passing resulting from variations in service times. The original sequence is required before service can take place at the next station in the network. These problems arise naturally in flexible manufacturing systems. The result is that the next station beyond the parallel bank of servers can be approximated by a non-Markovian bulk arrival system. This station sees batch arrivals of customers that are eligible to receive service. The size of the arriving batches is shown to depend on the inter-arrival times. Several fundamental results are established for this class of problems including the distribution of batch inter-arrival times, batch sizes, and an approximate method for determining the distribution of the number of eligible and an exact method for determining the distribution of the number of ineligible customers in the system.     

A multi-objective lead time control problem in multi-stage assembly systems using genetic algorithms

In this paper, we develop a multi-objective model to optimally control the lead time of a multi-stage assembly system, using genetic algorithms. The multi-stage assembly system is modelled as an open queueing network. It is assumed that the product order arrives according to a Poisson process. In each service station, there is either one or infinite number of servers (machines) with exponentially distributed processing time, in which the service rate (capacity) is controllable. The optimal service control is decided at the beginning of the time horizon. The transport times between the service stations are independent random variables with generalized Erlang distributions. The problem is formulated as a multi-objective optimal control problem that involves four conflicting objective functions. The objective functions are the total operating costs of the system per period (to be minimized), the average lead time (min), the variance of the lead time (min) and the probability that the manufacturing lead time does not exceed a certain threshold (max). Finally, we apply a genetic algorithm with double strings using continuous relaxation based on reference solution updating (GADSCRRSU) to solve this multi-objective problem, using goal attainment formulation. The results are also compared against the results of a discrete-time approximation technique to show the efficiency of the proposed genetic algorithm approach.     

Hybrid approaches to optimize mixed-model assembly lines in low-volume manufacturing

In this paper, a production planning problem for mixed-model assembly lines in low-volume manufacturing as can be found in aircraft manufacturing is considered. This type of manufacturing is labor-intensive. Low-volume production of huge-sized jobs, i.e. airplanes, is typical. Balancing labor costs and inventory holding costs assuming a given job sequence is the purpose of this paper. Therefore, worker assignments to each station and start times and processing times for each job on each station are determined. Two different mathematical models are proposed. The first formulation is a time-indexed linear formulation that allows for a flexible allocation of workers to periods and stations while the second one has a non-linear objective function and allows only for a fixed assignment of workers to stations. It is proven that the second formulation leads to a linear program with continuous decision variables if the values of the decision variables that determine the number of workers assigned to a station are given, while the first formulation contains even in this situation binary decision variables. Heuristics that hybridize the mathematical formulations with variable neighborhood search techniques are proposed. Computational experiments on randomly generated problem instances and on real-world instances demonstrate the high performance of the heuristics.     

Consolidating or non-consolidating queues: A game theoretic queueing model with holding costs

We consider a two-server queueing system in which the servers choose their service rate based on the demand and holding cost allocation scheme offered by the demand generating entity. We provide an optimal holding cost allocation scheme that leads to the maximum possible service rate for each of a pooled and a split system. Our results suggest that careful allocation of holding costs can create incentives that enable minimum turnaround times using a common queue.     

Optimal assignment of servers to tasks when collaboration is inefficient

Consider a Markovian system of two stations in tandem with finite intermediate buffer and two servers. The servers are heterogeneous, flexible, and more efficient when they work on their own than when they collaborate. We determine how the servers should be assigned dynamically to the stations with the goal of maximizing the system throughput. We show that the optimal policy depends on whether or not one server is dominant (i.e., faster at both stations) and on the magnitude of the efficiency loss of collaborating servers. In particular, if one server is dominant then he must divide his time between the two stations, and we identify the threshold policy the dominant server should use; otherwise each server should focus on the station where he is the faster server. In all cases, servers only collaborate to avoid idleness when the first station is blocked or the second station is starved, and we determine when collaboration is preferable to idleness as a function of the efficiency loss of collaborating servers.     

Approximate analysis of exponential tandem queues with blocking

In this paper, an approximate method for the analysis of open networks of queues in tandem and with blocking is proposed. The network consists of M single server queuing stations with exogenous Poisson arrival processes and exponentially distributed service times. The analysis is based on the method of decomposition where the total network is broken down into queues which are analyzed as M/C₂/1/N queues assuming Poisson arrival and departure processes to find the steady-state probabilities of the number of customers at each station. The procudure reduces the problem to a number of elementary operations which can be performed efficiently with the aid of a computer. We also compare different definitions of blocking. Numerical results are given to demonstrate the accuracy of the new method.     

Exploiting locality: approximating sorting buffers

The sorting buffers problem is motivated by many applications in manufacturing processes and computer science, among them car-painting and file servers architecture. The input is a sequence of items of various types. All the items must be processed, one by one, by a service station. We are given a random-access sorting buffer with a limited capacity. Whenever a new item arrives it may be moved directly to the service station or stored in the buffer. Also, at any time items can be removed from the buffer and assigned to the service station. Our goal is to give the service station a sequence of items with minimum type transitions. We generalize the problem to allow items with different sizes and type transitions with different costs. We give a polynomial-time 9-approximation algorithm for the maximization variant of this problem, which improves the best previously known 20-approximation algorithm.     

Scheduling networks of queues: Heavy traffic analysis of a simple open network

We consider a queueing network with two single-server stations and two types of customers. Customers of type A require service only at station 1 and customers of type B require service first at station 1 and then at station 2. Each server has a different general service time distribution, and each customer type has a different general interarrival time distribution. The problem is to find a dynamic sequencing policy at station 1 that minimizes the long-run average expected number of customers in the system.The scheduling problem is approximated by a dynamic control problem involving Brownian motion. A reformulation of this control problem is solved, and the solution is interpreted in terms of the queueing system in order to obtain an effective sequencing policy. Also, a pathwise lower bound (for any sequencing policy) is obtained for the total number of customers in the network. We show via simulation that the relative difference between the performance of the proposed policy and the pathwise lower bound becomes small as the load on the network is increased toward the heavy traffic limit.     

Optimal Sequencing of Servers in the Two-Station Series Queueing System

This paper deals with determining an optimal sequence of service stations in a series queueing system. Optimality is defined in terms of the total time spent waiting for service. Sequences are compared on the basis of the moments of their steady-state total waiting time. In addition, the rules of stochastic dominance are applied which allow comparison of sequences on the basis of their waiting time distributions. Analytical results in the sequencing of service stations in series queues have been limited to stations with constant or exponential service times. This study extends the investigation to service distributions with varying degrees of statistical regularity given by the family of Erlang distributions.Relationships are developed for predicting optimal sequences. Validation is accomplished by simulating a number of systems and comparing the waiting time distribution functions for each sequence. The relationships are shown to be good predictors and useful in the study and design of systems of servers in series.     

Performance analysis of a constrained resource sharing system

We consider a queueing system where the servers are arranged in a circle, and each arriving customer requires a pair of resources that is shared by its server with the respective neighbors on either side. If either resource is being used, the customer is denied service. Customers arrive at each server according to independent Poisson processes, and lengths of service times at each server have an exponential distribution. We derive a closed-form formula for the expected fraction of busy servers at any time in terms of the number of servers and the utilization factor (defined as the arrival rate times the mean service-time duration). This allows us to evaluate system performance when these parameters are varied, and to determine whether denying service to arrivals at alternate servers improves performance. We relate the system to Dijkstra's dining philosophers problem, which is an abstraction for resource sharing in an operating system. This revised version was published online in June 2006 with corrections to the Cover Date.     

Heavy-traffic limits for an infinite-server fork–join queueing system with dependent and disruptive services

We study an infinite-server fork–join queueing system with dependent services, which experiences alternating renewal service disruptions. Jobs are forked into a fixed number of parallel tasks upon arrival and processed at the corresponding parallel service stations with multiple servers. Synchronization of a job occurs when its parallel tasks are completed, i.e., non-exchangeable. Service times of the parallel tasks of each job can be correlated, having a general continuous joint distribution function, and moreover, the service vectors of consecutive jobs form a stationary dependent sequence satisfying the strong mixing (\(\alpha \)-mixing) condition. The system experiences renewal alternating service disruptions with up and down periods. In each up period, the system operates normally, but in each down period, jobs continue to enter the system, while all the servers will stop working, and services received will be conserved and resume at the beginning of the next up period. We study the impact of both the dependence among service times and these down times upon the service dynamics, the unsynchronized queueing dynamics, and the synchronized process, assuming that the down times are asymptotically negligible. We prove FWLLN and FCLT for these processes, where the limit processes in the FCLT possess a stochastic decomposition property and the convergence requires the Skorohod \(M_1\) topology.     

The price of anarchy in an exponential multi-server

We consider two criteria for routing selection in a multi-server service station: the equilibrium and social optimization. The ratio between the average mean waiting times in these two routings is called the price of anarchy (PoA). We show that the worst-case PoA is precisely the number of servers.     

Optimal resource allocation for multiqueue systems with a shared server pool

We study optimal allocation of servers for a system with multiple service facilities and with a shared pool of servers. Each service facility poses a constraint on the maximum expected sojourn time of a job. A central decision maker can dynamically allocate servers to each facility, where adding more servers results in faster processing speeds but against higher utilization costs. The objective is to dynamically allocate the servers over the different facilities such that the sojourn-time constraints are met at minimal costs. This situation occurs frequently in practice, for example, in Grid systems for real-time image processing (iris scans, fingerprints). We model this problem as a Markov decision process and derive structural properties of the relative value function. These properties, which are hard to derive for multidimensional systems, give a full characterization of the optimal policy. We demonstrate the effectiveness of these policies by extensive numerical experiments.     

Approximation of throughput in tandem queues with multiple servers and blocking

In this paper, we develop an approximation method for throughput in tandem queues with multiple independent reliable servers at each stage and finite buffers between service stations. We consider the blocking after service (BAS) blocking protocol of each service stage. The service time distribution of each server is exponential. The approximation is based on the decomposition of the system into a set of coupled subsystems which are modeled by two-stage tandem queue with two buffers and are analyzed by using the level dependent quasi-birth-and-death (LDQBD) process.     

On the Introduction of an Agile, Temporary Workforce into a Tandem Queueing System

We consider a two-station tandem queueing system where customers arrive according to a Poisson process and must receive service at both stations before leaving the system. Neither queue is equipped with dedicated servers. Instead, we consider three scenarios for the fluctuations of workforce level. In the first, a decision-maker can increase and decrease the capacity as is deemed appropriate; the unrestricted case. In the other two cases, workers arrive randomly and can be rejected or allocated to either station. In one case the number of workers can then be reduced (the controlled capacity reduction case). In the other they leave randomly (the uncontrolled capacity reduction case). All servers are capable of working collaboratively on a single job and can work at either station as long as they remain in the system. We show in each scenario that all workers should be allocated to one queue or the other (never split between queues) and that they should serve exhaustively at one of the queues depending on the direction of an inequality. This extends previous studies on flexible systems to the case where the capacity varies over time. We then show in the unrestricted case that the optimal number of workers to have in the system is non-decreasing in the number of customers in either queue. AMS subject classification: 90B22, 90B36     

Location–Allocation of Multiple-Server Service Centers with Constrained Queues or Waiting Times

Recently, the authors have formulated new models for the location of congested facilities, so to maximize population covered by service with short queues or waiting time. In this paper, we present an extension of these models, which seeks to cover all population and includes server allocation to the facilities. This new model is intended for the design of service networks, including health and EMS services, banking or distributed ticket-selling services. As opposed to the previous Maximal Covering model, the model presented here is a Set Covering formulation, which locates the least number of facilities and allocates the minimum number of servers (clerks, tellers, machines) to them, so to minimize queuing effects. For a better understanding, a first model is presented, in which the number of servers allocated to each facility is fixed. We then formulate a Location Set Covering model with a variable (optimal) number of servers per service center (or facility). A new heuristic, with good performance on a 55-node network, is developed and tested.