Second-Order Cone Optimization Formulations for Service System Design Problems with Congestion
We consider the service system design problem with congestion. This problem arises in a number of practical applications in the literature and is concerned with determining the location of service centers, the capacity level of each service center, and th
- PDF / 517,731 Bytes
- 24 Pages / 439.37 x 666.142 pts Page_size
- 81 Downloads / 156 Views
Abstract We consider the service system design problem with congestion. This problem arises in a number of practical applications in the literature and is concerned with determining the location of service centers, the capacity level of each service center, and the assignment of customers to the facilities so that the customers demands are satisfied at total minimum cost. We present seven mixed-integer second-order cone optimization formulations for this problem, and compare their computational performances between them, and with the performance of other exact methods in the literature. Our results show that the conic formulations are competitive and may outperform the current leading exact methods. One advantage of the conic approach is the possibility of using off-the-shelf state-of-the-art solvers directly. More broadly, this study provides insights about different conic modeling approaches and the significant impact of the choice of approach on the efficiency of the resulting model. Keywords Service systems · Congestion · Second-order cone optimization · Mixed-integer optimization
1 Introduction We consider the service system design problem with congestion. In this problem, one has m different potential locations, and in each location there is a set of possible service capacities to satisfy incoming demand. We refer to those as service centers and their capacities are determined by the type of servers installed in each of them. J. C. Góez (B) Department of Business and Management Science, NHH Norwegian School of Economics, Bergen, Norway e-mail: [email protected] M. F. Anjos Canada Research Chair in Discrete Nonlinear Optimization in Engineering, GERAD & Polytechnique Montreal, Montreal, QC, Canada e-mail: [email protected] © Springer Nature Switzerland AG 2019 J. D. Pintér and T. Terlaky (eds.), Modeling and Optimization: Theory and Applications, Springer Proceedings in Mathematics & Statistics 279, https://doi.org/10.1007/978-3-030-12119-8_5
97
98
J. C. Góez and M. F. Anjos
We assumed that for all service centers, there are n different types of possible servers, and the service times for those servers are assumed to have exponential distributions. The cost of opening a service locations depends both on the location and the service capacity chosen. Additionally, there is a set of locations where the costumers’ demand is originated, we refer to those as demand sources. We assume that every demand source may be served from any potential service center, and the cost of serving a demand source will depend on which service center is assigned to it. Also, we assume the orders generated at any demand source follows a Poisson process. The stochasticity both in the service facilities and the demand sources leads to a probability that the orders arriving to a service center will have to enter into a waiting queue, which will create congestion in the system. There is a cost per unit of time an order has to wait in the system before service. Hence, one has to decide which service facilities to open, with whi
Data Loading...
