A reinforcement-learning approach for admission control in distributed network service systems

In the distributed network service systems such as streaming-media systems and resource-sharing systems with multiple service nodes, admission control (AC) technology is an essential way to enhance performance. Model-based optimization approaches are good ways to be applied to analyze and solve the optimal AC policy. However, due to “the curse of dimensionality”, computing such policy for practical systems is a rather difficult task. In this paper, we consider a general model of the distributed network service systems, and address the problem of designing an optimal AC policy. An analytical model is presented for the system with fixed parameters based on semi-Markov decision process (SMDP). We design an event-driven AC policy, and the stationary randomized policy is taken as the policy structure. To solve the SMDP, both the state aggregation approach and the reinforcement-learning (RL) method with online policy optimization algorithm are applied. Then, we extend the problem by considering the system with time-varying parameters, where the arrival rates of requests at each service node may change over time. In view of this situation, an AC policy switching mechanism is presented. This mechanism allows the system to decide whether to adjust its AC policy according to the policy switching rule. And in order to maximize the gain of system, that is, to obtain the optimal AC policy switching rule, another RL-based algorithm is applied. To assess the effectiveness of SMDP-based AC policy and policy switching mechanism for the system, numerical experiments are presented. We compare the performance of optimal policies obtained by the solutions of proposed methods with other classical AC policies. The simulation results illustrate that higher performance and computational efficiency could be achieved by using the SMDP model and RL-based algorithms proposed in this paper.     

Piecewise linear approximations for the static–dynamic uncertainty strategy in stochastic lot-sizing

In this paper, we develop a unified mixed integer linear modelling approach to compute near-optimal policy parameters for the non-stationary stochastic lot sizing problem under static–dynamic uncertainty strategy. The proposed approach applies to settings in which unmet demand is backordered or lost; and it can accommodate variants of the problem for which the quality of service is captured by means of backorder penalty costs, non-stockout probabilities, or fill rate constraints. This approach has a number of advantages with respect to existing methods in the literature: it enables seamless modelling of different variants of the stochastic lot sizing problem, some of which have been previously tackled via ad hoc solution methods and some others that have not yet been addressed in the literature; and it produces an accurate estimation of the expected total cost, expressed in terms of upper and lower bounds based on piecewise linearisation of the first order loss function. We illustrate the effectiveness and flexibility of the proposed approach by means of a computational study.     

Optimal design and augmentation of strongly attack-tolerant two-hop clusters in directed networks

We consider the problems of minimum-cost design and augmentation of directed network clusters that have diameter 2 and maintain the same diameter after the deletion of up to R elements (nodes or arcs) anywhere in the cluster. The property of a network to maintain not only the overall connectivity, but also the same diameter after the deletion of multiple nodes/arcs is referred to as strong attack tolerance. This paper presents the proof of NP-completeness of the decision version of the problem, derives tight theoretical bounds, as well as develops a heuristic algorithm for the considered problems, which are extremely challenging to solve to optimality even for small networks. Computational experiments suggest that the proposed heuristic algorithm does identify high-quality near-optimal solutions; moreover, in the special case of undirected networks with identical arc construction costs, the algorithm provably produces an exact optimal solution to strongly attack-tolerant two-hop network design problem, regardless of the network size.     

Pilot power optimization and coverage control in WCDMA mobile networks

In mobile networks using wideband code division multiple access (WCDMA), common pilot channel (CPICH) signals are used by mobile terminals for channel quality estimation, cell selection, and handover. The strength of the CPICH signal determines the coverage area of the cell, impacts the network capacity, and thereby the quality of service, and is therefore a crucial parameter in network planning and optimization. Pilot power is the most important parameter that allows us to control the strength of the CPICH signal. The more power is spent for pilot signals, the better coverage is obtained. On the other hand, a higher value of the pilot power level in a cell means higher pilot pollution in the network and less power available to serve user traffic in the cell. In this paper, we consider the problem of minimizing the total amount of pilot power subject to a coverage constraint. Our modeling and solution approaches are based on mathematical programming techniques. We present a basic model for pilot power optimization subject to a full coverage constraint as well as its extended version which allows us to study various coverage levels and to consider user traffic distribution over the network. We also propose an efficient algorithm that gives near-optimal solutions to the problem within a reasonable amount of time. We report our numerical experiments for three WCDMA networks of various sizes based on realistic planning scenarios and examine the effect of different levels of the required coverage degree on the total amount of pilot power.     

Risk Pooling Advantages of Manufacturing Network Configuration

The decision of a firm to set up a plant network is influenced by a number of factors, including demand fluctuations across its portfolio of products, logistics costs, and service level requirements. Product plant networks offer the benefits of consolidated production and reduced transshipment costs; on the other hand, process plant networks allow intensive dedication to process expertise and economies of scale. In this paper, we show that, aside from these benefits, process plant networks offer significant risk pooling advantages under a wide range of conditions. We analytically demonstrate that, even without accounting for economies of scale advantages, firms may prefer the process plant network configuration due to the risk pooling benefits offered.     

The benefit of receding horizon control: Near-optimal policies for stochastic inventory control

In this paper we address the single-item, single-stocking point, non-stationary stochastic lot-sizing problem under backorder costs. It is well known that the (s, S) policy provides the optimal control for such inventory systems. However the computational difficulties and the nervousness inherent in (s, S) paved the way for the development of various near-optimal inventory control policies. We provide a systematic comparison of these policies and present their expected cost performances. We further show that when these policies are used in a receding horizon framework the cost performances improve considerably and differences among policies become insignificant.     

优化设施服务的网络调整费用均衡问题研究

在物流网络中,当服务设施(配送中心、大型超市等)建立后,由于设施服务水平、市场需求等因素发生变化,需要调整物流网络中各个环节的配送时间来优化设施的服务能力。调整优化的过程中既要考虑需求目标、运行费用的同时也需要考虑调整的成本。本文针对该问题,提出了优化设施服务的物流网络调整费用均衡模型,并针对单个设施的树形配送网络结构,通过辅助网络将该问题转化为最小费用流问题,给出了多项式算法。最后,文中给出了算例以及两种费用的均衡分析。     

Revenue Management of Reusable Resources with Advanced Reservations

We consider a revenue management problem wherein the seller is endowed with a single type resource with a finite capacity and the resource can be repeatedly used to serve customers. There are multiple classes of customers arriving according to a multi‐class Poisson process. Each customer, upon arrival, submits a service request that specifies his service start time and end time. Our model allows customer advanced reservation times and services times in each class to be arbitrarily distributed and correlated. Upon arrival of each customer, the seller must instantaneously decide whether to accept this customer's service request. A customer whose request is denied leaves the system. A customer whose request is accepted is allocated with a specific item of the resource at his service start time. The resource unit occupied by a customer becomes available to other customers after serving this customer. The seller aims to design an admission control policy that maximizes her expected long‐run average revenue. We propose a policy called the ε‐perturbation class selection policy (ε‐CSP), based on the optimal solution in the fluid setting wherein customers are infinitesimal and customer arrival processes are deterministic, under the restriction that the seller can utilize at most (1 − ε) of her capacity for any ε ∈ (0, 1). We prove that the ε‐CSP is near‐optimal. More precisely, we develop an upper bound of the performance loss of the ε‐CSP relative to the seller's optimal revenue, and show that it converges to zero with a square‐root convergence rate in the asymptotic regime wherein the arrival rates and the capacity grow up proportionally and the capacity buffer level ε decays to zero.     

Revenue Management Through Dynamic Cross Selling in Call Centers

This paper models the cross‐selling problem of a call center as a dynamic service rate control problem. The question of when and to whom to cross sell is explored using this model. The analysis shows that, under the optimal policies, cross‐selling targets may be a function of the operational system state. Sufficient conditions are established for the existence of preferred calls, i.e., calls that will always generate a cross‐sell attempt. These provide guidelines in segment formation for marketing managers, and lead to a static heuristic policy. Numerical analysis establishes the value of different types of information, and different types of automation available for cross selling. Increased staffing for the same call volume is shown to have a positive and increasing return on revenue generation via cross selling, suggesting the need to staff for lower loads in call centers that aim to be revenue generators. The proposed heuristic leads to near optimal performance in a wide range of settings.     

Practical scheduling for call center operations

A practical spreadsheet-based scheduling method is developed to determine the optimal allocation of service agents to candidate tour types and start times in an inbound call center. A stationary Markovian queueing model with customer abandonment is employed to determine required staffing levels for a sequence of time intervals with varying call volumes, handling times, and relative agent availabilities. These staffing requirements populate a quadratic programming model for determining the distribution of agent tours that will maximize the fraction of offered calls beginning service within a target response time, subject to side constraints on tour type quantities. The optimal distribution is scaled to reflect the total number of scheduled agents, and a near-optimal integer solution is derived using rounding thresholds found by successive one-dimensional searches. This novel approach has been successfully implemented in large service centers at Qwest Communications and could easily be adapted to other operational environments.     

Minimizing number of tardy jobs on a single machine subject to periodic maintenance

This paper considers a single-machine scheduling problem with periodic maintenance. In this study, a schedule consists of several maintenance periods and each maintenance period is scheduled after a periodic time interval. The objective is to find a schedule that minimizes the number of tardy jobs subject to periodic maintenance and nonresumable jobs. Based on the Moore's algorithm, an effective heuristic is developed to provide a near-optimal schedule for the problem. A branch-and-bound algorithm is also proposed to find the optimal schedule. Some important theorems associated with the problem are implemented in the algorithm. Computational results are presented to demonstrate the effectiveness of the proposed heuristic.     

