Locating an n-server facility in a stochastic environment

We consider a demand-responsive service system in which n mobile units (servers) are garaged at one facility. Service demands arrive in time as a homogenous Poisson process, but are located over the service region according to an arbitrary probability law. Given a random service demand, either (1) a mobile unit is dispatched to the demand's location to provide on-scene service or (2) the demand is lost (i.e. it is handled by some back-up system). The resultant queueing system is an M/G/n loss system operating in steady state. The objective is to locate the garage facility so that the average cost of response is minimized, where the cost of response is a weighted sum of mean travel time to a random serviced demand and the cost of a lost demand, the weights being the respective probabilities of occurrence. We show that the optimum facility location reduces to Hakimi's well-known minisum location.     

Optimal NT policies for M/G/1 system with a startup and unreliable server

This paper studies the control policies of an M/G/1 queueing system with a startup and unreliable server, in which the length of the vacation period is controlled either by the number of arrivals during the idle period, or by a timer. After all the customers are served in the queue exhaustively, the server immediately takes a vacation and operates two different policies: (i) the server reactivates as soon as the number of arrivals in the queue reaches to a predetermined threshold N or the waiting time of the leading customer reaches T units; and (ii) the server reactivates as soon as the number of arrivals in the queue reaches to a predetermined threshold N or T time units have elapsed since the end of the completion period. If the timer expires or the number of arrivals exceeds the threshold N, then the server reactivates and requires a startup time before providing the service until the system is empty. Furthermore, it is assumed that the server breaks down according to a Poisson process and his repair time has a general distribution. We analyze the system characteristics for each scheme. The total expected cost function per unit time is developed to determine the optimal thresholds of N and T at a minimum cost.     

Optimal management for infinite capacity N-policy M/G/1 queue with a removable service station

In this article, we consider an infinite capacity N-policy M/G/1 queueing system with a single removable server. Poisson arrivals and general distribution service times are assumed. The server is controllable that may be turned on at arrival epochs or off at service completion epochs. We apply a differential technique to study system sensitivity, which examines the effect of different system input parameters on the system. A cost model for infinite capacity queueing system under steady-state condition is developed, to determine the optimal management policy at minimum cost. Analytical results for sensitivity analysis are derived. We also provide extensive numerical computations to illustrate the analytical sensitivity properties obtained. Finally, an application example is presented to demonstrate how the model could be used in real applications to obtain the optimal management policy.     

Switched poisson process/g/1 queue with service interruptions

In this paper, we develop an expression for the expected waiting time in a single server queueing system subject to interruptions with alternately varying Poisson arrival and renewal service rates. This queueing system is useful to model situations in production, computer and telecommunication systems in which customer arrivals and service requirements differ depending on whether the server is working or not. We develop an expression for the expected waiting time by approximating the virtual delay process by a Brownian motion. Our approximation for the expected waiting time involves only the means and variances and does not depend on any assumptions regarding the interarrival, service or switching time distributions. We present simulation results to illustrate the quality of our approximations.     

Control Policies of an M/G/1 Queueing System with a Removable and Non-reliable Server

This paper considers a single non-reliable server in the ordinary M/G/1 queueing system whose arrivals form a Poisson process and service times are generally distributed. We also study a single removable and non-reliable server in the controllable M/G/1 queueing systems operating under the N policy, the T policy and the Min( N , T ) policy. It is assumed that the server breaks down according to a Poisson process and the repair time has a general distribution. In three control policies, we show that the probability that the server is busy in the steady-state is equal to the traffic intensity. It is shown that the optimal N policy and the optimal Min( N , T ) policy are always superior to the optimal T policy. Sensitivity analysis is also investigated.     

Comparative analysis of a randomized N-policy queue: An improved maximum entropy method

