A simpler competitive analysis for scheduling equal-length jobs on one machine with restarts

摘要

We consider the online problem of scheduling jobs with equal processing times on a single machine. Each job has a release time and a deadline, and the goal is to maximize the number of jobs completed by their deadlines. Chrobak et al. (2007, SICOMP 36:6) introduce a preempt-restart model in which progress toward completing a preempted job is lost, yet that job can be restarted from scratch. They provide a 3/2-competitive deterministic algorithm and show that this is the optimal competitiveness. Their analysis is based on a complex charging scheme among individual jobs and the use of several partial functions and mappings for assigning the charges. In this paper, we provide an alternative proof of the result using a more global potential argument to compare the relative progress of the algorithm versus the optimal schedule over time. This new proof is significantly simpler and more intuitive that the original, and our technique is applicable to related problems.