Real options valuation principle in the multi-period base-stock problem

This paper analyzes the multi-period base-stock problem where there is a financial risk associated with a stochastic demand. For the single-period problem, it is known that the optimal inventory policy can be obtained with the Black and Scholes option pricing formula. This paper pushes the analysis further by applying the options valuation framework to the multi-period problem and presenting an algorithm for finding the optimal inventory policy. A computational study indicates that the effect of systematic risk is typically negligible (as for the single-period problem). Therefore, it can be concluded that systematic risk in demand is of little importance for optimal inventory control.     

ALLOCATING AND SCHEDULING MOBILE DIAGNOSTIC IMAGING EQUIPMENT AMONG HOSPITALS

The allocation and weekly scheduling of mobile magnetic resonance imaging (MRI) units leased to a group of hospitals that share the equipment can be a complex problem. Similar problems occur in other domains where expensive equipment or facilities such as video conference facilities, aircraft, and supercomputers are leased. The crux of the problem was determining the number of days and which days of the week various types of equipment types should be leased to hospitals, so as to maximize the rental revenues and satisfy client preferences for days of the week and equipment types. We found rental revenues were a decreasing function of the number of days allocated to a hospital. We considered two sub-problems linked by a set of variables to model the problem. We show that one of these subproblems is a minimum cost network flow problem and the other is an integer multi-commodity transportation problem. We developed a procedure for solving the latter problem by exploiting earlier results for specialized networks. We conducted a computational study to evaluate the performance of this procedure and showed that it generally provides near-optimal integer solutions. We describe the development and implementation of a spreadsheet-based decision support system based on this model. This system was successfully implemented by a small firm with no expertise or prior experience using models.     

Joint production and subcontracting planning of unreliable multi-facility multi-product production systems

This article addresses the problem of joint optimization of production and subcontracting of unreliable production systems. The production system considered presents a common problem in the pharmaceutical industry. It is composed of multiple production facilities with different capacities, each of which is capable of producing two different classes of medications (brand name and generic). The resort to subcontracting is double: first, it involves the quantity of products received on a regular basis in order to compensate for insufficient production capacity in existing facilities, second, when needed, urgent orders are also launched in order to reduce the risk of shortages caused by breakdowns of manufacturing facilities. Failures, repairs and urgent delivery times may be represented by any probability distributions.The objective is to propose a general control policy for the system under consideration, and to obtain, in the case of two facilities, optimal control parameters that minimize the total incurred cost for a specific level of the customer service provided. Given the complexity of the problem considered, an experimental optimization approach is chosen in order to determine the optimal control parameters. This approach includes experimental design, analysis of variance, response surface methodology and simulation modeling. It allows the accurate representation of the dynamic and stochastic behaviors of the production system and the assessment of optimal control parameters. Other control parameters which represent the subcontracting are introduced and three joint production/subcontracting control policies (general, urgent, regular) are compared to one another. The proposed joint production/regular subcontracting control policy involves a cost decrease of up to 20%, as compared to results obtained by Dror et al. [1], who used a simplified control policy in addition to a heuristic solution approach for a real case study. This policy offers not only cost savings, but is also easier to manage, as compared to that proposed by Dror et al. [1]. Numerical examples and a sensitivity analysis are also performed to illustrate the robustness of the proposed control policy and the solution approach.     

Honeynet games: a game theoretic approach to defending network monitors

A honeynet is a portion of routed but otherwise unused address space that is instrumented for network traffic monitoring. It is an invaluable tool for understanding unwanted Internet traffic and malicious attacks. We formalize the problem of defending honeynets from systematic mapping (a serious threat to their viability) as a simple two-person game. The objective of the Attacker is to identify a honeynet with a minimum number of probes. The objective of the Defender is to maintain a honeynet for as long as possible before moving it to a new location within a larger address space. Using this game theoretic framework, we describe and prove optimal or near-optimal strategies for both the Attacker and the Defender. This is the first mathematically rigorous study of this increasingly important problem on honeynet defense. Our theoretical ideas provide the first formalism of the honeynet monitoring problem, illustrate the viability of network address shuffling, and inform the design of next generation honeynet defense systems.     

The optimum traversal of a graph

