PROBLEM_SPEC.md

Research specification: two-machine FIXB

The open classification problem

There are (n) jobs and two machines. Job (j) has a finite ordered set of feasible modes

[ M_j={(a_{jr},b_{jr}):r=1,\ldots,q_j}, ]

where (a_{j1}<\cdots<a_{jq_j}) and (b_{j1}>\cdots>b_{jq_j}). A mode is a split point in the job's operation chain: (a_{jr}) is its aggregate processing time on machine 1 and (b_{jr}) its aggregate processing time on machine 2.

Every eligible operation--machine assignment has a strictly positive processing time. A flexible operation may have different processing times on its two eligible machines; equal times are a special restriction, not part of the general model.

Choose one mode (r_j) for every job and one common permutation (\pi=(\pi_1,\ldots,\pi_n)). Under the no-wait/blocking timing forced by that choice, the makespan is

[ C_{\max}(\pi,r)= a_{\pi_1r_{\pi_1}}

• \sum_{t=2}^{n} \max{b_{\pi_{t-1}r_{\pi_{t-1}}}, a_{\pi_tr_{\pi_t}}}
• b_{\pi_nr_{\pi_n}}. ]

Determine whether minimizing this expression is polynomial-time solvable or NP-hard. This is the unresolved two-machine, nonpreemptive, free-order case identified by Nicosia et al. (2025).

All computational experiments use positive integers. Rational data reduce to integer data by a common scaling.

Exact win conditions

A complete polynomial result must give:

1. an algorithm returning an optimal mode vector and permutation for every finite monotone mode set;
2. a proof that every transformation, exchange, recurrence, and reconstruction step preserves global optimality; and
3. a running-time bound polynomial in (n+\sum_j q_j) and the bit length of the data.

A complete hardness result must give:

1. a polynomial reduction from a named NP-hard decision problem;
2. an if-and-only-if proof with an explicit threshold;
3. only valid monotone mode frontiers, with every abstract frontier realized by an actual FIXB operation chain;
4. polynomially bounded encoding length; and
5. membership in NP, if NP-completeness is claimed.

A valid narrower theorem must state its scope explicitly. It may be a useful new result, but it does not close the classification unless it meets one of the two complete win conditions above.

Facts that may be used

For selected pairs ((a_j,b_j)),

[ C_{\max} =\sum_j(a_j+b_j) -\sum_{t=2}^{n}\min{b_{\pi_{t-1}},a_{\pi_t}}. ]

Thus fixed modes reduce to the classical two-machine no-wait flow-shop sequencing problem solved by Gilmore and Gomory. A fixed permutation reduces to a layered shortest-path problem over consecutive modes.

Any two-mode frontier [ (a_1,b_1),(a_2,b_2),\qquad a_1<a_2,\quad b_1>b_2, ] is realized by a three-operation FIXB job using [ p^1_1=a_1,\quad p^1_2=a_2-a_1,\quad p^2_2=b_1-b_2,\quad p^2_3=b_2. ] Consequently a hardness proof cannot evade realizability merely by using two strict modes.

Results that are not enough

The following are evidence or partial progress, not a solution:

• a local-search rule without a global exchange proof;
• a Johnson-style sort tested only on examples;
• floating-point or random experiments;
• an exponential exact algorithm presented as a polynomial classification;
• a reduction whose modes are arbitrary pairs but not realizable frontiers;
• proving only a fixed-order or fixed-mode case already covered in the paper;
• an approximation theorem described as exact optimization;
• an unproved lemma carrying the main combinatorial burden;
• a computer search without a small human-readable certificate and an independent checker; or
• a theorem whose novelty relative to the 2025 FIXB paper and the classical fixed-mode literature has not been checked.

Research protocol

Maintain independent polynomial, hardness, and computational/adversarial routes. Each route must return a concrete lemma, recurrence, gadget, certificate, or counterexample. Do not merge incompatible routes merely because one looks elegant.

Every computational claim must be integer-exact and reproducible. The checker must verify a supplied certificate without relying on the search procedure. Computation may discover a conjecture or falsify one; it does not replace the general proof.

Before any full-solution claim, perform a separate audit of:

• all quantifiers and boundary cases;
• strict versus weak mode inequalities;
• positivity and encoding size;
• the common-permutation and blocking semantics;
• both directions of a reduction or every step of an optimality induction;
• claimed complexity;
• exact certificate replay; and
• the boundary between a new theorem and the still-open classification.