Service system design with immobile servers, stochastic demand and concave-cost capacity selection. (June 2018)

• Record Type: Journal Article
• Authors: Elhedhli, Samir; Wang, Yan; Saif, Ahmed
• Is Part Of: Computers & operations research. Volume 94(2018)
• Page Start: 65
• Page End: 75
• Publication Date: 2018-06
• Subjects: Service system design -- Economies-of-scale -- M/M/1 -- Second-order cone programming -- Special order sets of type 2 (SOS2) -- Lagrangian relaxation; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2018.01.019
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: A general model with continuous capacity and economies-of-scale, modelled using an increasing concave function. A reformulation as a mixed-integer quadratic program with fourth-degree polynomial equality constraints. Two solution methodologies based on linear approximation and Lagrangian relaxation with second-order conic programming subproblems. Abstract: The service system design problem is a location-allocation problem with service quality considerations that is often modeled as a network of M/M/1 queues to minimize facility setup, customer access, and waiting costs. Traditionally, capacity decisions are either ignored or modeled as a selection among discrete capacity levels. In this work, we study the general continuous capacity case and account for economies-of-scale in its cost through an increasing concave function. We focus on the special square-root case that has been shown to model capacity in terms of the number of servers needed under Poisson arrivals and exponential service times. The problem is formulated as a mixed-integer nonlinear program with concave and convex terms in the objective function. Two novel resolution approaches are proposed: In the first, the problem is reformulated as a mixed-integer quadratic program with fourth-degree polynomial equality constraints. These constraints and the quadratic objective function are approximated using piecewise-linear segments. In the second, we use Lagrangian relaxation to decompose the problem and reformulate the subproblems as second-order cone programs that are solved at multiple utilization levels. The Lagrangian multipliers are updated using a cutting-plane method and a feasible solution is obtained by solving the corresponding set-covering formulation. The solution approaches are tested and compared. The linearization approach provides high quality solutions within short computational times for small instances and lower accuracy; whereas the Lagrangian approach scales well as size increases.