Subject Area
Computer Engineering
Abstract
We propose easy-to-implement heuristics for a problem referred to in the literature as the facility location problem with immobile servers, stochastic demand, and congestion, or the service system design problem. The problem is typically posed as one of allocating capacity to a set of M/M/1 queues to which customers with stochastic demand are assigned with the objective of minimizing a cost function composed of a fixed capacity-acquisition cost, a variable customer-assignment cost, and an expected-waiting-time cost. The expected-waiting-time cost results in a non-linear term in the objective function of the standard binary programming formulation of the problem. Thus, the solution approaches proposed in the literature are either sophisticated linearization or relaxation schemes, or metaheuristics. In this study we demonstrate that an ensemble of straight-forward, greedy heuristics can find high-quality solutions in less than one second of CPU time. In addition to filling the gap in the literature using the heuristic, a noniterating linear model was also developed and the existing iterating linear model was tested using various stopping criteria while also examining the affects of additional constraints on the problem similar to issues being discussed in current literature. In many cases, our heuristic approach finds solutions of the same or better quality than those found with expensive, state-of-the art mathematical programming software, in particular a commercial non-linear MIP solver given a five-minute time limit.
Degree Date
Fall 2022
Document Type
Thesis
Degree Name
Ph.D.
Department
Operations Research and Engineering Management
Advisor
Eli Olinick
Second Advisor
Sila Cetinkaya
Third Advisor
Richard barr
Fourth Advisor
Gheorghe Spiride
Fifth Advisor
Michael Hahsler
Format
Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial 4.0 License
Recommended Citation
Colley, Adam, "Heuristics For Capacity Allocation And Queue Assignment In Congested Service Systems With Stochastic Customer Demand And Immobile Servers" (2022). Operations Research and Engineering Management Theses and Dissertations. 21.
https://scholar.smu.edu/engineering_managment_etds/21
