Myopic policies for non-preemptive scheduling of jobs with decaying value
From MaRDI portal
Publication:4628406
Abstract: 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.
Recommendations
- An approximate dynamic programing approach to the development of heuristics for the scheduling of impatient jobs in a clearing system
- Minimizing the expected waiting time of emergency jobs
- Scheduling Jobs That Are Subject to Deterministic Due Dates and Have Deteriorating Expected Rewards
- Scheduling Deteriorating Jobs on a Single Processor
- Stochastically Minimizing Total Delay of Jobs Subject to Random Deadlines
Cites work
- Dynamic Multipriority Patient Scheduling for a Diagnostic Resource
- Dynamic programming and optimal control. Vol. 2
- scientific article; zbMATH DE number 4087408 (Why is no real title available?)
- scientific article; zbMATH DE number 44282 (Why is no real title available?)
- scientific article; zbMATH DE number 3541843 (Why is no real title available?)
- scientific article; zbMATH DE number 941166 (Why is no real title available?)
- Improved On-Line Broadcast Scheduling with Deadlines
- Introduction to algorithms.
- Inventory models with shelf-age and delay-dependent inventory costs
- Multi-armed bandit allocation indices. With a foreword by Peter Whittle.
- On an index policy for restless bandits
- Scheduling broadcasts with deadlines
- Scheduling Flexible Servers with Convex Delay Costs: Heavy-Traffic Optimality of the Generalized cμ-Rule
- SCHEDULING IMPATIENT JOBS IN A CLEARING SYSTEM WITH INSIGHTS ON PATIENT TRIAGE IN MASS CASUALTY INCIDENTS
- Stochastic depletion problems: effective myopic policies for a class of dynamic optimization problems
- TOPSIS method for hesitant fuzzy multiple attribute decision making
- User Delay Costs and Internal Pricing for a Service Facility
Cited in
(2)
This page was built for publication: Myopic policies for non-preemptive scheduling of jobs with decaying value
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4628406)
