Finding a schedule that is as fair as possible becomes computationally difficult at different points depending on how fairness is measured, according to a new mathematical analysis. The authors summarize completion-time fairness as polynomial-time solvable with at most two days, NP-hard for a fixed number of days greater than two, and strongly NP-hard when the number of days is arbitrary. Waiting-time and tardiness fairness become NP-hard already with two days.
The analysis concerns exact computation in a formal repetitive scheduling model, not observed outcomes. It examines symbolic scheduling instances and uses polynomial-time reductions from Partition with lemma-based, if-and-only-if proofs. No empirical participant or observational data are described.
A fairness rule across repeated workdays
In the model, each of n clients is associated with one job on each of q days. Each day’s jobs are scheduled nonpreemptively on a single machine, meaning a job is not interrupted once it starts. The objective is the classical min–max rule: choose a schedule that minimizes the largest quality-of-service value among clients.
Quality of service, or QoS, can be measured through completion time, waiting time, lateness or tardiness. The paper asks how polynomial-time solvability versus NP-hardness changes as the fixed number of days changes.
Here, NP-hard is a formal complexity label, not a stopwatch reading. The results classify whether a polynomial-time solution is available for the stated problem; they do not report how long a particular software implementation takes. That distinction helps separate the paper’s mathematical classification from practical scheduling performance.
Two reductions locate the hard cases
To prove the three-day completion-time result, the authors use a polynomial-time reduction from Partition, a classical NP-hard problem, to the scheduling problem. The constructed instance has the number of clients specified as n = |A| + 2 and uses q = 3 days. The proof uses an if-and-only-if argument to establish the formal hardness classification.
Theorem 1 establishes weak NP-hardness for maximal fairness under total completion time when q = 3. Weak NP-hardness is distinct from strong NP-hardness, another classification used in the paper’s broader summary. Neither label comes from a statistical estimate, so there is no sampling margin of error to report.
That completion-time result transfers to total tardiness under a special condition. When the due-date parameter dij is 0, the tardiness value Tij equals the completion-time value Cij. Under that equality, the q = 3 tardiness problem receives the same hardness transfer. This is a formal implication, not a separate empirical test.
For waiting time, a second polynomial-time reduction from Partition establishes weak NP-hardness when q = 2, even in the restricted case pij = pj for every job. In plain terms, the processing time assigned to each job does not change from day to day in that special case. The result therefore covers day-independent processing times as well as the general formal problem.
The tardiness result is stated as Corollary 1. It says that total tardiness is weakly NP-hard at q = 2 even with day-independent processing times, using the condition dij = pij. Taken together, the formal results place waiting-time and tardiness difficulty at two days, while completion-time hardness appears for fixed horizons greater than two days.
What the map does—and does not—answer
The authors interpret these theorems alongside earlier cited results as a clearer account of how the number of days affects maximal-fairness scheduling. Their reading is that completion-time fairness remains polynomial-time solvable through two days but becomes hard beyond that, while waiting-time and tardiness fairness are already hard with two days. The broad classification therefore includes results established in the paper and results drawn from cited prior work.
One important boundary remains unresolved. The paper leaves open whether the fixed-q weakly NP-hard cases admit pseudo-polynomial algorithms. In this setting, that term refers to algorithms whose running time can depend on the numerical values in the input; the paper does not settle whether such procedures exist for these cases.
These are formal complexity results for a stated single-machine model. The conclusions apply to nonpreemptive scheduling with all jobs available at time zero, and the study provides no direct evidence about clients, patients, workers or service users. It also does not report practical runtimes, approximation quality, heuristic performance or validation on real scheduling data.
The document is an arXiv version 1 preprint dated 20 Aug 2026. Its funding footnotes list Israel Science Foundation grant No. 977/24 and United States-Israel Binational Science Foundation grant No. 2024004.
Paper data and sources
Original title: New Complexity Results for Fair Repetitive Scheduling
Authors: Moran Koren, Michael L. Pinedo, Dvir Shabtay
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-20
DOI: Not available
Original paper · Full text