An Overview for Markov Decision Processes in Queues and Networks <s> Objective seven: Dynamic control of queues and networks with pricing <s> The reorder point/reorder quantity policies, also referred to as r, Q policies, are widely used in industry and extensively studied in the literature. However, for a period of almost 30 years there has been no efficient algorithm for computing optimal control parameters for such policies. In this paper, we present a surprisingly simple and efficient algorithm for the determination of an optimal r*, Q* policy. The computational complexity of the algorithm is linear in Q*. For the most prevalent case of linear holding, backlogging and stockout penalty costs in addition to fixed order costs, the algorithm requires at most 6r* + 13Q* elementary operations additions, comparisons and multiplications, and hence, no more than 13 times the amount of work required to do a single evaluation of the long-run average cost function in the point r*, Q*. <s> BIB001 </s> An Overview for Markov Decision Processes in Queues and Networks <s> Objective seven: Dynamic control of queues and networks with pricing <s> Abstract This paper studies pricing and incentive issues in the assignment of customers to servers in a system that suffers congestion effects. When customers have private information about their waiting costs, a system administrator who wishes to maximize steady-sate net benefits per unit of time (i.e. total benefits from service minus total waiting costs) may do so using a pricing and routing scheme that is incentive compatible; that is, no customer has any incentive to reveal his private information untruthfully. When the system administrator wants to maximize toll revenue, the optimal scheme involves higher tolls, and hence lower congestion, than is socially optimal. <s> BIB002 </s> An Overview for Markov Decision Processes in Queues and Networks <s> Objective seven: Dynamic control of queues and networks with pricing <s> Existing studies of pricing when customers queue, assume that the firm cannot adjust the price to the state of demand. In most applications this assumption is false. We adapt the classic model of Naor (1969) to allow the firm to adjust the price to the state of demand. When customers are homogeneous the firm's pricing rule maximizes social welfare. When customers are unobservably heterogenous, the firm's pricing rule does not maximize social welfare. We find that the firm may not always attract customers even when it is technically and economically feasible to do so. This is interpreted as an option effect. The effects of changes to the basic parameters, on the queue length are presented. <s> BIB003 </s> An Overview for Markov Decision Processes in Queues and Networks <s> Objective seven: Dynamic control of queues and networks with pricing <s> We consider congestion control in a nonstationary queueing system. Assuming that the arrival and service rates are bounded, periodic functions of time, a Markov decision process (MDP) formulation is developed. We show under the infinite horizon discounted and average reward optimality criteria, for each fixed time, optimal pricing and admission control strategies are nondecreasing in the number of customers in the system. This extends stationary results to the nonstationary setting. Despite this result, the problem still seems intractable. We propose an easily implementable pointwise stationary approximation (PSA) to approximate the optimal policies, suggest a heuristic to improve the implementation of the PSA and verify its usefulness via a numerical study. <s> BIB004 </s> An Overview for Markov Decision Processes in Queues and Networks <s> Objective seven: Dynamic control of queues and networks with pricing <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> BIB005 </s> An Overview for Markov Decision Processes in Queues and Networks <s> Objective seven: Dynamic control of queues and networks with pricing <s> We investigate a problem of admission control in a queue with batch arrivals. We consider a single server with exponential service times and a compound Poisson arrival process. Each arriving batch computes its expected benefit and decides whether or not to enter the system. The controller's problem is to set state dependent prices for arriving batches. Once prices have been set we formulate the admission control problem, derive properties of the value function, and obtain the optimal admission policy. <s> BIB006 </s> An Overview for Markov Decision Processes in Queues and Networks <s> Objective seven: Dynamic control of queues and networks with pricing <s> This paper studies optimal pricing for a GI/M/k/N queueing system with several types of customers. An arrival joins the queue if the price of service is not higher than the maximum amount that the arrival is willing to pay, and this maximum amount is defined by the customer type. A system manager chooses a price depending on the number of customers in the system. In addition, the system incurs holding costs when there are customers waiting in the queue for their services. Service times and holding costs do not depend on customer types. The holding costs are nondecreasing and convex with respect to the number of customers in the queue. This paper describes average reward optimal, canonical, bias optimal, and Blackwell optimal policies for this pricing problem. <s> BIB007 </s> An Overview for Markov Decision Processes in Queues and Networks <s> Objective seven: Dynamic control of queues and networks with pricing <s> Pricing control is an important problem in service systems and it aims to control customer behaviors through an economic way, instead of administrative commands. In this paper, we study a dynamic pricing and service rate control problem in an open Jackson network with limited capacity. The goal is to determine the optimal admission prices and the optimal service rates at every state such that the long-run average social welfare is maximized. The original problem is decomposed into a rate-setting problem plus a price-setting problem. To solve the rate-setting problem, we derive a difference formula based on the sensitivity-based optimization theory. When the cost rate function is convex in service rates and the value rate function is concave in arrival rates, we decompose the rate-setting problem into a series of convex optimization subproblems. When the rate functions have linear structure, these subproblems are even simpler and a bang–bang control is optimal. For the price-setting problem, we determine the state-dependent prices so as to induce the optimal arrival rates obtained by the rate-setting problem. We propose a recursive algorithm to numerically compute the conditional expected delays at every state. Finally, we conduct numerical experiments to explore the optimality properties and some useful insights for this dynamic pricing control problem. <s> BIB008
The optimal pricing policy is an interesting topic in dynamic control of queues and networks, e.g., see literature Low  , Chen and Frank BIB003 , Yoon and Lewis BIB004 , Ç elik and Maglaras  , Economou and Kanta BIB005 , Yildirim and Hasenbein BIB006 , Feinberg and Yang BIB007 , Bradford BIB002 , Xia and Chen BIB008 and Federgruen and Zheng BIB001 .