Polynomial-time scheduling on three identical machines

The explanation

Picture nine jobs that each take one hour, and three identical machines. Each machine runs one job at a time. Three of the jobs form a chain. The first must finish before the second starts, and the second before the third. The other six jobs can run whenever there is room. The goal is to finish everything as early as possible. The finishing time of the last job is called the makespan.

The best schedule takes three hours. Each hour runs one chain job beside two free jobs. Now suppose the first hour is filled with three free jobs instead. The chain cannot start until hour two, so its last job ends in hour four. One poor early choice costs a whole extra hour. With order rules (called precedence constraints), early choices can quietly ruin later ones.

Trying everything does not scale. Ignoring the order rules, nine jobs can be split into three ordered groups of three in 1,680 ways. Thirty jobs over ten hours allow about 4.4 × 10^24 splits. So researchers want a polynomial-time method. That means its number of steps grows at most like a fixed power of the input size.

For two machines the question was settled long ago. Fujii, Kasami and Ninomiya treated it in 1969. Coffman and Graham gave an optimal method in 1972. If the number of machines is part of the input, Ullman showed in 1975 that the problem is NP-complete. That puts it in a large family of problems with no known fast method. Three fixed machines sat in between. Garey and Johnson listed that case as an open problem in their 1979 book.

Partial answers followed. Garey, Johnson, Tarjan and Yannakakis handled three machines in linear time when the order rules form opposing forests. Dolev and Warmuth gave a polynomial method when the chains of rules have bounded length. In 2025, Nederlof, Swennenhuis and Węgrzycki gave an exact method for any rules. For three machines it runs in time 2^{O(√n log n)} for n jobs. That beats trying everything, but it is not polynomial. Other work found schedules within any fixed percentage of the best one.

This paper proves that a polynomial-time method exists for three machines and any order rulesSource 1. It finds a schedule with the smallest makespan. Given a deadline, it decides exactly whether all jobs can finish by then. It also returns a schedule when the answer is yesSource 2.

The natural plan is to cut a good schedule at a few chosen hours. The jobs in each gap between cuts can then be rearranged on their own. Rearranging them does not change their order relative to any job outside the gapSource 3. So one could solve gaps separately and reuse the answers. The obstacle is how many gaps there are. Knowing the jobs at a gap's two edges does not pin down which jobs sit insideSource 4. Describing a gap through all the cuts above it can need an ever longer recipeSource 5.

The paper removes this obstacle with short descriptions. It shows that every schedule that meets the deadline can be cut so that each gap has a short recipe. A recipe combines simple yes-or-no tests on a job. One test asks whether the job must come before or after some group of three jobs. Another asks where the job falls in one fixed ordering of all jobs. The method allows recipes of up to 10,000 testsSource 6. The proof needs fewer than 500. Crucially, the length does not grow with the depth of cuttingSource 7. Only polynomially many job sets then need checking. The method checks them from smallest to largest and glues accepted pieces into a full scheduleSource 8.

In the nine-job example, the method would always find the three-hour schedule. But fast in theory is not fast in practice. The paper bounds the steps by (L + 2)^150020, where L is the input length in bitsSource 1. For a 10-bit input, that bound is a number with about 162,000 digits. The paper makes no practical running-time claimSource 9. The theorem covers exactly three machines, one-hour jobs, and no release dates or communication delaysSource 10.

How sure is this? A computer proof checker called Lean has checked a formal version of the main theorem. It covers one fixed algorithm that finds a minimum-makespan schedule and decides a given deadline exactly. Its running time is polynomial in the input length. The scope note links this to a fixed reference statement for a tool called Comparator. It does not mention the paper's specific exponent. No specialists have published a review yet.

What it doesn't show. This does not give a practical program, and it does not cover four or more machines.