Multi-Priority Online Scheduling with Cancellations

We study a fundamental model of resource allocation in which a finite amount of service capacity must be allocated to a stream of jobs of different priorities arriving randomly over time. Jobs incur costs and may also cancel while waiting for service. To increase the rate of service, overtime capacity can be used at a cost. This model has application in healthcare scheduling, server applications, make-to-order manufacturing systems, general service systems, and green computing. We present an online algorithm that minimizes the total cost due to waiting, cancellations and overtime capacity usage. We prove that our scheduling algorithm has cost at most twice of an optimal offline algorithm. This competitive ratio is the best possible for this class of problems. We also provide extensive numerical experiments to test the performance of our algorithm and its variants.