Hostname: page-component-7b7567c8c-w7t8q Total loading time: 0 Render date: 2026-11-17T21:45:38.416Z Has data issue: false hasContentIssue false

MYOPIC POLICIES FOR NON-PREEMPTIVE SCHEDULING OF JOBS WITH DECAYING VALUE

Published online by Cambridge University Press:  28 November 2016

Neal Master
Affiliation:
Department of Electrical Engineering, Stanford University, Stanford, California, USA E-mail: nmaster@stanford.edu
Carri W. Chan
Affiliation:
Decision, Risk, and Operations, Columbia Business School, New York, New York, USA E-mail: cwchan@columbia.edu
Nicholas Bambos
Affiliation:
Department of Management Sciences & Engineering and Department of Electrical Engineering, Stanford University, Stanford, California, USA E-mail: bambos@stanford.edu
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

In many scheduling applications, minimizing delays is of high importance. One adverse effect of such delays is that the reward for completion of a job may decay over time. Indeed in healthcare settings, delays in access to care can result in worse outcomes, such as an increase in mortality risk. Motivated by managing hospital operations in disaster scenarios, as well as other applications in perishable inventory control and information services, we consider non-preemptive scheduling of jobs whose internal value decays over time. Because solving for the optimal scheduling policy is computationally intractable, we focus our attention on the performance of three intuitive heuristics: (1) a policy which maximizes the expected immediate reward, (2) a policy which maximizes the expected immediate reward rate, and (3) a policy which prioritizes jobs with imminent deadlines. We provide performance guarantees for all three policies and show that many of these performance bounds are tight. In addition, we provide numerical experiments and simulations to compare how the policies perform in a variety of scenarios. Our theoretical and numerical results allow us to establish rules-of-thumb for applying these heuristics in a variety of situations, including patient scheduling scenarios.

Information

Type
Research Article
Copyright
Copyright © Cambridge University Press 2016