The Setting
A three-machine unit-job schedule assigns each job a positive integer slot, puts at most three jobs in a slot, and assigns a smaller slot to every predecessor. Let be a precedence relation on a finite job set . A schedule block on is a pair consisting of a length and a time assignment .✦ The family of valid full blocks for is defined by (1): (1)✦ The empty block has length zero and assigns zero everywhere✦; the single-triple block has length one and assigns one everywhere.✦ Concatenating two blocks adds their lengths, keeps the first assignment on its designated job set, and shifts the second assignment by the first length on all other jobs.✦
Structural Sets and Tables
A job triple is a subset of of size three.✦ The predecessor and successor cones of a job triple in are the sets and ; the weak cones of include . A boundary is a triple or either endpoint.✦ The left endpoint has empty predecessor cones and universal successor cones, and the right endpoint has universal predecessor cones and empty successor cones.
For an indexed job set with , the canonical rank of a job is its position when jobs are ordered by predecessor count, breaking ties by job index.✦ The two ranks in (2) describe the original and reversed working frames: (2) In a reversed working frame precedence is reversed as well. Structural atoms are the empty and universal sets, upper and lower rank thresholds with , and the five sets in either frame. A Boolean structural formula is an expression formed from signed structural atoms, conjunction and disjunction, interpreted as complementation, intersection and union. The leaf count of a Boolean structural formula is the number obtained by assigning one to each leaf and adding the counts across either binary operation.✦ Fix . The structural family enumerates the sets obtained from all formula templates of depth at most and at most leaves under all assignments of structural atoms to their available labels.✦ A relative description of in is an expression with a globally described set from the structural family .
Structural acceptance at depth is defined for any family of atomic sets. At every depth the accepted set must have a description with at most leaves. At depth zero it must be empty. At depth , a nonempty set must admit a possibly empty chain of compatible scheduling states in which the prefix jobs of each state are contained in the left region of the next, and whose initial left region, terminal right region and intervening gaps are accepted at depth .
A scheduling state for is compatible when these sets partition , has three jobs with no precedence within it, and precedence never goes from to , from to , or from to .✦ Candidate states have the form in (3), with and in a supplied list ; only compatible candidates are retained: (3) A block table is an ordered list of pairs , where is a job set and is a schedule block.✦ A block table is valid, written , when every stored block belongs to for its paired job set .✦ Lookup returns the first matching entry✦, and a successful-result table retains just the successful evaluations in their original order.✦ The prefix jobs of a state are its left and middle jobs together, denoted by in (3).✦
A marked state is a scheduling state together with a candidate block for its left region . Initial markings use lookup in . Let and be scheduling states. A marking at can extend to when and the table contains a block for ; the extension concatenates the marked block, the triple of , and that gap block.✦ Each marking expansion retains existing markings and otherwise takes the first successful extension.✦ The subset solver returns the empty block for empty ; otherwise, after expansions, it takes the first marked state whose right region has a table entry and completes its block through its middle triple and right region.✦ Failure is denoted by .
The layer table contains only the empty set and empty block. The table retains the successful subset-solver results for members of , using . The complete solver looks up in , using the structural family just defined and the enumeration of all job triples for .✦
Requests and Computation
A precedence instance on original jobs is an edge list .✦ Its reachability relation is obtained from the listed edges by repetitions of the operation that retains known pairs and appends one listed edge to each known path.✦ For a deadline satisfying , the deadline solver pads to with jobs, gives added jobs no precedence links, runs the complete solver on the padded reachability relation, and restricts a returned assignment to the original jobs. It returns failure when . Without a supplied deadline, the makespan search tests positive deadlines in increasing order through and retains its first successful answer.✦
A request consists of an instance and an optional deadline.✦ Write for its input bit string and for the algorithm’s output bit string. An integer whose binary word is is written ✦, and a list is prefixed by its encoded length.✦ The input begins with a bit recording whether the deadline is present and, when present, its integer representation; it then lists the one-based job labels and the endpoint pairs in .✦ The output is a zero bit for failure, or a one bit followed by the list of assigned slots in job index order.✦ The input length and request measure are those in (4), where is the supplied deadline or zero when absent: (4)
A tree routine computing a transformation with charge is a program on finitely many registers holding binary trees, with distinct input and output registers. Its instructions clear, copy or pair register contents, or select a subtree, and combine by sequencing, branching on nonemptiness and looping while a register is nonempty. Starting with in the input register and all other registers empty, it terminates at cost at most with retained in the input register, in the output register and every other register empty. The binary serialization of a tree is a zero bit for the empty tree, or a one bit followed by the serializations of its two subtrees in order for a pair. Primitive operation costs include one plus the serialization sizes of the overwritten and read values; sequencing, branching and loop tests also have their specified unit charges. A uniform routine uses one program for every input size.✦ Let and be the charged running times of the compiled complete solver on a Boolean relation matrix and of the compiled request-answer routine. For an arbitrary uniform routine , write for its charge.✦ Polynomial bounds here have one multiplicative constant for all inputs. Define the raw request bound by (5): (5)✦
For a deterministic multitape Turing machine , the notation means that the machine halts with at and to the right of the head on tape zero, followed by blanks; denotes that halting time.✦ Initially tape zero contains and every other tape is blank.✦
The Claim
Theorem 1. Let be finite and a precedence relation. For any atom family and any set structurally accepted at depth , (6)✦ Given a valid table , arbitrary lists , and a successful result , (7)✦ For arbitrary lists and every layer index , (8)✦ For an indexed job set and any successful result , (9)✦ The compiled routine charges satisfy (10) for every Boolean relation matrix on jobs and (11) for every request : (10)✦ (11)✦ For every uniform routine computing , there is a single deterministic multitape Turing machine with fixed finite tape, state and symbol sets such that (12) holds for every request : (12)✦ For requests with , the bound in (5) satisfies (13): (13)✦
In the paper, the result reads: the specified algorithm is uniform, deterministic and polynomial-time, returns a full schedule for every accepted set, and, with , decides deadline feasibility and constructs schedules in deterministic multitape steps.
What Is Checked
The scheduling assertions concern finite relations and the full-block conditions in (1); the computational assertions concern the request measure in (4), charged execution of uniform tree programs, and halting output on tape zero. The compiled complete solver returns the result of when is the relation specified by its Boolean input matrix, and the compiled request routine returns for every request , using one program for all input sizes in each case.