For a given graph (network) having costs [c_ij] associated with its links, the present paper examines the problem of finding a cycle which traverses every link of the graph at least once, and which incurs the minimum cost of traversal. This problem (called thegraph traversal problem, or theChinese postman problem [9]) can be formulated in ways analogous to those used for the well-known travelling salesman problem, and using this apparent similarity, Bellman and Cooke [1] have produced a dynamic programming formulation. This method of solution of the graph traversal problem requires computational times which increase exponentially with the number of links in the graph. Approximately the same rate of increase of computational effort with problem size would result by any other method adapting a travelling salesman algorithm to the present problem.This paper describes an efficient algorithm for the optimal solution of the graph traversal problem based on the matching method of Edmonds [5, 6]. The computational time requirements of this algorithm increase as a low order (2 or 3) power of the number of links in the graph. Computational results are given for graphs of up to 50 vertices and 125 links.The paper then discusses a generalised version of the graph traversal problem, where not one but a number of cycles are required to traverse the graph. In this case each link has (in addition to its cost) a quantity q_ij associated with it, and the sum of the quantities of the links in any one cycle must be less than a given amount representing the cycle capacity. A heuristic algorithm for the solution of this problem is given. The algorithm is based on the optimal algorithm for the single-cycle graph traversal problem and is shown to produce near-optimal results.There is a large number of possible applications where graph traversal problems arise. These applications include: the spraying of roads with salt-grit to prevent ice formation, the inspection of electric power lines, gas, or oil pipelines for faults, the delivery of letter post, etc.     

On dual power assignment optimization for biconnectivity

Topology control is an important technology of wireless ad hoc networks to achieve energy efficiency and fault tolerance. In this paper, we study the dual power assignment problem for 2-edge connectivity and 2-vertex connectivity in the symmetric graphical model which is a combinatorial optimization problem from topology control technology.The problem is arisen from the following origin. In a wireless ad hoc network where each node can switch its transmission power between high-level and low-level, how can we establish a fault-tolerantly connected network topology in the most energy-efficient way? Specifically, the objective is to minimize the number of nodes assigned with high power and yet achieve 2-edge connectivity or 2-vertex connectivity.We addressed these optimization problems (2-edge connectivity and 2-vertex connectivity version) under the general graph model in (Wang et al. in Theor. Comput. Sci., 2008). In this paper, we propose a novel approximation algorithm, called Candidate Set Filtering algorithm, to compute nearly-optimal solutions. Specifically, our algorithm can achieve 3.67-approximation ratio for both 2-edge connectivity and 2-vertex connectivity, which improves the existing 4-approximation algorithms for these two cases.     

Traffic engineering of tunnel-based networks with class specific diversity requirements

Tunnel-based networks such as Multi-protocol Label switching (MPLS) are suitable for providing diversity guarantees to different service classes or customers. Based on the number of active tunnels to handle, router capabilities can be taxed due to the limited amount of memory and/or processing power of these routers. In this paper, we present a mixed-integer linear program formulation for a traffic engineering problem where such tunnel restrictions are taken into account in addition to standard capacity constraints while addressing diversity requirement of services. Due to large size of the formulation, we also present an accompanied solution approach based on Lagrangian relaxation and sub-gradient optimization. We then present results towards impact of diversity constraint upon the tunneling and capacity restrictions. We observed that the networks having higher amounts of capacity and demands with higher level of survivability are much more sensitive to number of allowed tunnels in the network. The impact is even more prominent for sparsely-connected, large-sized networks.     

Static-dynamic uncertainty strategy for a single-item stochastic inventory control problem

We consider a single-stage inventory system facing non-stationary stochastic demand of the customers in a finite planning horizon. Motivated by the practice, the replenishment times need to be determined and frozen once and for all at the beginning of the horizon while decisions on the exact replenishment quantities can be deferred until the replenishment time. This operating scheme is refereed to as a “static-dynamic uncertainty” strategy in the literature [3]. We consider dynamic fixed-ordering and linear end-of-period holding costs, as well as dynamic penalty costs, or service levels. We prove that the optimal ordering policy is a base stock policy for both penalty cost and service level constrained models. Since an exponential exhaustive search based on dynamic programming yields the optimal ordering periods and the associated base stock levels, it is not possible to compute the optimal policy parameters for longer planning horizons. Thus, we develop two heuristics. Numerical experiments show that both heuristics perform well in terms of solution quality and scale-up efficiently; hence, any practically relevant large instance can be solved in reasonable time. Finally, we discuss how our results and heuristics can be extended to handle capacity limitations and minimum order quantity considerations.     

Inventory Control with a Fixed Cost and a Piecewise Linear Convex Cost

This paper studies the optimal policy for a periodic‐review inventory system in which the production costs consist of a fixed cost and a piecewise linear convex variable cost. Such a cost function can arise from alternate sources of supply or from the use of overtime production. We fully characterize the structure of the optimal policy for the single‐period problem. For the multi‐period problem, the optimal policy can have disconnected production regions and complicated optimal produce‐up‐to levels, which implies that implementation of the optimal policy may not be practical. Fortunately, careful investigation shows that the optimal policy has some interesting properties. The structure of the optimal policy outlined by these properties leads to a practical and close‐to‐optimal heuristic policy. In an extensive numerical study, the average gap is only 0.02% and the worst gap is 1.37%.