The Setting
An instance of three-machine unit-job scheduling on jobs is a list of ordered pairs from .✦ Its edge relation is membership in ✦, and its strict precedence relation is the transitive closure of that relation.✦ A feasible schedule with deadline is an assignment satisfying (1); write for the set of these assignments. (1)✦
For , the padded job set is , where . Its padded precedence relation retains precisely the original precedences, as in (2); the additional jobs are isolated. (2)✦
A layout of is a bijection from the jobs to the zero-based positions .✦ Its slot assignment is (3); the jobs are read in consecutive triples. A full layout of for a relation on is a layout whose job count is divisible by three and whose slots satisfy whenever .✦ Write for the set of full layouts. (3)✦
The Structural Family
The complete solver uses a finite family of job subsets described by precedence cones and rank thresholds. For a relation on and a job , the predecessor count is the number of jobs in that precede under .✦ For a relation on and a job , the canonical rank is the position of in the ordering of jobs by the lexicographic key , as in (4); its reverse rank is . (4)
A job triple is a subset of with cardinality three.✦ For a job triple in and a relation on , the strict predecessor and successor cones and are the sets in (5); the weak cones and include itself. (5)
A frame on consists of a relation on and a rank function . In a frame with rank function , an atomic structural set is or , a rank threshold set or with , or a triple or one of its four cones. Atoms use either the original frame or the reversed frame , where .
A structural formula is a signed atomic leaf, or the conjunction or disjunction of two structural formulas.✦ The value of a structural formula on is a subset of : a negative leaf takes the complement of its atom, and conjunction and disjunction take intersection and union.✦ The leaf count of a structural formula is one for a leaf and the sum of the two counts at a binary operation.✦ For a natural-number parameter , a template is a structural formula with labels in place of atomic sets and with labels available. The effective family is the list obtained by evaluating these templates with depth and leaf count at most , under all assignments of atomic sets to the labels.✦ The parameterized complete solver uses ; its fixed version takes . For job subsets , a relative description of in is an equality with .
The Padded Solver
A schedule block consists of a length and a slot assignment .✦ The empty block is ✦, and the single-triple block is .✦ For , block concatenation is the block in (6). (6)✦
A scheduling state on is an ordered triple of subsets of .✦ A scheduling state is compatible with when partition , is a job triple with no internal precedence, and contains no pair from to or from to .✦ The prefix of a scheduling state is the job subset .✦ Candidate states are , enumerated over the structural family and the list of job triples, then restricted to compatible states.✦ The triple list is obtained by enumerating ordered triples of jobs and retaining their underlying sets when their cardinality is three.✦ Completing or extending a state with blocks gives the block in (7). (7)
A scheduling table on is a list pairing subsets of with schedule blocks on , with lookup returning the first matching entry. Each table construction retains the successful results in enumeration order✦, and every search selects the first successful result.✦ Given a table , initial state markings attach to a state whenever that entry exists. A marking round keeps existing marks. For an unmarked state , it searches the previous round’s marked pairs with and an entry , and attaches when successful.
The subset solver on returns when . Otherwise it performs marking rounds and completes the first marked pair whose right set has an entry , returning . The layer table starts with the single entry ; each successive layer applies the subset solver to the structural family using the previous layer’s table.✦ The complete solver runs layers and looks up , returning a block when an entry exists and failure otherwise.✦
A Boolean matrix of dimension specifies the relation given by .✦ For any target dimension , its padded matrix retains when and , and has zero in every other entry.✦ The padded solver with deadline applies the complete solver to the relation specified by .✦
A uniform implementation computes its specified function using one finite-register program on binary trees for every input dimension.✦ Let and denote the charged running times of the respective uniform implementations. For a running-time function on inputs , a polynomial growth bound of degree in a size parameter is a bound for a constant independent of .✦
The binary serialization of a tree writes a zero for an empty tree and a one followed by the serializations of the head and tail for a pair.✦ Its serialization size is the number of bits in this serialization.✦
A tree register program may leave the store unchanged, clear a register, pair two register values, select a head or tail, or copy a register value. Programs also allow sequencing, branching on whether a register is empty, and looping while a register is nonempty.
The execution cost of a primitive register instruction is one plus the serialization sizes of the overwritten and read values, and leaving the store unchanged costs one. Sequencing adds one to the costs of its two parts, and each branch or loop test costs one.
The Claim
Theorem 1. Let be a precedence instance on jobs and let . For every feasible schedule , (8)✦ If , take and from (2). Then (9)✦ There are constants such that, for every dimension , every Boolean matrix of dimension , and every target dimension , (10)✦ and, for every deadline , (11)✦
In the paper, the result reads: the original deadline is feasible if and only if the padded set has a full schedule, and the padded instance has polynomial size in the stated input encoding.
What Is Checked
The equivalence (9) is stated over finite edge lists under the capacity condition (8); the cost bounds (10) and (11) range over arbitrary Boolean matrices. The execution cost of a uniform implementation is bounded by its charged running time.