An Overview for Markov Decision Processes in Queues and Networks <s> Objective three: Dynamic control under different service mechanisms <s> In this article we consider the optimal control of an M[X]/M/s queue, s ≧ 1. In addition to Poisson bulk arrivals we incorporate a reneging function. Subject to control are an admission price p and the service rate μ. Thus, through p, balking response is induced. When i customers are present a cost h(i,μ,p) per unit time is incurred, discounted continuously. Formulated as a continuous time Markov decision process, conditions are given under which the optimal admission price and optimal service rate are each nondecreasing functions of i. In Section 4 we indicate how the infinite state space may be truncated to a finite state space for computational purposes. <s> BIB001 </s> An Overview for Markov Decision Processes in Queues and Networks <s> Objective three: Dynamic control under different service mechanisms <s> Two of the optimality criteria most commonly considered to compare job assignment policies, namely, the stochastic order and the average total completion time criterion, are discussed. It is shown that the latter, while being weaker than the former, still provides a useful criterion when policies are to be evaluated in terms of average performance measures such as the system average response time. Some of the most relevant results available in the literature on job assignment to parallel first come, first served (FCFS) servers are summarized. The assignment problem is discussed for a parallel system of processor sharing (PS) queues with exponential interarrival times and exponential and identical service requirements. The optimality of the join-the-shortcut-queue (JSQ) assignment policy for this case is proven. Feasible policies for general service time distribution are discussed. An approach allowing a meaningful comparison of servers in the perspective of job assignment is proposed. A comparison of the assignment problem for FCFS and PS parallel systems is presented. > <s> BIB002 </s> An Overview for Markov Decision Processes in Queues and Networks <s> Objective three: Dynamic control under different service mechanisms <s> In this article the M/G/1 queue with server vacations is considered with the assumption that the decision whether or not to take a new vacation, when the system is empty, depends on the number of vacations already taken through a random outcome. Both descriptive and optimization issues are considered, where the latter is done under the expected long-run average cost criterion with linear holding costs, fixed setup costs and a concave piecewise linear reward function for being on vacation. The optimization problem results in an infinite dimensional fractional program of which the solution yields a (deterministic) policy of the control limit type. <s> BIB003 </s> An Overview for Markov Decision Processes in Queues and Networks <s> Objective three: Dynamic control under different service mechanisms <s> In this paper we consider a class of single-server queueing systems with compound Poisson arrivals, in which, at service completion epochs, the server has the option of taking off for one or several vacations of random length. The cost structure consists of a holding cost rate specified by a general non-decreasing function of the queue size, fixed costs for initiating and terminating service, and a variable operating cost incurred for each unit of time that the system is in operation. We show under some weak conditions with respect to the holding cost rate function and the service time, vacation time and arrival batch size distributions that it is either optimal among all feasible (stationary and non-stationary) policies never to take a vacation, or it is optimal to take a vacation when the system empties out and to resume work when, upon completion of a vacation, the queue size is equal to or in excess of a critical threshold. These optimality results are generalized for several variants of this model. VACATION MODELS; REMOVABLE SERVER; MONOTONE POLICIES; SEMI-MARKOV DECISION PROCESS <s> BIB004 </s> An Overview for Markov Decision Processes in Queues and Networks <s> Objective three: Dynamic control under different service mechanisms <s> An M/G/1 queue where the server may take repeated vacations is considered. Whenever a busy period terminates, the server takes a vacation of random duration. At the end of each vacation, the server may either take a new vacation or resume service; if the queue is found empty, the server always takes a new vacation. The cost structure includes a holding cost per unit of time and per customer in the system and a cost each time the server is turned on. One discounted cost criterion and two average cost criteria are investigated. It is shown that the vacation policy that minimizes the discounted cost criterion over all policies (randomized, history dependent, etc.) converges to a threshold policy as the discount factor goes to zero. This result relies on a nonstandard use of the value iteration algorithm of dynamic programming and is used to prove that both average cost problems are minimized by a threshold policy. > <s> BIB005 </s> An Overview for Markov Decision Processes in Queues and Networks <s> Objective three: Dynamic control under different service mechanisms <s> Consider anM/M/1 queueing system with server vacations where the server is turned off as soon as the queue gets empty. We assume that the vacation durations form a sequence of i.i.d. random variables with exponential distribution. At the end of a vacation period, the server may either be turned on if the queue is non empty or take another vacation. The following costs are incurred: a holding cost ofh per unit of time and per customer in the system and a fixed cost of γ each time the server is turned on. We show that there exists a threshold policy that minimizes the long-run average cost criterion. The approach we use was first proposed in Blanc et al. (1990) and enables us to determine explicitly the optimal threshold and the optimal long-run average cost in terms of the model parameters. <s> BIB006 </s> An Overview for Markov Decision Processes in Queues and Networks <s> Objective three: Dynamic control under different service mechanisms <s> This paper studies bicriterion optimization of an M/G/1 queue with a server that can be switched on and off. One criterion is an average number of customers in the system, and another criterion is an average operating cost per unit time. Operating costs consist of switching and running costs. We describe the structure of Pareto optimal policies for a bicriterion problem and solve problems of optimization of one of these criteria under a constraint for another one. <s> BIB007 </s> An Overview for Markov Decision Processes in Queues and Networks <s> Objective three: Dynamic control under different service mechanisms <s> We consider a two-stage tandem queue attended by a moving server, with homogeneous Poisson arrivals and general service times. Two different holding costs for stages 1 and 2 and different switching costs from one stage to the other are considered. We show that the optimal policy in the second stage is greedys and if the holding cost rate in the second stage is greater or equal to the rate in the first stage, then the optimal policy in the second stage is also exhaustive. Then, the optimality condition for sequential service policy in systems with zero switchover times is introduced. Considering some properties of the optimal policy, we then define a Triple-Threshold (TT) policy to approximate the optimal policy in the first stage. Finally, a model is introduced to find the optimal TT policy, and using numerical results, it is shown that the TT policy accurately approximates the optimal policy. <s> BIB008 </s> An Overview for Markov Decision Processes in Queues and Networks <s> Objective three: Dynamic control under different service mechanisms <s> Abstract We consider a model consisting of a deteriorating installation (I) that transfers a raw material to a production unit and a buffer, which has been built between the I and the production unit to cope with unexpected failures of the I that may cause delays in production. The problem of the optimal preventive maintenance of the I is considered. It is assumed that the repair times follow some known continuous distributions. It seems intuitively reasonable that, for fixed buffer level, the optimal policy is of control-limit type, i.e. it initiates the preventive maintenance of the I if and only if the degree of its deterioration exceeds a critical level. An efficient semi-Markov decision algorithm, which operates on the class of control-limit policies, is developed. Numerical examples provide strong evidence that the algorithm converges to the optimal policy. <s> BIB009 </s> An Overview for Markov Decision Processes in Queues and Networks <s> Objective three: Dynamic control under different service mechanisms <s> We consider the single server Markovian queue and we assume that arriving customers decide whether to enter the system or balk based on a natural reward-cost structure, which incorporates their desire for service as well as their unwillingness to wait. ::: ::: We suppose that the waiting space of the system is partitioned in compartments of fixed capacity for a customers. Before making his decision, a customer may or may not know the compartment in which he will enter and/or the position within the compartment in which he will enter. Thus, denoting by n the number of customers found by an arriving customer, he may or may not know ? n/a ?+1 and/or (n mod a)+1. ::: ::: We examine customers' behavior under the various levels of information regarding the system state and we identify equilibrium threshold strategies. We also study the corresponding social and profit maximization problems. <s> BIB010 </s> An Overview for Markov Decision Processes in Queues and Networks <s> Objective three: Dynamic control under different service mechanisms <s> In this paper, we discuss the dynamic server control in a two-class service system with abandonments. Two models are considered. In the first case, rewards are received upon service completion, and there are no abandonment costs (other than the lost opportunity to gain rewards). In the second, holding costs per customer per unit time are accrued, and each abandonment involves a fixed cost. Both cases are considered under the discounted or average reward/cost criterion. These are extensions of the classic scheduling question (without abandonments) where it is well known that simple priority rules hold. ::: ::: The contributions in this paper are twofold. First, we show that the classic c---μ rule does not hold in general. An added condition on the ordering of the abandonment rates is sufficient to recover the priority rule. Counterexamples show that this condition is not necessary, but when it is violated, significant loss can occur. In the reward case, we show that the decision involves an intuitive tradeoff between getting more rewards and avoiding idling. Secondly, we note that traditional solution techniques are not directly applicable. Since customers may leave in between services, an interchange argument cannot be applied. Since the abandonment rates are unbounded we cannot apply uniformization--and thus cannot use the usual discrete-time Markov decision process techniques. After formulating the problem as a continuous-time Markov decision process (CTMDP), we use sample path arguments in the reward case and a savvy use of truncation in the holding cost case to yield the results. As far as we know, this is the first time that either have been used in conjunction with the CTMDP to show structure in a queueing control problem. The insights made in each model are supported by a detailed numerical study. <s> BIB011 </s> An Overview for Markov Decision Processes in Queues and Networks <s> Objective three: Dynamic control under different service mechanisms <s> While vacation processes are considered to be ordinary behavior for servers, the study of queueing networks with server vacations is limited, interesting, and challenging. In this paper, we provide a unified and effective method of functional analysis for the study of a supermarket model with server multiple vacations. Firstly, we analyze a supermarket model of N identical servers with server multiple vacations, and set up an infinite-dimensional system of differential (or mean-field) equations, which is satisfied by the expected fraction vector, in terms of a technique of tailed equations. Secondly, as N??? we use the operator semigroup to provide a mean-field limit for the sequence of Markov processes, which asymptotically approaches a single trajectory identified by the unique and global solution to the infinite-dimensional system of limiting differential equations. Thirdly, we provide an effective algorithm for computing the fixed point of the infinite-dimensional system of limiting differential equations, and use the fixed point to give performance analysis of this supermarket model, including the mean of stationary queue length in any server and the expected sojourn time that any arriving customer spends in this system. Finally, we use some numerical examples to analyze how the performance measures depend on some crucial factors of this supermarket model. Note that the method of this paper will be useful and effective for performance analysis of complicated supermarket models with respect to resource management in practical areas such as computer networks, manufacturing systems and transportation networks. <s> BIB012 </s> An Overview for Markov Decision Processes in Queues and Networks <s> Objective three: Dynamic control under different service mechanisms <s> We investigate a resource allocation problem in a multi-class server with convex holding costs and user impatience under the average cost criterion. In general, the optimal policy has a complex dependency on all the input parameters and state information. Our main contribution is to derive index policies that can serve as heuristics and are shown to give good performance. Our index policy attributes to each class an index, which depends on the number of customers currently present in that class. The index values are obtained by solving a relaxed version of the optimal stochastic control problem and combining results from restless multi-armed bandits and queueing theory. They can be expressed as a function of the steady-state distribution probabilities of a one-dimensional birth-and-death process. For linear holding cost, the index can be calculated in closed-form and turns out to be independent of the arrival rates and the number of customers present. In the case of no abandonments and linear holding cost, our index coincides with the cμ-rule, which is known to be optimal in this simple setting. For general convex holding cost we derive properties of the index value in limiting regimes: we consider the behavior of the index (i) as the number of customers in a class grows large, which allows us to derive the asymptotic structure of the index policies, and (ii) as the abandonment rate vanishes, which allows us to retrieve an index policy proposed for the multi-class M/M/1 queue with convex holding cost and no abandonments. In fact, in a multi-server environment it follows from recent advances that the index policy is asymptotically optimal for linear holding cost. To obtain further insights into the index policy, we consider the fluid version of the relaxed problem and derive a closed-form expression for the fluid index. The latter coincides with the stochastic model in case of linear holding costs. For arbitrary convex holding cost the fluid index can be seen as the Gcμθ-rule, that is, including abandonments into the generalized cμ-rule (Gcμ-rule). Numerical experiments show that our index policies become optimal as the load in the system increases. <s> BIB013 </s> An Overview for Markov Decision Processes in Queues and Networks <s> Objective three: Dynamic control under different service mechanisms <s> The goal of this paper is to provide a model that is an extension of classic scheduling problems for a tandem queueing system by including customer impatience. In such scenarios, the server(s) must balance abandonments from each phase of service with the need to prioritize higher reward customers. This presents an interesting challenge since the trade-off between the cost of abandonments and revenue maximization is not at all clear. As a result of customer abandonments, traditional solution techniques are not available. In particular, uniformization is not possible since the transition rates are unbounded. We do our analysis in continuous time, using the continuous-time Markov decision process framework to discern simple relationships of the value functions depending on the starting state. We then use sample path arguments to analyze the structure of the optimal policy. We provide conditions under which an optimal policy is nonidling and never splits servers (except to avoid idling). We then consider the single-server model as a proxy for the decision problem when there are more customers at each station than there are servers. In this case, we provide conditions under which it is optimal to prioritize each station. <s> BIB014 </s> An Overview for Markov Decision Processes in Queues and Networks <s> Objective three: Dynamic control under different service mechanisms <s> We consider queueing systems with general abandonment. Abandonment times are approximated by a particular Cox distribution with all phase exponential rates being the same. We prove that this distribution arbitrarily closely approximates any nonnegative distribution. By explicitly modeling the waiting time of the first customer in line, we obtain a natural bounded jump Markov process allowing for uniformization. This approach is useful to solve, via dynamic programming, various optimization problems where the objectives and/or constraints involve the distributions of the performance measures, not only their expected values. It is also useful for the performance analysis of queueing systems with general abandonment times. <s> BIB015
Many practical and real problems lead to introduction of different service mechanisms which make some interesting queueing systems, for example, priority queues, processorsharing queues, retrial queues, vacation queues, repairable queues, fluid queues and so on. (a) The priority queueing control: The priority is an important service mechanism, and it is a precondition that sets up useful relations among key customers, segmenting market and adhering to long-term cooperation. Note that the priority makes dynamic control of queues with multi-class customers. Readers may refer to Rykov BIB002 . BIB012 , Altman and Nain BIB005 BIB006 , Kella BIB003 and Federgruen and So BIB004 . (e) The repairable queueing control: Dimitrakos and Kyriakidis BIB009 . (f ) The removable server control: For dynamic control of working servers, it is nec-essary to real-time response to the peak period or an emergency phenomenon through increasing or decreasing the number of working servers according to either customer number or system workload. We refer the readers to Feinberg and Kim BIB007 , Feinberg and Kella  and Iravani et al. BIB008 . (g) The dynamic control of queueing behavior: blocking by Blackburn  and Economou and Kanta BIB010 ; reneging and impatience by Li et al. BIB012 and Anderson BIB001 ; and abandonment by Down et al. BIB011 , Legros et al. BIB015 , Larrañaga et al. BIB013 and Zayas-Cabán et al. BIB014 .