We analyze a single removable and unreliable server in an M/G/1 queueing system operating under the 〈p, N〉-policy. As soon as the system size is greater than N, turn the server on with probability p and leave the server off with probability (1 ? p). All arriving customers demand the first essential service, where only some of them demand the second optional service. He needs a startup time before providing first essential service until there are no customers in the system. The server is subject to break down according to a Poisson process and his repair time obeys a general distribution. In this queueing system, the steady-state probabilities cannot be derived explicitly. Thus, we employ an improved maximum entropy method with several well-known constraints to estimate the probability distributions of system size and the expected waiting time in the system. By a comparative analysis between the exact and approximate results, we may demonstrate that the improved maximum entropy method is accurate enough for practical purpose, and it is a useful method for solving complex queueing systems.     

The optimal control of an M/G/1 queueing system with server vacations, startup and breakdowns

This paper studies the control policy of the N policy M/G/1 queue with server vacations, startup and breakdowns, where arrivals form a Poisson process and service times are generally distributed. The server is turned off and takes a vacation whenever the system is empty. If the number of customers waiting in the system at the instant of a vacation completion is less than N, the server will take another vacation. If the server returns from a vacation and finds at least N customers in the system, he requires a startup time before providing service until the system is again empty. It is assumed that the server breaks down according to a Poisson process and his repair time has a general distribution. The system characteristics of such a model are analyzed and the total expected cost function per unit time is developed to determine the optimal threshold of N at a minimum cost.     

Cost-minimization analysis of a working vacation queue with N-policy and server breakdowns

This paper investigates the N-policy M/M/1 queueing system with working vacation and server breakdowns. As soon as the system becomes empty, the server begins a working vacation. The server works at a lower service rate rather than completely stopping service during a vacation period. The server may break down with different breakdown rates during the idle, working vacation, and normal busy periods. It is assumed that service times, vacation times, and repair times are all exponentially distributed. We analyze this queueing model as a quasi-birth–death process. Furthermore, the equilibrium condition of the system is derived for the steady state. Using the matrix-geometric method, we find the matrix-form expressions for the stationary probability distribution of the number of customers in the system and system performance measures. The expected cost function per unit time is constructed to determine the optimal values of the system decision variables, including the threshold N and mean service rates. We employ the particle swarm optimization algorithm to solve the optimization problem. Finally, numerical results are provided, and an application example is given to demonstrate the applicability of the queueing model.     

Efficient solution of a class of location–allocation problems with stochastic demand and congestion

We consider a class of location–allocation problems with immobile servers, stochastic demand and congestion that arises in several planning contexts: location of emergency medical clinics; preventive healthcare centers; refuse collection and disposal centers; stores and service centers; bank branches and automated banking machines; internet mirror sites; web service providers (servers); and distribution centers in supply chains. The problem seeks to simultaneously locate service facilities, equip them with appropriate capacities, and allocate user demand to these facilities such that the total cost, which consists of the fixed cost of opening facilities with sufficient capacities, the access cost of users׳ travel to facilities, and the queuing delay cost, is minimized. Under Poisson user demand arrivals and general service time distributions, the problem is set up as a network of independent M/G/1 queues, whose locations, capacities and service zones need to be determined. The resulting mathematical model is a non-linear integer program. Using simple transformation and piecewise linear approximation, the model is linearized and solved to ϵ-optimality using a constraint generation method. Computational results are presented for instances up to 400 users, 25 potential service facilities, and 5 capacity levels with different coefficients of variation of service times and average queueing delay costs per customer. The results indicate that the proposed solution method is efficient in solving a wide range of problem instances.     

Production/inventory systems with a stochastic production rate under a continuous review policy

A single production facility is dedicated to producing one product with completed units going directly into inventory. The unit production time is a random variable. The demand for the product is given by a Poisson process and is supplied directly from inventory when available, or is backordered until it is produced by the production facility. Relevant costs are a linear inventory holding cost, a linear backorder cost, and a fixed setup cost for initiating a production run. The objective is to find a control policy that minimizes the expected cost per time unit.The problem may be modeled as an M/G/1 queueing system, for which the optimal decision policy is a two-critical-number policy. Cost expressions are derived as functions of the policy parameters, and based on convexity properties of these cost expressions, an efficient search procedure is proposed for finding the optimal policy. Computational test results demonstrating the efficiency of the search procedure and the behavior of the optimal policy are presented.     

