Multi-Priority Online Scheduling with Cancellations

Xinshang Wang () and Truong Van-Anh ()
Additional contact information
Xinshang Wang: Department of Industrial Engineering and Operations Research, Columbia University, New York, New York 10027
Truong Van-Anh: Department of Industrial Engineering and Operations Research, Columbia University, New York, New York 10027

Operations Research, 2018, vol. 66, issue 1, 104-122

Abstract: 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.

Keywords: analysis of algorithms; approximations/heuristic; cost analysis (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://doi.org/10.1287/opre.2017.1653 (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:oropre:v:66:y:2018:i:1:p:104-122

Access Statistics for this article

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