Three-machine unit-job scheduling with precedence constraints (Garey-Johnson OPEN8): is P3|prec,p_j=1|Cmax in P?

Theorem 1.1: a uniform deterministic algorithm constructs a minimum-makespan schedule for unit-length jobs with arbitrary precedence constraints on three identical machines, and decides feasibility for a deadline $1\le T\le n$ exactly, in $O((L+2)^{150020})$ Turing machine steps. The method decomposes schedules into gaps whose job sets have bounded-size global Boolean descriptions and searches them by dynamic programming. The exponent is astronomically large and no practical claim is made. It does not settle $m\ge4$ fixed machines, which remains open.

Theorem 1.1: a uniform deterministic algorithm constructs a minimum-makespan schedule for unit-length jobs with arbitrary precedence constraints on three identical machines, and decides feasibility for a deadline $1\le T\le n$ exactly, in $O((L+2)^{150020})$ Turing machine steps. The method decomposes schedules into gaps whose job sets have bounded-size global Boolean descriptions and searches them by dynamic programming. The exponent is astronomically large and no practical claim is made. It does not settle $m\ge4$ fixed machines, which remains open.