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

Abstract

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.

Keywords:

• Capacity allocation
• Markov decision process
• customer preferences
• curbside pickup
• state aggregation
• order fulfillment

Additional information

Notes on contributors

Melis Boran

Melis Boran received her BS in industrial engineering from Galatasaray University and her MS degree in operations research from Middle East Technical University. She is currently a PhD candidate and a research assistant in industrial engineering department at Middle East Technical University. Her research areas include operations management, control of stochastic systems, and Markov decision processes.

Bahar Çavdar

Bahar Çavdar received her BS in industrial engineering from Middle East Technical University with a minor in computer engineering, and her MS and PhD degree in industrial engineering from Georgia Institute of Technology. She is currently an assistant professor in industrial distribution at Texas A&M University. Her primary research interests are in time-sensitive routing problems and integrating human behavior into classical models in supply chain management/operations management.

Tuğçe Işık

Tuğçe Işık received her BS in industrial engineering from Bogazici University and her MS and PhD in operations research from Georgia Institute of Technology. She is currently an assistant professor in the Industrial Engineering Department at Clemson University, USA. Her research areas include operations planning and control, stochastic processes and optimization, queueing networks, and Markov decision processes, with applications to agile production and service systems.