T-preemptive priority queue and its application to the analysis of an opportunistic spectrum access in cognitive radio networks

We propose a new priority discipline called the T-preemptive priority discipline. Under this discipline, during the service of a customer, at every T time units the server periodically reviews the queue states of each class with different queue-review processing times. If the server finds any customers with higher priorities than the customer being serviced during the queue-review process, then the service of the customer being serviced is preempted and the service for customers with higher priorities is started immediately. We derive the waiting-time distributions of each class in the M/G/1 priority queue with multiple classes of customers under the proposed T-preemptive priority discipline. We also present lower and upper bounds on the offered loads and the mean waiting time of each class, which hold regardless of the arrival processes and service-time distributions of lower-class customers. To demonstrate the utility of the T-preemptive priority queueing model, we take as an example an opportunistic spectrum access in cognitive radio networks, where one primary (licensed) user and multiple (unlicensed) users with distinct priorities can share a communication channel. We analyze the queueing delays of the primary and secondary users in the proposed opportunistic spectrum access model, and present numerical results of the queueing analysis.     

Optimal control of a queueing system with two heterogeneous servers

The problem considered is that of optimally controlling a queueing system which consists of a common buffer or queue served by two servers. The arrivals to the buffer are Poisson and the servers are both exponential, but with different mean service times. It is shown that the optimal policy which minimizes the mean sojourn time of customers in the system is of threshold type. The faster server should be fed a customer from the buffer whenever it becomes available for service, but the slower server should be utilized if and only if the queue length exceeds a readily computed threshold value.     

Queueing analysis and optimal control of and systems

We first consider a finite-buffer single server queue where arrivals occur according to batch Markovian arrival process (BMAP). The server serves customers in batches of maximum size ‘b’ with a minimum threshold size ‘a’. The service time of each batch follows general distribution independent of each other as well as the arrival process. We obtain queue length distributions at various epochs such as, pre-arrival, arbitrary, departure, etc. Some important performance measures, like mean queue length, mean waiting time, probability of blocking, etc. have been obtained. Total expected cost function per unit time is also derived to determine the optimal value N^* of N at a minimum cost for given values of a and b. Secondly, we consider a finite-buffer single server queue where arrivals occur according to BMAP and service process in this case follows a non-renewal one, namely, Markovian service process (MSP). Server serves customers according to general bulk service rule as described above. We derive queue length distributions and important performance measures as above. Such queueing systems find applications in the performance analysis of communication, manufacturing and transportation systems.     

Optimal (N,T)-policy for M/G/1 system with cost structures

In this paper, the optimal (N,T)-policy for M/G/1 system with cost structure is studied. The system operates only intermittently. It is shut down when no customers are present. A fixed set-up cost of K>0 is incurred each time the system is reopened. Also, a holding cost of h>0 per unit time is incurred for each customer present. The (N,T)-policy studied for this system is as follows: the system reactivates as soon as N customers are present or the waiting time of the leading customer reaches a predefined time T (see A.S. Alfa, I. Frigui, Eur. J. Oper. Res. 88 (1996) 599-613; Y.N. Doganata, in: E. Arikan (Ed.), Communication, Control, and Signal Processing, 1990, pp. 1663–1669). Later on, as a comparison, the start of the timer count is relaxed as follows: the system reactivates as soon as N customers are present or the time units after the end of the last busy period reaches a predefined time T. For both cases, the explicit optimal policy (N^*,T^*) for minimizing the long-run average cost per unit time are obtained. As extreme cases, we include the simple optimal policies for N-and T-polices. Several counter-intuitive results are obtained about the optimal T-policies for both types of models.     

Transmission reliability of k minimal paths within time threshold

