An Overview for Markov Decision Processes in Queues and Networks <s> Objective four: Threshold control <s> This paper studies an M/M/1 queueing decision process in which the arrival and service rates are chosen from a finite set whenever the queue length changes. Each choice has a switching cost depending on the chosen rates and those currently in use, and a usage cost depending on the chosen rates and the queue length; these switching and usage cost functions are submodular and satisfy additional technical conditions. The system objective is to find a policy for dynamically choosing the rates, based on the current rates and queue length, that minimizes the expected total discounted cost or average cost over an infinite horizon. We prove that there is a monotone hysteretic optimal policy in which the arrival and service rates are decreasing and increasing, respectively, in the queue length; there is a hysteresis (retardation) in the changing of the actions due to the switching costs. We establish this result by showing that such optimal policies exist for an equivalent discrete-time random walk decision proces... <s> BIB001 </s> An Overview for Markov Decision Processes in Queues and Networks <s> Objective four: Threshold control <s> A cyclic service system is composed of K channels (queues) and a single cyclically roving server who typically takes a positive amount of time to switch between channels. Research has previously focused on evaluating and computing performance measures (notably, waiting times) of fixed template routing schemes under three main service disciplines, the exhaustive, gated and limited service regimes. In this paper, probabilistic results are derived that allow control strategies and optimal policies to be considered for the first time. By concentrating on a new objective function, we are able to derive rules of index form amenable for direct implementation to dynamically control the system at suitably defined decision epochs. These rules utilize current system information, are of an adaptive nature, and are shown to emanate from a general physical principle. CYCLIC QUEUES; POLLING SYSTEMS; STOCHASTIC SCHEDULING <s> BIB002 </s> An Overview for Markov Decision Processes in Queues and Networks <s> Objective four: Threshold control <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> BIB003 </s> An Overview for Markov Decision Processes in Queues and Networks <s> Objective four: Threshold control <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 four: Threshold control <s> The system under consideration comprises two classes of customers to be served by two stations, with parallel servers in each station. While class-1 customers can only receive service from station 1, class-2 customers can be served by either station. Arrival processes of customers form two mutually independent Poisson processes. The service time of a customer at either station is exponentially distributed with a common rate. A class- i customer, while present in the system, will incur a holding cost h i with h 1 ≥ h 2 . The objective is to dynamically assign customers to idle servers so that the expected discounted (or the long-run average) holding cost is minimized. We show that a class- j customer should be assigned to an idle server in station j , j = 1, 2, whenever possible, and a class-2 customer should be assigned to an idle server in station 1 only if (no class-1 customers are waiting, and) the length of queue 2 exceeds a critical number. Moreover, the critical number is monotonically increasing in the number of busy servers in station 1. The numerical results for some test cases are reported. <s> BIB005 </s> An Overview for Markov Decision Processes in Queues and Networks <s> Objective four: Threshold control <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 four: Threshold control <s> This paper considers an M/M/1 queueing system with dynamically controlled arrival and service rates. At each arrival or service completion epoch, a decision maker chooses a pair of arrival and service rates from a finite set, and the system operates under these rates until the next arrival or service completion. There is a switching cost for changing the rates, and there is a cost per unit time of holding customers and using the arrival and service rates. The results describe natural conditions on the costs under which an optimal policy for either the discounted-cost or average-cost criterion is a hysteretic policy. Such a policy increases the service rate and decreases the arrival rate as the queue length increases. Furthermore, the control exhibits a stickiness or resistance to change, called hysteresis, due to the switching costs. <s> BIB007 </s> An Overview for Markov Decision Processes in Queues and Networks <s> Objective four: Threshold control <s> We consider a two-class $$M^{\lambda_1, \lambda_2}|M^{\mu}|1$$ 1 preemptive priority queue in which there are two essential, on-line decisions that have to be taken. The first is the decision to either accept or reject new type-1 or type-2 jobs. The second is the decision to abort jobs, i.e., to remove any type-1 or type-2 jobs from the system. We show that there exist optimal threshold policies for these two types of, decisions. <s> BIB008
In dynamic control of queues and networks, the threshold-type policy is a simple and effective mode, including single-threshold and dual-threshold. (a) The single-threshold policy: Brouns  , Altman and Nain BIB006 , Federgruen and So BIB004 , Brouns and Van Der Wal BIB008 ; (b) The dual-threshold policy: Lu and Serfozo BIB001 , Plum  and Kitaev and Serfozo BIB007 . BIB002 and Altman and Nain BIB006 . (c) The assignment policy: Weber  , Bonomi BIB003 and Xu et al. BIB005 .