An open research package for a candidate resolution of the two-machine, free-order Flow shop with Inter-stage fleXibility and Blocking (FIXB) complexity problem.
Important
This is an unreviewed mathematical research draft, not an established theorem. The proof and code are public to make attempted refutations, independent verification, and literature-priority checks easy.
The two-machine FIXB decision problem is strongly NP-complete. The reduction continues to work when:
- every job has the same number of operations and eligibility pattern;
- each shiftable operation has the same duration on either eligible machine (durations may differ between operations);
- every operation has strictly positive integer duration; and
- each job has mode-independent total workload (a+b).
If the proof survives external review, this resolves the case marked open by Nicosia et al. (2025).
After choosing one mode ((a_j,b_j)) for every job and a common job permutation (\pi), the two-machine blocking/no-wait makespan is
[ C_{\max}(\pi)=a_{\pi_1} +\sum_{r=2}^{N}\max{b_{\pi_{r-1}},a_{\pi_r}} +b_{\pi_N}. ]
The decision problem asks whether some mode selection and permutation has (C_{\max}\le K).
Interpret each selected mode as a directed arc (a\to b). The identity
[ 2C_{\max} =\sum_j(a_j+b_j) +a_{\mathrm{first}} +\sum_{\mathrm{adjacent}}|b_{\mathrm{previous}}-a_{\mathrm{next}}| +b_{\mathrm{last}} ]
turns the makespan threshold into an exact-transition condition. The reduction from Numerical Matching with Target Sums makes (\sum_j(a_j+b_j)) independent of the mode choices. The lower bound is met exactly when all selected arcs form an Euler tour, whose degree balances encode the numerical matching.
| Path | Purpose |
|---|---|
paper/NP_COMPLETENESS_PROOF.md |
Canonical readable proof |
paper/manuscript.tex |
Editable LaTeX manuscript |
paper/fixb-strong-np-completeness.pdf |
Rendered proof brief |
scripts/verify_reduction.py |
Exact NMTS-to-FIXB reduction audit |
scripts/explore.py |
Held--Karp oracle and brute-force cross-check |
scripts/build_pdf.py |
Deterministic ReportLab PDF builder |
docs/LITERATURE_AUDIT.md |
Closest prior models and novelty boundary |
docs/REPRODUCIBILITY.md |
Reproduction instructions and audit scope |
docs/PROBLEM_SPEC.md |
Original problem specification and win conditions |
docs/RESEARCH_LOG.md |
Independent approaches and outcomes |
docs/TWITTER_THREAD.md |
Cautious public-facing explanation |
assets/fixb-proof-card.png |
Shareable first-page proof card |
Python 3.11 or later is recommended. The mathematical verifier uses only the Python standard library.
python3 scripts/explore.py validate --seed 137 --trials 250
python3 scripts/verify_reduction.py \
--n 2 --max-value 5 --random-trials 500 --seed 137Expected output:
validated Held--Karp DP on 250 random instances
PASS: 795 canonical exhaustive instances and 500 random instances;
base and uniform-padding reductions agree exactly with NMTS
The scripts audit finite instances of the construction; they do not replace the analytic proof.
To rebuild the PDF brief:
python3 -m pip install -r requirements.txt
RL_invariant=1 python3 scripts/build_pdf.pyA targeted audit through 2026-07-23 found several close hardness results,
but no theorem for the exact strictly-positive, mandatory-two-machine,
nonpreemptive, free-order FIXB model. The important distinctions are recorded
in docs/LITERATURE_AUDIT.md.
The defensible public wording is:
No exact prior theorem was located in the databases and query families searched as of 2026-07-23. This repository contains a candidate resolution, subject to mathematical review and a broader priority check.
Proof objections, counterexamples, checker failures, and missing prior
literature are especially welcome. Please
open an issue
with a reproducible example or a precise citation. See
CONTRIBUTING.md.
Prepared by patrick (@pwyhack). Citation
metadata is provided in CITATION.cff.
Released under the MIT License.