Multi-Priority Online Scheduling with Cancellations

• 成果类型: Article
• 署名作者: Wang, Xinshang; Van-Anh Truong
• 署名单位: Columbia University
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2017.1653
• 发表日期: 2018
• 页码: 104-122
• 关键词: make-to-order; Approximation algorithms; allocation; management; admission; capacity; policies; surgery; models; QUEUE

摘要

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.