Sample-Path Exact Algorithm for Resource Allocation in Queueing Systems with Performance Constraints

Resource allocation problems with performance constraints (RAP–PC) are a category of optimization problems on queueing system design, widely existing in operations management of manufacturing and service systems. RAP–PC aims at finding the system with minimum cost while guaranteeing target performance, which usually can be obtained only by simulation due to complexity of practical systems. This work considers the optimization of the integer–ordered variables, which the system performance is monotonic on. It proposes an algorithm providing a sample–path exact solution within finite time. Specifically, the algorithm works on the mathematical programming model of RAP–PC and uses logic– based exact and gradient–based approximate feasibility cuts to define and reduce the feasible region. Results on randomly generated instances show that the proposed approach can solve at optimality up to 9–dimension problems within two hours and feasible good quality solutions can be found faster than the state–of–the–art algorithm.