The Setting
A scheduling algorithm that describes candidate job subsets by Boolean formulas needs a finite list of candidates and a bound on the cost of producing it. The relevant formulas use rank thresholds and cones of precedence around triples of jobs. Their allowance counts leaves, including repeated occurrences of an atom.
Let be a finite job set of size , with precedence relation . In a padded three-machine scheduling instance, for the deadline . A job triple is a set of three jobs.✦ For a relation on and a job triple , the predecessor cone , successor cone , and weak cones and are the subsets of defined in (1). (1) A scheduling boundary is a left endpoint, a job triple, or a right endpoint.✦ At the left endpoint both predecessor cones are empty and both successor cones are ; at the right endpoint these conventions are reversed.
For two rank functions , a working orientation selects the relation and rank in (2). (2) An atomic structural predicate is a Boolean constant, a rank threshold, or one of the five triple sets in (3), with either working orientation.✦ Its interpretation assigns the indicated subset of to the atom. (3)✦ For a job list , the triple enumeration lists the sets obtained from ordered choices of three entries of , retaining those of cardinality three.✦ The structural alphabet lists both constants, all thresholds, and all five cone kinds for every listed triple, in both orientations.✦ Repetitions in these lists are retained. Write for the list of job indices , and .
Formulas and Their Enumeration
A Boolean structural formula over an atom set is an expression consisting of a signed atom of , or a conjunction or disjunction of two Boolean structural formulas over .✦ For a Boolean structural formula over and an assignment of subsets of to atoms in , the interpretation is a subset of and the leaf count is an integer, both defined by (4); complements are relative to . (4) A set has a description with leaf allowance under when it belongs to the collection in (5). (5)✦ The finite interpretation of a Boolean structural formula under an assignment is the finite job set obtained by performing the operations of (4) on finite job sets.✦
For an alphabet list of atoms in , the bounded-depth enumeration is a list of Boolean structural formulas over , defined recursively; at depth zero it is empty. At depth it lists both signs of every entry of , followed by both binary connectives applied to every ordered pair from . Write . The template list is the sublist in (6), with enumerated in increasing order. (6)✦ The assignment list lists every function obtained by choosing an entry of at each index, retaining repetitions.✦ For a template and an assignment , the substituted formula is the formula obtained by replacing each index in by without changing signs or connectives.✦
The formula family and the effective structural family are the lists in (7), ordered first by assignment and then by template. (7) Here finite atomic interpretation selects from exactly the jobs satisfying the atom.✦
The Uniform Implementation
A Boolean adjacency matrix on jobs is a function ✦; its relation satisfies exactly when .✦ For a key function on the job indices with values in a linearly ordered set, the rank function orders jobs by according to (8). The canonical key pairs a job’s predecessor count with its index, ordered lexicographically.✦ (8)
A binary tree is empty or an ordered pair of binary trees.✦ A tree encoding of a set of values assigns a binary tree to each value.✦ For fixed tree encodings of its input and output values, an implementation of a function is a finite register program that, on the encoding of each input , returns the encoding of within a specified charge.✦ Execution starts with all other registers empty and ends with the input preserved, the result in a distinct output register, and all remaining registers empty. The serialization size of a binary tree is one for the empty tree and one plus the two subtree sizes for a pair.✦ Primitive instructions charge one plus the sizes of the values read or overwritten; sequencing and control tests each charge one. An implementation of a family of functions is uniform when one finite register program and one charge function apply at every index, sending each encoded input to the encoded value of the corresponding function.✦ The binary serialization of a tree is the word consisting of a zero for an empty tree, or a one followed by the serializations of the first and second subtrees for a pair.✦
The compiled atomic set enumeration returns the finite interpretations of under .✦ Compiled assignment enumeration lists the assignments ✦, and compiled template evaluation returns the finite interpretations of a supplied template list under a supplied assignment.✦ The compiled structural family enumeration is a uniform implementation returning from the list of all job indices and .✦ Denote its running time charge by , and fix for the cost bound. The compiled predecessor count routine takes the universe listing, a Boolean adjacency matrix , and a job , and returns the number of jobs preceding under .✦ The compiled predecessor count vector routine takes the universe listing and and returns the function assigning each job its predecessor count under .✦ For a supplied count function and job , the compiled count based ranking routine uses the universe listing to return one plus the number of jobs with smaller count, or equal count and smaller index.✦ The compiled job ranking routine takes the universe listing and and returns the canonical job rank function .✦ The compiled rank reversal routine takes the universe listing and a rank function and returns the function .✦ The compiled forward or reverse ranking routine takes the universe listing and and returns in the original orientation and in the reversed orientation.✦ For a supplied rank function , the compiled rank threshold set routine uses the universe listing to enumerate either all sets or all sets , for .✦ The compiled rank threshold enumeration takes the universe listing and and lists the lower threshold sets followed by the upper threshold sets for every , using in the original orientation and in the reversed orientation.✦ For a chosen orientation and a list of cone kinds, the compiled cone enumeration takes the universe listing and and lists the corresponding finite cone sets for every enumerated job triple, ordered first by cone kind and then by triple.✦
The Claim
Theorem 1 (Lemma 2.3). For an alphabet list containing every atom and any set interpretation of those atoms, membership has the characterization (9) for every allowance and job set . (9)✦ For any alphabet list, the list length is given by (10), counting repetitions. (10)✦ The structural alphabet on all job indices satisfies (11). (11)✦ Let be a decidable relation on finite , let be rank functions, and let contain every job. For a set with a description of at most leaves under , its finite job set satisfies (12). (12)✦ For every job list , the effective family has the length in (13). (13)✦ At allowance , a constant independent of and gives the uniform bound (14) for every and Boolean adjacency matrix . (14)✦
In the paper, the result reads: the family can be generated deterministically in polynomial time and represented by -bit vectors.
What Is Checked
The set enumeration statements concern alphabet lists and finite job universes with supplied relations and rank functions; their completeness assertions require the relevant lists to contain every atom or every job. The running time statement concerns the uniform compiled program on a universe listing and an arbitrary Boolean adjacency matrix, with the canonical ranks of (8).