The quickest path problem involving two attributes, the capacity and the lead time, is to find a single path with minimum transmission time. The capacity of each arc is assumed to be deterministic in this problem. However, in many practical networks such as computer networks, telecommunication networks, and logistics networks, each arc is multistate due to failure, maintenance, etc. Such a network is named a multistate flow network. Hence, both the transmission time to deliver data through a minimal path and the minimum transmission time through a multistate flow network are not fixed. In order to reduce the transmission time, the data can be transmitted through k minimal paths simultaneously. The purpose of this paper is to evaluate the probability that d units of data can be transmitted through k minimal paths within time threshold T. Such a probability is called the transmission reliability. A simple algorithm is proposed to generate all lower boundary points for (d, T), the minimal system states satisfying the demand within time threshold. The transmission reliability can be subsequently computed in terms of such points. Another algorithm is further proposed to find the optimal combination of k minimal paths with highest transmission reliability.     

Entropy maximization and NT vacation M/G/1 model with a startup and unreliable server: comparative analysis on the first two moments of system size

We consider the control policy of an M/G/1 queueing system with a startup and unreliable server, in which the length of the vacation period is controlled either by the number of arrivals during the idle period, or by a timer. After all the customers have been served in the queue, the server immediately takes a vacation and operates an NT vacation policy: the server reactivates as soon as the number of arrivals in the queue reaches a predetermined threshold N or when the waiting time of the leading customer reaches T units. In such a variant vacation system, the steady-state probabilities cannot be obtained explicitly. Thus, the maximum entropy principle is used to derive the approximate formulas for the steady-state probability distributions of the queue length. A comparitive analysis of two approximation approaches, using the first and the second moments of system size, is studied. Both solutions are compared with the exact results under several service time distributions with specific parameter values. Our numerical investigations demonstrate that the use of the second moment of system size for the available information is, in general, sufficient to obtain more accurate estimations than that of the first moment.     

A pseudoconservation law for a time-limited service polling system with structured batch poisson arrivals

We consider a cyclic-service queueing system (polling system) with time-limited service, in which the length of a service period for each queue is controlled by a timer, i.e., the server serves customers until the timer expires or the queue becomes empty, whichever occurs first, and then proceeds to the next queue. The customer whose service is interrupted due to the timer expiration is attended according to the nonpreemptive service discipline. For the cyclic-service system with structured batch Poisson arrivals (M^x/G/1) and an exponential timer, we derive a pseudoconservation law and an exact mean waiting time formula for the symmetric system.     

Analysis of a G/M/K/O queueing loss system with heterogeneous servers and retrials

Consider a G/M/K/O queueing loss system with K heterogeneous servers, exponentially distributed service times, no waiting room, a stationary counting arrival process, and an ordered entry. The ordered entry rule implies that, if the servers are indexed from 1 to K, units first arrive at the first server, then at the second server, and finally at the Kth server. In this queueing system, units that find the servers busy are not lost. Those units re-try to receive service by merging with the incoming units to be reconsidered for service by one of the free servers. This queueing system is analysed in terms of approximating the flows of units inside the system by a two parameter method. An example is introduced and approximation results are compared with those from a simulation study.     

Bi-objective vibration damping optimization for congested location–pricing problem

This paper presents a bi-objective mathematical programming model for the restricted facility location problem, under a congestion and pricing policy. Motivated by various applications such as locating server on internet mirror sites and communication networks, this research investigates congested systems with immobile servers and stochastic demand as M/M/m/k queues. For this problem, we consider two simultaneous perspectives; (1) customers who desire to limit waiting time for service and (2) service providers who intend to increase profits. We formulate a bi-objective facility location problem with two objective functions: (i) maximizing total profit of the whole system and (ii) minimizing the sum of waiting time in queues; the model type is mixed-integer nonlinear. Then, a multi-objective optimization algorithm based on vibration theory (so-called multi-objective vibration damping optimization (MOVDO)), is developed to solve the model. Moreover, the Taguchi method is also implemented, using a response metric to tune the parameters. The results are analyzed and compared with a non-dominated sorting genetic algorithm (NSGA-II) as a well-developed multi-objective evolutionary optimization algorithm. Computational results demonstrate the efficiency of the proposed MOVDO to solve large-scale problems.