Audit date: 2026-07-23
Status: living document; not a certification of priority
The literature reviewed for this repository does not contain a prior proof of strong NP-completeness for the exact problem treated here:
- two machines;
- a freely chosen common job permutation;
- blocking (zero intermediate buffer);
- nonpreemptive operations with strictly positive processing times;
- every operation assigned to exactly one eligible machine and every job visiting both machines; and
- inter-stage flexibility represented by a finite choice of valid assignment modes.
The strongest contemporaneous evidence is Nicosia et al. (2025), whose formal definition matches these assumptions and whose complexity table marks the two-machine, free-sequence, blocking-and-flexibility case Open. The proof in this repository is therefore best described as a candidate resolution of that open case. It has not been externally peer reviewed, and this search cannot establish that no unpublished, unindexed, differently named, or simultaneously developed result exists.
For each job, a mode is summarized by a pair ((a_j,b_j)), the aggregate processing assigned to machines (M_1) and (M_2). With selected modes and a common permutation (\pi), the two-machine makespan is
[ C_{\max}(\pi) =a_{\pi_1}
- \sum_{r=2}^{N}\max{b_{\pi_{r-1}},a_{\pi_r}}
- b_{\pi_N}. ]
In the general model a flexible operation may have distinct positive processing times on its two eligible machines. The candidate reduction uses the stricter special case in which those two times are equal for each shiftable operation.
The repository claims strong NP-completeness of the corresponding decision problem. The reduction further uses instances in which:
- all jobs can be padded to the same operation count and the same operation-to-machine eligibility pattern;
- each shiftable operation takes the same time on either eligible machine (durations may differ between operations); and
- a job's total processing time (a_j+b_j) is independent of its selected mode.
Those restrictions are useful when comparing the result with adjacent models: hardness caused by preemption, zero-duration operations, missing machine visits, or a special global idleness rule would not establish this theorem.
| Work | Result and model | Why it does not duplicate this repository |
|---|---|---|
| Nicosia et al. (2025) | Introduces FIXB as a permutation flow shop with blocking and inter-stage-flexible operations. Processing times are strictly positive, every operation is assigned to exactly one machine, and every job visits every machine. Their Table 1 classifies the two-machine case with blocking, flexibility, and a non-fixed job sequence as open. They prove polynomial solvability when the two-machine job sequence is fixed. | This is the matching problem definition and the source of the open case, not an earlier hardness proof. The theorem in this repository is intended to fill precisely the open row in their table. |
| Dong et al. (2021) | Studies a nonpreemptive two-stage no-wait model in which (M_1) may process the whole second-stage operation. It proves ordinary NP-hardness by a reduction from Partition and gives a (13/8)-approximation. In the published reduction, the first operation has processing time (a_i=0), while the flexible second operation has processing time (b_i=s_i). | A job whose second operation is assigned to (M_1) need not visit (M_2), and the hardness construction explicitly uses zero processing times. Both features are excluded by FIXB's strictly-positive, mandatory-machine-visit definition. The reduction also proves ordinary, rather than strong, NP-hardness. |
| Zhong and Shi (2018) | Studies a two-stage no-wait hybrid flow shop, generally with parallel machines at each stage. Each job has fixed total processing time; its stage-1 work has an obligatory part and a solution-dependent optional part. A special rule forbids optional stage-1 work from running while any stage-2 machine is idle. The problem is strongly NP-hard even with one machine at each stage. | The solution-dependent optional-work rule and its system-wide stage-2-idleness condition are not the FIXB operation-assignment/blocking model. Their one-machine-per-stage hardness result therefore applies to a different feasible-schedule set, despite the close “inter-stage flexibility” terminology. |
| Khorasanian and Moslehi (2017) | Studies a two-machine flow shop with blocking, multi-task flexibility of (M_1), and preemption, and proves strong NP-hardness. | Preemption is an explicit part of both the model and its hardness construction. FIXB operations in the present result are nonpreemptive, so this theorem does not settle the candidate's case. |
| Gupta et al. (2004) | Introduces heterogeneous three-operation jobs with a positive (M_1)-only prefix, one equal-duration flexible middle operation, and a positive (M_2)-only suffix. The job order is chosen, and the problem is binary NP-hard. | This is perhaps the closest operation-chain structure, but it is a standard infinite-buffer flow shop: it does not impose FIXB's zero-buffer blocking/no-wait timing. It also establishes ordinary rather than strong NP-hardness. |
| Della Croce, Salassa, and T'kindt (2022) | Gives an exact approach for the heterogeneous three-operation problem introduced by Gupta et al., solving large instances computationally. | It retains the infinite-buffer, nonblocking model. Its algorithms and inherited NP-hardness baseline therefore do not classify the blocking model treated here. |
| Crama and Gultekin (2010) | Studies the same dedicated/flexible/dedicated operation pattern for identical parts, including finite, infinite, and zero intermediate-buffer variants. | Identical parts eliminate heterogeneous sequencing choices. The zero-buffer analysis is a close structural comparator, but it is a high-multiplicity allocation/throughput problem rather than the candidate's heterogeneous-job decision problem. |
| Gultekin (2012) | Studies identical three-operation jobs whose flexible operation may have machine-dependent durations, and gives constant-time solutions for both infinite- and zero-buffer cases. | The tractability relies on every job being identical. It neither proves hardness nor supplies an algorithm for heterogeneous FIXB jobs with independent mode frontiers. |
| Lin, Hwang, and Gupta (2017) | Studies three-operation jobs on two machines: the first and last operations are dedicated and the middle operation is flexible. The job sequence is supplied as part of the input, and the model does not impose FIXB blocking. It proves ordinary NP-hardness for several objectives, including makespan, even when the dedicated-operation processing times are zero. | The sequence is fixed rather than chosen, and the blocking constraint is absent. These distinctions are substantive: Nicosia et al. show that adding blocking makes the fixed-sequence, two-machine FIXB case polynomially solvable. |
| Gilmore and Gomory (1964) | Gives a polynomial algorithm for a solvable one-state-variable traveling-salesman class. Through the classical reduction, it supplies the polynomial baseline for the two-machine no-wait/blocking makespan problem when every job's processing pair is fixed. | It contains no per-job mode-selection decision. The candidate result's hardness comes from jointly selecting endpoints/modes and ordering the resulting jobs; fixing one mode per job returns to the classical solvable setting. |
Some adjacent papers use “no-wait” while FIXB is stated with “blocking.” Nicosia et al. observe that, for two machines, there is an optimal blocking schedule in which each job moves immediately from (M_1) to (M_2), so the optimal values coincide. This explains why no-wait papers are relevant comparators. It does not remove the differences above concerning preemption, zero-length operations, skipped machines, optional work, or fixed-versus-free sequencing.
This audit used the 2025 FIXB paper and its bibliography as the principal classification anchor, then searched the exact title and terminology together with adjacent terms including blocking, no-wait, inter-stage flexibility, multi-task flexibility, flexible operation, three-operation jobs, identical jobs, two-machine, free sequence, nonpreemptive, Numerical Matching with Target Sums, and Gilmore--Gomory. Publisher and author-hosted records were checked for the papers above. DOI/Crossref metadata and the OpenAlex and Semantic Scholar citation records for the Nicosia paper were also checked for later work; the indexed forward citations inspected did not resolve the open complexity case.
This is a targeted audit, not a systematic review with guaranteed recall. Bibliographic databases differ in coverage and merge preprints, accepted manuscripts, and journal versions imperfectly. Very recent, in-press, non-English, thesis-only, workshop-only, unpublished, or unusually terminologized work may be absent. Citation graphs also lag publication. Accordingly, a negative search result is evidence of novelty, not proof of novelty.
Until independent experts have checked both the proof and the literature, appropriate wording is:
This repository presents a candidate proof that two-machine FIXB with a free job order is strongly NP-complete. Nicosia et al. (2025) list this case as open, and our literature audit found no earlier proof for the exact model.
Also appropriate:
- “candidate resolution of the open case”;
- “to the best of our search, no prior exact result was found”; and
- “if verified, the theorem closes the two-machine free-order FIXB complexity gap.”
Avoid unqualified priority claims such as “the first proof,” “we definitively solved the problem,” or “this result is absent from all literature.”
Before making a formal priority claim, the recommended next steps are:
- obtain an independent proof audit from a scheduling-complexity researcher;
- send the manuscript and this comparison to the authors of Nicosia et al.;
- repeat the citation and keyword searches immediately before posting a dated preprint; and
- preserve a public, immutable release containing the proof and verification code.
- G. Nicosia, A. Pacifici, U. Pferschy, A. Russo Russo, and C. Salvatore, “Flow shop scheduling with inter-stage flexibility and blocking constraints,” Computers & Operations Research 184, 107219 (2025). DOI; open preprint.
- J. Dong, H. Pan, C. Ye, W. Tong, and J. Hu, “No-wait two-stage flowshop problem with multi-task flexibility of the first machine,” Information Sciences 544, 25–38 (2021). DOI; open full text.
- W. Zhong and Y. Shi, “Two-stage no-wait hybrid flowshop scheduling with inter-stage flexibility,” Journal of Combinatorial Optimization 35(1), 108–125 (2018). DOI.
- D. Khorasanian and G. Moslehi, “Two-machine flow shop scheduling problem with blocking, multi-task flexibility of the first machine, and preemption,” Computers & Operations Research 79, 94–108 (2017). DOI.
- B. M. T. Lin, F. J. Hwang, and J. N. D. Gupta, “Two-machine flowshop scheduling with three-operation jobs subject to a fixed job sequence,” Journal of Scheduling 20(3), 293–302 (2017). DOI.
- P. C. Gilmore and R. E. Gomory, “Sequencing a one state-variable machine: A solvable case of the traveling salesman problem,” Operations Research 12(5), 655–679 (1964). DOI.
- J. N. D. Gupta, C. P. Koulamas, G. J. Kyparisis, C. N. Potts, and V. A. Strusevich, “Scheduling three-operation jobs in a two-machine flow shop to minimize makespan,” Annals of Operations Research 129, 171–185 (2004). DOI.
- F. Della Croce, F. Salassa, and V. T'kindt, “Exact solution of the two-machine flow shop problem with three operations,” Computers & Operations Research 138, 105595 (2022). DOI.
- Y. Crama and H. Gultekin, “Throughput optimization in two-machine flowshops with flexible operations,” Journal of Scheduling 13(3), 227–243 (2010). DOI.
- H. Gultekin, “Scheduling in flowshops with flexible operations: Throughput optimization and benefits of flexibility,” International Journal of Production Economics 140(2), 900–911 (2012). DOI.