The Setting
A precedence instance on indexed jobs is an edge list of ordered job pairs.✦ A scheduling request specifies either a deadline or a search for the minimum makespan when is absent.✦ The accounting concerns the complete computation from the request bits to a schedule listed in job order, or a failure answer.
Write for the request bit string and . The self-delimiting encoding of an integer is a bit string consisting of the binary digits of in order from least to most significant, preceded by as many ones as there are digits and a zero separator.✦ The length-prefixed encoding of a list is the self-delimiting encoding of its length followed by the encodings of its elements in list order.✦ The request begins with a deadline flag and, when present, its encoded value; the remaining lists give the one-based vertex labels and edge endpoints.✦ The binary parser reads these lists, takes the vertex count as , and subtracts one from each edge endpoint, with subtraction truncated at zero.✦ With for a supplied deadline and otherwise, the request size is the measure in (1). (1)✦ A bounded deadline request is a scheduling request with , where is the supplied deadline or zero when the deadline is absent.✦ The binary natural-number parser counts the initial ones, discards them and the following separator, and interprets the next equally many bits as a least significant first binary numeral; it returns that value and the unconsumed bits.✦ Given a parser for individual elements, the binary list parser first reads a natural number giving the list length, then parses that many elements and returns them in input order together with the remaining bits.✦ The binary deadline parser consumes the first bit, treating an absent bit as zero; a one causes it to parse a natural number as the deadline, and a zero gives an absent deadline with the remaining bits.✦
Reachability is computed from by rounds of extension: a round retains current pairs and adds when a current pair can be followed by an edge . For a deadline , the deadline solver returns failure if ; otherwise it pads this relation to a job set of size , with the added jobs unrelated to all jobs. It runs the complete solver, a dynamic program on structural subsets of the padded job set, and restricts the returned time assignment to the original jobs. Without a deadline, minimum makespan search retains the first successful answer among deadlines .✦ The output string is a single zero for failure, or a one followed by the length-prefixed list of self-delimiting schedule times.✦
For arbitrary , a Boolean matrix on the indexed jobs defines the relation by its true entries.✦ Let denote the complete job enumeration. The canonical rank orders jobs lexicographically by predecessor count and index; its reverse rank is specified in (2). (2) An atomic structural set on is a subset of equal to the empty set or , a lower or upper rank threshold at , or one of , , , and for a job triple . Here , and ; the weak cones include . Both working orientations are allowed, reversing the relation and using in the reversed orientation. A Boolean structural formula on is an expression built from signed atomic leaves by conjunction and disjunction, interpreted as intersection and union, with a negative leaf interpreted by complementation. The leaf count of a Boolean structural formula is a nonnegative integer defined recursively as one at a leaf and additively at either connective.✦ For an integer allowance , the structural family on is an enumeration of the sets obtained by substituting all assignments of atomic sets into formula templates of depth and leaf count at most .✦ The complete solver uses .
The job triple enumeration runs over all ordered choices of three jobs from the job list, forms their set and retains it when it has cardinality three, preserving repetitions and enumeration order.✦
A compatible scheduling state for a job set is an ordered partition of in which is an antichain triple and no precedence runs from to , from to , or from to .✦ Candidate states use the relative description in (3) for . (3)✦ A schedule block for a job set is a nonnegative length together with a time assignment to the jobs in .✦ The empty block has length and times zero✦; the single triple block has length and times one.✦ For blocks on and a job set , their concatenation has length equal to the sum of their lengths, assigns each job in its time from , and assigns every other job its time from plus the length of .✦ A subset schedule table on is an ordered list pairing job sets with blocks✦, and a state marking table on is an ordered list pairing scheduling states with blocks.✦ Lookups select the first matching entry✦; successful result tables retain successful evaluations in order.✦
For a target set , the compatible state enumeration forms a candidate state for every pair of a member of the structural family and an enumerated triple, then retains exactly the states compatible with .✦
The subset solver marks each state’s left part from the subset table. A marking can advance to another state when its prefix lies in that state’s left part and the remaining left jobs have a table entry.✦ Block extension concatenates the marked block, its middle triple, and the block for the remaining jobs.✦ Marking expansion retains existing markings and otherwise selects the first successful extension.✦ After expansions, completion appends a block for the right part, taking the first successful result; the empty subset receives the empty block.✦ The initial scheduling layer is the table containing the empty job set paired with the empty block; each next layer applies the subset solver to every member of using the preceding layer as its subset table, retaining successful results in order.✦ The complete solver looks up after layers.✦
Programs and Their Charges
A binary tree datum is a finite tree formed from an empty tree and ordered pairs.✦ The serialization of a binary tree gives the empty tree a zero and a pair a one followed by the two subtree serializations✦; denotes its length.✦ A tree program on finitely many registers is a program built from instructions that do nothing, clear a register, copy a register, select its head or tail, or construct a pair, combined by sequencing, branching on whether a register is nonempty, and looping while a register is nonempty.✦ Head and tail selection both return the empty tree on empty input. A primitive instruction costs one plus the serialization sizes of the overwritten and read values. Sequencing adds one to the component costs; each branch or loop test costs one. A bounded execution of a tree program with budget is an execution of whose cost is at most .✦
A certified tree program for a transformation with charge is a tree program that takes input in its input register, with all other registers empty, and reaches the store containing and in distinct input and output registers, with all other registers empty, at cost at most .✦ A tree data encoding of a set is a map assigning a tree to each value in .✦ A certified implementation of a function is a certified tree program computing on tree data encodings.✦ A uniform implementation of a family of functions indexed by size is an implementation using one transformation and charge for every size index.✦
Write for the tree encoding of bit strings, for the compiled complete solver’s charge, and for the compiled request answer’s charge on its encoded input. The compiled request answer extracts the job count, graph and optional deadline from the scheduling request, constructs the complete job enumeration, computes the reachability matrix, applies the matrix scheduling answer and serializes its result.✦ The compiled parameterized scheduling solver takes the allowance as a parameter. Its specialization at is the compiled complete solver.✦
The compiled request bound is defined by (4). (4)✦ For an input measure , a polynomial growth bound of degree for a function means the uniform domination in (5), with a natural constant independent of the input. (5)✦
A deterministic multitape Turing machine is a machine with finite state and tape alphabets whose transition either halts or gives a new state, a written symbol and an optional head movement on each tape.✦ Its initial configuration has state zero and the input on tape zero, with other tapes blank.✦ Bits zero and one use symbols one and two, leaving symbol zero blank.✦ The run iterates transitions and retains a halted configuration.✦ For a deterministic multitape Turing machine , input bit string , output bit string , and time budget , write when some configuration of the run on input at time at most is halted and the contents to the right of the head on tape zero are followed by blanks.✦
The Claim
Theorem 1. There are constants , independent of the matrix or request, with the following bounds. For every enumerated Boolean matrix input, the compiled complete solver satisfies (6). (6)✦ For every scheduling request, the compiled request answer satisfies (7). (7)✦ For a bounded deadline request, the size comparison is (8). (8)✦ For any certified tree program computing with charge , there is a fixed multitape Turing machine whose production bound for bit strings satisfying is (9). $$\operatorname{Produces}_M\!left( b,o;2000\bigl(c(\iota(b))+|b|+|o|+1\bigr)\right).$$(9)✦ The compiled request bound satisfies (10) for every request and (11) for every bounded deadline request. (10)✦ (11)✦
In the paper, the result reads: sequential-scan all-set processing takes time, and the final allowance, with the input bit length, includes preprocessing and all deadline trials for optimization.
What Is Checked
The bounds concern uniform implementations on size-indexed Boolean matrices and edge-list requests, together with the bounded execution semantics of finite register programs and the halting output semantics of multitape Turing machines.
Binary increment propagates carry through an initial run of ones; iterating it times from the empty string gives the standard binary representation of .✦ The binary numeral evaluation also equals the left fold of the update over the reversed digit list, starting at zero, where a digit has value zero or one.✦
For every nonnegative integer , the tree encoding of equals the tree encoding of the list of copies of the unique element of a one-element set.✦