Abstract
This paper addresses the NP-hard problem of scheduling tasks whose value diminishes over time, a scenario common in disaster triage and perishable inventory management. We evaluate three myopic heuristics: Greedy, Rate Greedy, and Earliest Deadline First (EDF). Through mathematical analysis and simulation, we demonstrate that these simple policies offer strong performance guarantees, with Rate Greedy emerging as the most robust strategy in congested systems. We establish that for independent and identically distributed (IID) service times, myopic policies provide a 2-approximation of the optimal reward.
Introduction
In traditional scheduling theory, job values are often treated as static. However, in high-stakes environments such as emergency healthcare, the "reward" for completing a task (e.g., a patient's probability of survival) decays the longer the task remains in the queue. This paper investigates a "clearing system" where a batch of jobs is available at the start, and a limited number of servers must process them non-preemptively. Because the reward for each job decays according to arbitrary functions, finding an optimal schedule is computationally intractable. This research seeks to identify simple, fast algorithms that capture near-optimal value.
Myopic Scheduling Policies
The researchers focus on three "myopic" (short-sighted) heuristics that make immediate decisions without complex look-ahead calculations:
- Greedy Policy ($\pi^G$): Selects the job offering the highest expected immediate reward upon completion.
- Rate Greedy Policy ($\pi^g$): Selects the job with the highest "reward rate" (expected reward divided by expected service time).
- Earliest Deadline First (EDF): Prioritizes jobs whose value will reach zero the soonest.
Modeling Value Decay
To evaluate these policies, the study utilizes various decay models, including linear, exponential, and step-wise functions. These functions represent how a job's potential reward—referred to as an RPM Score in some simulations—diminishes over time increments.
As shown in Figure 1, different initial states (Initial RPM) follow distinct decay trajectories. Some values remain stable briefly before declining, while others drop immediately. The challenge for any scheduling policy is to sequence these jobs to minimize the aggregate loss of value across the entire batch.
Theoretical and Simulation Results
The core contribution of the paper is the establishment of approximation ratios using induction and coupling arguments. These ratios guarantee that a heuristic will achieve at least a specific fraction of the optimal reward, regardless of the specific decay functions.
Key Findings:
- The Robustness of Rate Greedy: The Rate Greedy policy is the most reliable. By considering service time, it prevents the system from being "clogged" by long, high-value jobs that would otherwise allow multiple smaller jobs to decay to zero.
- The EDF Phase Transition: EDF performs exceptionally well when the number of patients is low and service times are nearly constant. However, it exhibits a "phase transition" under congestion; if a few imminent jobs take longer than expected, the policy can lead to a system-wide collapse in value.
- Performance Bounds: For IID service times, both Greedy and Rate Greedy are proven 2-approximations, meaning they will always capture at least 50% of the optimal reward. In non-IID cases, Rate Greedy provides a mathematically tighter performance guarantee than the standard Greedy policy.
Conclusion
Despite their simplicity, myopic policies are often sufficient for practical applications. The Rate Greedy policy, in particular, offers a robust "rule-of-thumb" for managing heterogeneous jobs in congested, time-sensitive environments. Future research will look to extend these proofs to dynamic systems with new job arrivals and stochastic decay functions.
Summary updated