Greedy Minimization of the Number of Late Tasks: Implementation and Analysis

Abstract

We study the classical single-machine deadline problem $1 \mid\mid \sum U_j$, in which each task has a deadline and an execution requirement and the goal is to select as many on-time tasks as possible. The standard Moore-Hodgson algorithm processes tasks by deadline and may later delete a previously accepted task. We study the insertion-only shortest-job-first rule of Lin and Wang: process the tasks in nondecreasing execution requirement, and accept a task exactly when doing so preserves feasibility. We give a direct $O(n\log n)$-time implementation using a balanced augmented BST keyed by deadline. Unlike the previous $O(n\log n)$ implementation of this SJF rule, our implementation needs neither a preëmptive schedule nor an amortized analysis of interval changes. Our analysis gives an explicit threshold form of the rule's lexicographic (\emph{lex-first}) optimality: for every threshold~$e$, its outputs maximize the number of selected tasks whose execution requirement is at most~$e$. The analysis also reveals additional combinatorial structure. After the shorter tasks have been greedily fixed, the feasible choices within a single execution-requirement tier form a nested matroid. These tier matroids assemble, as a direct sum, into an overall laminar matroid whose bases are exactly the greedy outputs. Finally, a flow network encoding the deadline-prefix constraints gives a polymatroid rank function for the underlying scheduling feasibility structure. This flow view also recovers the nested matroids that govern the equal-execution tiers.