Capacity allocation in service systems with preferred delivery times and multiple customer classes

Motivated by operational problems in click-and-collect systems, such as curbside pickup programs, we study a joint admission control and capacity allocation problem. We consider systems where customers have preferred service delivery times and can be of different priority classes. The service provider can reject customers upon arrival or serve jobs via overtime when service capacity is insufficient. The service provider’s goal is to find the minimum-cost admission and capacity allocation policy to dynamically decide when to serve and whom to serve. We model this problem as a Markov Decision Process and present structural results to partially characterize suboptimal solutions. We then develop a linear programming-based exact solution method using these results. We also present a problem-specific approximation method using a new state aggregation rule to address computational challenges faced due to large state and action spaces. Finally, we develop heuristic policies for large instances based on the behavior of optimal policies in small problems. We evaluate our methods through extensive computational experiments where we vary the service capacity, arrivals, associated service costs, customer segmentation, and order patterns. Our solution methods perform significantly better than several benchmarks in managing the tradeoff between the computation time and solution quality.