Results on schedules, descriptions, separators, lists and boundary invariants, with their assumptions

The course proves the statements below; each link leads to the statement with its assumptions and its proof. The lessons are self-checked by the writing AI; independent mathematical review is not complete.

• Linear extensions — Lemma 1.2. Removing a job without remaining predecessors at each step lists a finite partial order in an order extending it.
• Integer start times suffice — Lemma 1.3. A schedule with real start times on three machines can be replaced by a slot schedule with no larger makespan.
• Padding — Lemma 2.1. A deadline T is feasible exactly when the jobs padded with isolated jobs to 3T have a full schedule.
• Reordering an open interval — Lemma 2.2. Replacing the slots of an open interval by any full schedule of its job set keeps the whole schedule full.
• Three-machine scheduling in polynomial time (OpenAI) — Theorem 3.1. A deterministic algorithm decides every deadline and finds a minimum-makespan schedule of unit jobs with precedence constraints on three machines in polynomial time.
• The family is polynomial — Lemma 2.2. Boolean formulas of at most K leaves in rank, triple and cone tests describe at most C_K N^(3K) sets, listed in polynomial time.
• Soundness — Proposition 3.1. Every set accepted by the dynamic program has a full schedule, assembled along an accepting path of states.
• Hierarchies give acceptance — Lemma 4.2. If a full schedule has a bounded-description hierarchy, the dynamic program accepts all jobs.
• Structure theorem (OpenAI) — Theorem 4.3. Every full schedule has a bounded-description hierarchy whose descriptions have fewer than 500 leaves.
• Jobs before a separator — Lemma 1.2. For a separator z at cutoff S and any H agreeing with S on the domain, P_z together with H minus the weak cone of z describes the jobs before z.
• No improving exchange — Lemma 2.1. In a normalized schedule, after any reordering strictly after a slot, no job there can be exchanged with a later job of better priority.
• One advance — Lemma 3.1. Advancing to the earliest exception keeps every earlier high job below the new slot.
• Shared-cutoff walk (OpenAI) — Lemma 3.3. Promoting one job, the walk from a separator of the old cutoff ends at a position separating both the old and the new cutoff.
• Separators exist — Corollary 3.4. Every cutoff of a set with a full schedule is separated by a slot of some full schedule of the set.
• Cover — Lemma 2.1. Invariant (I1) puts every job of a node in D_a or P_b, in either frame.
• Priority orders of the sides — Lemma 3.1. The same and switched priority orders extend precedence, and their promotions end at the center cutoff.
• Edge labels — Lemma 4.2. A child's low jobs lie in D_a' and P_b, its high jobs in P_b'; children miss the center.
• Suffix carry — Lemma 1.1. A suffix of a list trimmed by a rank threshold selects exactly the qualifiers with key at least the threshold, in the same order.
• The new qualifiers — Lemma 2.1. After a same or switched update, the child's qualifiers are exactly its high jobs, and (I1) holds.
• At most five entries — Lemma 3.2. Surviving injections contain different jobs of a three-job slot, so a list has at most five entries.
• Local flattening — Lemma 1.1. The carried switch pair agrees on later nodes of its run with a two-leaf upset.
• Short extension — Lemma 2.1. The low set of an existing edge extends to a global downset with at most 21 leaves.
• The switch upset — Lemma 3.2. A four-factor upset covers the node's X and contains no job at or before its boundary.
• (I2) for children — Lemma 2.1. Every qualifier scheduled at or before a child's left boundary lies in that boundary's weak predecessor cone.
• (I3) for children — Lemma 3.1. After any reordering of a child, no key-decreasing exchange with its boundary slot gives a full schedule.
• Global child descriptions — Lemma 2.1. A child's high and low jobs are described by bounded formulas on all jobs, without reference to its ancestors.
• Leaf counts — Lemma 4.1. Node descriptions need at most 257 leaves and split descriptions at most 132.
• Running time — Proposition 5.1. With K = 10000 the algorithm runs in O((L+2)^150020) multitape steps.
• Every fixed number of machines — Theorem 1.1. For every fixed m >= 3 one deterministic algorithm decides a deadline for unit jobs with precedence constraints on m identical machines, returns a schedule, and finds the minimum makespan in time O_m((L+2)^(60m^2+129m+2)).
• Lowering one element of an m-set — Lemma 4.1. Replacing an element of a set of m integers by a smaller integer outside the set lowers every order statistic weakly and one strictly, so the sorted tuple decreases lexicographically.
• No improving exchange, m machines — Lemma 4.2. In a lexicographically least schedule of an interval, exchanging a job at a slot with a later job of better priority never gives a full schedule, after any reordering of the later slots.
• At most m injections — Lemma 2.1. A pruned list has at most m injection entries and at most m + 2 entries, because distinct injections are witnessed by distinct jobs of one m-job slot.
• Entry sizes and unions — Lemma 3.4. Every list entry has a formula with at most 3m + 7 leaves, and the union of a list or of a carry has one with at most 6m + 9 leaves.
• Structure theorem on m machines — Theorem 2.2. Every full schedule on m machines has a hierarchy in which every node has a global description of at most 12m + 25 leaves and every mark a relative description of at most 6m + 16 leaves, at every depth.
• Correctness — Theorem 3.1. With a leaf budget of at least 12m + 25 the dynamic program accepts the padded jobs exactly when they have a full schedule, and returns one.
• Running time — Corollary 3.3. For fixed m >= 3 the padded deadline decision takes O_m(N^(60m^2+129m+1)) steps and the minimum makespan O_m((L+2)^(60m^2+129m+2)) steps.

Reading order

Read the lessons in order; the third lesson on separators can be read on its own after the first two. Lessons 9 to 11 extend the proof to every fixed number of machines.