UC Irvine

We study the problem of routing jobs in multi-class multi-server queueing systems, where the service rate depends both on the job type and the server type. This queueing setting arises in different applications. For example, in transportation systems, a vehicle's travel time depends on the job's location (e.g., a fire incident's location) and the vehicle's location (e.g., a fire station). In call centers, an agent's service time depends on her skills and the call type that is routed to her.

Chapter I focuses on maximizing the service level of jobs defined as the probability that a job is served within an acceptable waiting time. Service level is an important performance measure for queueing systems. For example, emergency vehicle networks should make sure that the selected server (e.g., a fire engine) arrives at the requester's location within the specified acceptable waiting time. We employ a mathematical programming approach which is desirable since it can easily be embedded within larger planning problems such as determining the optimal location of vehicle hubs and finding the minimum number of vehicles for the desired coverage level. We show that the expected waiting time is convex with respect to its variables, namely, arrival rate and workload. For this reason, the expected waiting time objective is more common in the literature, even though in many applications it is the service level function which is more practical. The service level function, however, is non-convex and requires more advanced methods to solve for optimal or near-optimal solutions. We develop one such advanced method, the Fixed-ratio Shifting Envelopes (FSE) method. Our extensive numerical experiments indicate that FSE outperforms other benchmark algorithms as well as the global solver BARON. In Chapter I, we end our treatment of the subject with the static policy developed for this novel math programming formulation.

Chapter II seeks online (or, real-time) routing policies that answer two questions: (i) Upon a job arrival, to which server group should we assign that job? and (ii) When a server becomes free, which job should the server begin to serve? We point out that the optimal dynamic policy for minimizing the expected waiting time or maximizing the service level is not characterized in the literature. In Chapter II we focus on designing a dynamic policy for the widely-used measure of minimizing the expected waiting time. We develop a math program to model a static variant of our routing problem. Then, we use the solution from our math program to build novel dynamic policies. Our experiments show that one of our proposed overflow dynamic routing policies, which we call FSFOptXOverflowBlock, outperforms Fastest-Server-First, a well-known routing policy for such problems in practice and in the literature. To showcase our methodology, we apply our proposed policy to the problem of assigning fire incidents in Irvine, CA, to fire stations. Methodologically, one could extend this so-called dynamization technique to also construct dynamic policies for the service level maximization problem of Chapter I. We leave the details for future research.