The Setting
Three identical machines can execute at most three unit-length jobs in each time slot. Precedence constraints require a job to finish before any of its successors starts. The optimization problem asks for the smallest number of slots; a deadline request asks whether a prescribed number suffices.
A precedence instance on jobs is an explicitly listed directed graph with job set and edge list .✦ The edge relation of a precedence instance with edge list is the relation that holds between two jobs exactly when their ordered pair belongs to the list. A precedence instance is acyclic when no job has a nonempty directed path back to itself.✦ A feasible schedule for with deadline is a map satisfying (1)✦ The conditions in (1) apply to every job, time slot and listed edge, respectively.
A request consists of an instance and either a nonnegative integer deadline or the symbol , which requests optimization.✦ A binary answer is a correct output for the instance and request , written , when it has the following meaning: for , it gives the slot list of a feasible schedule whose deadline is minimum among all feasible schedules; for , it gives a schedule satisfying (1), or reports infeasibility exactly when no such schedule exists.✦
The Scheduling Procedure
The reachability relation used by the scheduling procedure is the relation obtained from the edge list by reachability extensions.✦ With the set of listed edges, these extensions are (2) For a deadline with , the padded job set is , where ; the padded relation retains on the original jobs and leaves all added jobs isolated.✦ The deadline solver applies the full scheduling solver to this padded relation and restricts a returned time assignment to ; it returns failure when .✦
A job triple is a three-element subset of .✦ The canonical rank of a job orders jobs by the lexicographic key consisting of their predecessor count and their numerical label.✦ The reverse rank is defined by (3)✦ The two working frames use and the reversed relation with from (3), respectively.
For a boundary triple , its strict predecessor cone consists of jobs preceding some member of , and its strict successor cone consists of jobs following some member of . The weak predecessor and successor cones and of a boundary triple are the subsets of obtained by adjoining to its strict predecessor and successor cones, respectively. A boundary may also be a fictitious left or right endpoint: their predecessor cones are , respectively, and their successor cones are ; the weak cones have those same endpoint values.
For a working frame , write for in the original frame and in the reversed frame. An atomic structural set is a constant set or , a rank threshold or with , or one of in either working frame . A structural formula is an expression formed from atomic sets or their complements by intersection and union.✦ The size of a structural formula is its number of leaves, counting each occurrence separately.✦ The effective structural family is the list of sets obtained by substituting atomic sets into formula templates with at most leaves, where ; the templates are enumerated up to depth , and the atom assignments range over all choices at labeled positions.✦
A scheduling state on a subset is compatible when its parts partition , its middle part is a triple of mutually incomparable jobs, and no precedence points from to or from to .✦ The prefix of a scheduling state is the union of its left and middle parts. The candidate states are (4)✦ filtered by compatibility, with ranging over the enumerated job triples.
A schedule block on consists of a nonnegative length and a time assignment .✦ Concatenating blocks and on with first job set adds their lengths and assigns on , and elsewhere.✦ The empty block has length and times zero; the one-slot triple block has length and times one. A state extends a block for its left part by its middle triple and a further block; finishing a state uses this same concatenation.
The subset solver uses a table of previously obtained blocks. Its initial markings attach the table’s block for to each compatible state for which that block is present. A marking can extend to a state whose left part contains the marked state’s prefix, using a table block for the intervening difference.✦ Each expansion retains an existing marking or takes the first successful extension.✦ After expansions, the solver takes the first marked state whose right part has a table block and finishes that state; the empty subset receives the empty block.✦ Scheduling layers begin with the empty-subset entry and repeatedly tabulate successful subset solutions for using the preceding layer.✦ The full solver returns the entry for after layers.✦
The minimum makespan search tests deadlines in increasing order and retains its first success.✦ Write for the procedure’s binary output: the deadline solver supplies the answer when , and the minimum makespan search supplies it when .✦
Binary Requests and Computation
The input word starts with for an optimization request or with followed by the encoded deadline for a deadline request, then gives the explicitly listed job labels and the edge list with one-based endpoints.✦ A natural number is written as a binary numeral preceded by its length in unary and a zero; each list is prefixed by its length in that same integer format. The input length is . A failure answer is the single bit ; a schedule answer begins with and then gives its length-prefixed slot list.✦
A deterministic multitape Turing machine has a fixed finite number of tapes and fixed finite state and symbol sets. Its transition reads the current control state and the symbols under the heads, selects a new control state, writes a symbol on each tape and optionally moves each head; an undefined transition halts. The initial configuration has state zero, input on tape zero and all other tapes blank.✦ Successive configurations follow the transition, with a halted configuration retained thereafter.✦ Write for the number of transitions before halting and for the binary word on tape zero from its head to the right, followed by blanks, at that time.
The Claim
Theorem 1 (Uniform polynomial scheduling guarantee). For acyclic precedence instances on at least one job and for optimization requests or deadlines between one and the number of jobs, a fixed deterministic multitape Turing machine and a positive integer give the following guarantee. Write for the instance on jobs, and let be either or a deadline with . For the request , the machine halts with the guarantee (5)✦
In the paper, the result reads: for an explicitly listed finite directed acyclic graph specifying precedence constraints on nonpreemptive unit-length jobs on three identical machines, a uniform deterministic algorithm constructs a feasible schedule of minimum makespan and, given an integer deadline , decides feasibility exactly and returns a schedule on affirmative instances, with both tasks taking deterministic multitape Turing-machine steps, where is the total binary input length.
What Is Checked
The guarantee in (5) is stated over explicitly listed acyclic graphs with at least one job, the binary request and answer formats, and the halting output of a single finite multitape machine.
Theorem 2 (Correctness of the scheduling procedure). Let be an acyclic precedence instance on jobs. For every request , the procedure’s output satisfies (6): (6)✦
For the compiled request-answer routine, let denote its operation charge on request . Its raw time bound is the function (7)✦ A function is polynomially bounded of degree relative to a size when some constant satisfies for every .✦
Theorem 3 (Polynomial bound for compiled requests). For requests with an arbitrary finite graph and with or , the bound in (8) holds with a single constant . (8)✦