OctoInformBeta

Polynomial-time scheduling on three identical machines

An instance is an explicitly listed directed acyclic graph whose n≥1n\ge1 vertices are jobs to be run on three identical parallel machines. Each job runs for one unit of time without interruption. A feasible schedule assigns each job a positive integer completion time so that at most three jobs have any one completion time and every precedence edge points from an earlier job to a later job. The makespan is the greatest completion time. Given an integer deadline TT with 1≤T≤n1\le T\le n, deadline feasibility asks whether a feasible schedule has makespan at most TT. The optimization problem asks for a feasible schedule of minimum makespan. Let LL denote the total binary input length.

For two machines, Coffman and Graham gave an algorithm that constructs a schedule of minimum makespan. Ullman proved NP-completeness when the number of machines is part of the input. For three machines, Nederlof, Swennenhuis, and Węgrzycki obtained an exact algorithm with running time 2O(nlog⁡n)2^{O(\sqrt n\log n)}.

The preprint proves that deadline feasibility is decidable by a fixed deterministic multitape Turing machine in O((L+2)150020)O((L+2)^{150020}) steps. It also proves that an optimal schedule can be constructed within the same bound.

Lean has checked every result of the Lean library Scheduling, so the Lean library is the reference for the statements on these pages. The correctness theorem of the Lean library takes nonemptiness and acyclicity of the input as hypotheses. Each result on these pages is stated as in the Lean library and linked to its Lean declaration. Where the preprint states a result differently, the Lean library’s statement is given with the preprint’s beside it. The preprint is a guide only to the order and names of the results.

The Lean library: Scheduling

Scheduling is a Lean library: 33 items, in nine groups. Each has a page written by OctoInform, listed below.

§1. Introduction 2 items
  1. §1 (setting): the explicit scheduling problem and machine model Scheduling requests and their correct answers.
  2. Theorem 1.1 Polynomial time for three-machine scheduling.
§2. Full schedules, frames, and descriptions 5 items
  1. §2 (setting): full schedules, reachability, intervals, and the two frames Full schedules and their reversed layouts.
  2. Lemma 2.1 Feasible deadlines admit full padded schedules.
  3. Lemma 2.2 Feasible interval reorderings preserve precedence feasibility.
  4. §2 (setting): the fixed family of Boolean descriptions Boolean formulas describe sets of jobs.
  5. Lemma 2.3 Bounded descriptions have polynomial enumerations.
§3. The algorithm and its structural certificate 4 items
  1. §3 (setting): compatible states, accepted sets, and Definition 3.2 Recursive acceptance and scheduling layers.
  2. Proposition 3.1 Recursive acceptance yields full scheduling blocks.
  3. Lemma 3.3 Recursive certificates enter the scheduling table.
  4. Theorem 3.4 Full layouts yield recursive structural acceptance.
§4. Separators with a shared cutoff 5 items
  1. §4 (setting): Definition 4.1 and lexicographic normalization Separators constrain jobs across a cutoff.
  2. Lemma 4.2 Separators describe the jobs before a cutoff.
  3. Lemma 4.3 Normalized layouts exclude feasible improving exchanges.
  4. Lemma 4.4 Advancing to a shared priority separator.
  5. Corollary 4.5 Rearranging full schedules to separate ideals.
§5. The interval construction and its invariants 2 items
  1. §5 (setting): global lists, keys, and the three invariants Global priorities constrain interval exchanges.
  2. Lemma 5.1 Edge certificates yield smaller child intervals.
§6. Short global lists and changes of direction 8 items
  1. Lemma 6.1 Suffix carry preserves list priorities.
  2. Lemma 6.2 Lifting key comparisons from a pruned list.
  3. Lemma 6.3 List updates select and order high jobs.
  4. Lemma 6.4 Boundary bounds for pruned global lists.
  5. Lemma 6.5 Certified flattening preserves a window union.
  6. Lemma 6.6 Short global extensions of carried cutoffs.
  7. Lemma 6.7 Cutoffs for a change of direction.
  8. Lemma 6.8 Run certificates bound global entry descriptions.
§7. Preserving the global boundary invariants 3 items
  1. Lemma 7.1 Child updates preserve the past boundary invariant.
  2. Lemma 7.2 Exchange constraints persist in child windows.
  3. Proposition 7.3 Structural certificates persist through recursive scheduling.
§8. Global interval predicates and completion 3 items
  1. Lemma 8.1 Interval parts have global cone descriptions.
  2. Lemma 8.2 Certified edge prefixes have bounded descriptions.
  3. Lemma 8.3 Structural predicates have bounded formula size.
§9. Running time in the explicit input model 1 item
  1. §9 (proof of Proposition 3.1 and Theorem 1.1): uniform machine accounting Uniform compilation gives polynomial scheduling time.

No item matches.