Results for the online setting
The real complexity lies in the online setting, where jobs arrive dynamically and the scheduler must make immediate, irrevocable decisions without knowing what jobs will arrive next. We quantified the performance of an online algorithm via its competitive ratio, which is the worst case comparison between the throughput of our online algorithm and the throughput of an optimal algorithm that is aware of all the jobs apriori.
The standard non-preemptive algorithms fail completely here as their competitive ratio approaches zero. This happens because a single bad decision of scheduling a long job can ruin the possibility of scheduling many future smaller jobs. In this example, if you imagine that each completed job brings equal weight, regardless of its length, completing many short jobs is much more profitable than completing one long job.
To make the online problem solvable and reflect real-world flexibility, we studied two models that allow an active job to be interrupted if a better opportunity arises (though only jobs restarted and later completed non-preemptively count as successful).
Interruption with restarts
In this model, an online algorithm is allowed to interrupt a currently executing job. While the partial work already performed on the interrupted job is lost, the job itself remains in the system and can be retried.
We found that the flexibility provided by allowing job restarts is highly beneficial. A variant of Greedy that iteratively schedules the job that finishes earliest continues to achieve a 1/2-competitive ratio, matching the result in the offline setting.
Interruption without restarts
In this stricter model, all work performed on the interrupted job is lost and the job itself is discarded forever. Unfortunately, we find that in this strict model, any online algorithm can encounter a sequence of jobs that forces it into decisions which prevent it from satisfying much more work in the future. Once again, the competitive ratio of all online algorithms approaches zero. Analyzing the above hard instances led us to focus on the practical scenario where all jobs share a common deadline (e.g., all data processing must finish by the nightly batch run). For such common deadline instances, we devise novel constant competitive algorithms. Our algorithm is very intuitive and we describe the algorithm here for the simple setting of a unit capacity profile, i.e., we can schedule a single job at any time.
In this setting, our algorithm maintains a tentative schedule by assigning the jobs that have already arrived to disjoint time intervals. When a new job arrives, the algorithm modifies the tentative schedule by taking the first applicable action out of the following four actions: