Online Advance Scheduling with Overtime: A Primal-Dual Approach

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.

Automated summary

The study focuses on an online resource allocation problem in service operations, proposing new online algorithms with theoretical competitive ratios. Through empirical research on appointment scheduling data from a partner health system, the practical applicability of the methods and models is validated.