AI summaryⓘ
The authors study how to maximize the number of jobs completed on time when scheduling tasks that have different lengths and importance. They extend known results from a simpler model called interval scheduling to more general cases in real-time, showing that certain weighted problems can be managed well with algorithms that allow stopping and restarting jobs. They also introduce a new model where jobs are announced before they begin, allowing good scheduling without stopping jobs, but only for specific types of job weights. Finally, they show that for unweighted jobs with many different lengths, some limitations on performance exist even with preemption. The work provides bounds and algorithms depending on job length variations.
job throughput maximizationinterval schedulingreal-time schedulingpreemptioncompetitive ratioproportionally weighted jobsC-Benevolent weight functionsadvance notice modelprocessing timedeterministic algorithms
Authors
Allan Borodin, Changdao He, Nadim Mottu
Abstract
Job throughput maximization is the central maximization problem in scheduling. Interval scheduling is the special case of throughput maximization when jobs are intervals and therefore there is no slack available in which to schedule a job. It is interesting to know to what extent results for interval scheduling can be extended to the more general throughput problem in the real-time model. For the unweighted and proportionally weighted throughput problem (where the weight or value $w_i$ of a job $J_i$ is its processing time $p_i$), there are constant competitive real-time scheduling algorithms using preemption with restarting. More generally, the result for proportionally weighted interval scheduling can be extended to C-Benevolent weight functions. We also introduce a new real-time model in which jobs are announced before the actual release time of a job. We show that with sufficient advance notice, we can obtain a constant competitive ratio for proportionally weighted throughput {\it without any preemption}. However, this advance notice result does not extend to arbitrary C-Benevolent and D-Benevolent weight functions. Finally, we show that unlike interval scheduling, unweighted throughput using preemption with revoking admits no constant competitive ratio when the number of distinct processing times is unrestricted. More precisely, for instances with at most $k$ distinct processing times, we give a lower bound of $1/(k+1)$ and a deterministic $1/(2k)$-competitive algorithm.