Design And Optimization Of Service System Resource Allocation

In the course of the recovery and development of the service industry,the challenges encountered by service systems are increasingly complex and diverse.The potential issues arising from resource allocation in current service systems,as well as the ever-evolving demands of customers,have prompted the optimization of resource allocation models in complex scenarios.Furthermore,the widely used principle of assigning customers with consecutive service rates into the same queue are lacking in sufficient theoretical foundations,which necessitates the enrichment and refinement of the underlying theory.In light of these considerations,this study investigates the design and optimization of resource allocation in service systems from both micro-operational decision-making and macro-strategic decisionmaking perspectives.In Section 3 and 4,we investigate the optimization problem of resource allocation at each service point from the perspective of micro-operational decision-making.We study an optimal partition and assignment problem for an uncapacitated FCFS queueing system with heterogeneous types of customers.Each type of customer is associated with a Poisson arrival,a certain service time distribution,and a unit waiting cost.The decision maker can partition the server into sub-queues,each with a smaller service capacity,and can also route each type of customer to the sub-queues with a typespecific probability distribution.The objective is to minimize the expected total waiting cost.We first consider a simplified case where the service time follows an exponential distribution and unit waiting costs are identical.We show that by properly partitioning the queue,it is possible to reduce the expected waiting time of customers,and there exist a series of instances such that the reduction can be arbitrarily large.Then we consider four settings of this problem,depending on whether the partition is given(thus only assignment decision is to be made)or not and whether each type of customers can only be assigned to a unique queue or can be assigned to multiple queues in a probabilistic manner.When the partition is given,we show that this problem is NP-hard in general if each type of customers must be assigned to a unique queue.When the customers can be assigned to multiple queues in a probabilistic manner,we identify a structure of the optimal assignment and develop an efficient algorithm to find the optimal assignment.When the decision maker can also optimize the partition,we show that the optimal decision must be to segment customers deterministically based on their service rates,and to assign customers with consecutive service rates into the same queue.Efficient algorithms are also proposed in this case.We then consider the case where the service time follows a general distribution.We show that for any given partition,the optimal assignment admits a certain geometric structure,which enables us to develop an efficient algorithm to find the optimal assignment.Such an optimal structure also applies where we aim to minimize the expected sojourn time.Numerical results suggest that the proposed strategy outperforms the common rule of thumb.Finally,we consider the joint partition-assignment optimization problem.The assignment under the optimal partition admits stronger structures.For example,if the first two moments of the service time distributions satisfy certain properties,e.g.,exponential distributions,half-normal distributions or Rayleigh distributions,it is optimal to deterministically assign customer types with consecutive products of cost per unit waiting time and service rate to the same sub-queue.The stronger structure enables us to develop more efficient algorithms to solve the joint partition-assignment optimization problem.In Section 5,we approach the design and optimization of the service point distribution structure from the macro-strategic decision-making perspective based on a facility location model.We first establish a two-stage robust facility location framework with marginal information based on the characteristics of actual demand data.Subsequently,taking into account the uncertainty of spatiotemporal demand and the impact of queue congestion on service points,we study the robust facility location problem with customer queues in a time-space network and devise effective constraints and column generation algorithms.Finally,we illustrate the effectiveness of the algorithms on both simulated data and spatiotemporal population movement trajectory data in four cities in China.Overall,the common rule of thumb to partition customers into two continuous segments ranked by their service rates is suboptimal,and our work is the first to comprehensively study the queue partition problem based on customer types.The facility location algorithm that we have designed in the time-space network with marginal information has the potential to provide a feasible guidance solution for the challenging issue of service system resource allocation in practice.