The Setting
The scheduling question concerns the number of time slots needed by unit jobs on three identical machines, subject to directed precedence constraints. Let be the number of jobs and their names. A request has an optional deadline: denotes its absence, and its presence, for .
Binary Words
Write for the underlying binary representation of a natural number . Juxtaposition denotes concatenation, and denotes word length. The self-delimiting integer word and the length-prefixed list word , for a map to binary words, are defined by (1). (1)
For an assignment , its schedule list records its values in job order.✦ The answer word for either the absence of a schedule or a list of slot numbers is the binary word defined in (2). (2)
The Definition
Definition 1. A scheduling instance on jobs is a finite ordered list of precedence edges, as in (3), where a star denotes all finite lists. (3)✦ The precedence relation of a scheduling instance is the binary relation on its jobs for which holds when occurs in .✦ The reachability relation of a scheduling instance is the binary relation on its jobs defined by connection by a nonempty directed path in . An acyclic instance is an instance satisfying (4). (4)✦
A feasible schedule for by deadline is an assignment satisfying (5). (5)✦
The input word for an instance and request is the binary word in (6). (6)✦
A correct output for and request is a binary word satisfying (7); schedule variables range over maps . (7)✦
For , let index the tapes, let be the states, and let be the tape alphabet. A deterministic multitape Turing machine is a partial transition function of the form (8). (8)✦ Here , and mean move left, move right and stay. Symbol is blank; binary bits and are written as symbols and , respectively.✦ A configuration of a deterministic multitape Turing machine is a state in together with one tape with a head for each .✦
The initial configuration of a deterministic multitape Turing machine on a binary input word is the configuration with state , input on tape with its head at the first symbol, and blank tapes elsewhere.✦ A single computation step from a configuration of exists exactly when is defined at its current state and scanned symbols; the next configuration has the returned state, and on each tape the prescribed symbol is written before the prescribed head move is made.✦ A configuration of the machine is halted, denoted by , when its transition function is undefined at . For a deterministic multitape Turing machine , a binary input word and a time , the run configuration is the configuration obtained by steps from , retaining a halted configuration unchanged.✦
Let be the tape content from the head rightwards on tape , with trailing blanks identified, and let be the symbol word for followed by blanks. The time-bounded output relation , for binary words and a bound , is defined by (9). (9)✦
In the paper, the result reads: the input lists the vertices and edges of a finite directed acyclic graph with , a supplied deadline is an integer , and a feasible schedule assigns each unit job a slot in , puts at most three jobs in each slot, and places every edge’s source in an earlier slot than its target.
What Is Checked
The definitions are stated over finite edge lists and binary words, with natural deadline and time bounds and fixed finite machine parameters .