An instance is an explicitly listed directed acyclic graph whose vertices are jobs to be run on three identical parallel machines. Each job runs for one unit of time without interruption. A feasible schedule assigns each job a positive integer completion time so that at most three jobs have any one completion time and every precedence edge points from an earlier job to a later job. The makespan is the greatest completion time. Given an integer deadline with , deadline feasibility asks whether a feasible schedule has makespan at most . The optimization problem asks for a feasible schedule of minimum makespan. Let denote the total binary input length.
For two machines, Coffman and Graham gave an algorithm that constructs a schedule of minimum makespan. Ullman proved NP-completeness when the number of machines is part of the input. For three machines, Nederlof, Swennenhuis, and Węgrzycki obtained an exact algorithm with running time .
The preprint proves that deadline feasibility is decidable by a fixed deterministic multitape Turing machine in steps. It also proves that an optimal schedule can be constructed within the same bound.
Lean has checked every result of the Lean library Scheduling, so the Lean library is the reference for the statements on these pages. The correctness theorem of the Lean library takes nonemptiness and acyclicity of the input as hypotheses. Each result on these pages is stated as in the Lean library and linked to its Lean declaration. Where the preprint states a result differently, the Lean library’s statement is given with the preprint’s beside it. The preprint is a guide only to the order and names of the results.
Scheduling is a Lean library: 33 items, in nine groups. Each has a page written by OctoInform, listed below.
No item matches.