Online Advance Scheduling with Overtime: A Primal-Dual Approach

Esmaeil Keyvanshokooh (), Cong Shi () and Mark P. Van Oyen ()
Additional contact information
Esmaeil Keyvanshokooh: Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, Michigan 48105
Cong Shi: Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, Michigan 48105
Mark P. Van Oyen: Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, Michigan 48105

Manufacturing & Service Operations Management, 2021, vol. 23, issue 1, 246-266

Abstract: Problem definition : We study a fundamental online resource allocation problem in service operations in which a heterogeneous stream of arrivals that varies in service times and rewards makes service requests from a finite number of servers/providers. This is an online adversarial setting in which nothing more is known about the arrival process of customers. Each server has a finite regular capacity but can be expanded at the expense of overtime cost. Upon arrival of each customer, the system chooses both a server and a time for service over a scheduling horizon subject to capacity constraints. The system seeks easy-to-implement online policies that admit a competitive ratio (CR), guaranteeing the worst-case relative performance. Academic/practical relevance : On the academic side, we propose online algorithms with theoretical CRs for the problem described above. On the practical side, we investigate the real-world applicability of our methods and models on appointment-scheduling data from a partner health system. Methodology : We develop new online primal-dual approaches for making not only a server-date allocation decision for each arriving customer, but also an overtime decision for each server on each day within a horizon. We also derive a competitive analysis to prove a theoretical performance guarantee. Results : Our online policies are (i) robust to future information, (ii) easy-to-implement and extremely efficient to compute, and (iii) admitting a theoretical CR. Comparing our online policy with the optimal offline policy, we obtain a CR that guarantees the worst-case performance of our online policy. Managerial implications : We evaluate the performance of our online algorithms by using real appointment scheduling data from a partner health system. Our results show that the proposed online policies perform much better than their theoretical CR, and outperform the pervasive First-Come-First-Served (FCFS) and nested threshold policies (NTPO) by a large margin.

Keywords: advance scheduling; online resource allocation; online algorithms; competitive analysis (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
https://doi.org/10.1287/msom.2019.0832 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormsom:v:23:y:2021:i:1:p:246-266

Access Statistics for this article

More articles in Manufacturing & Service Operations Management from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().