manuscript.tex

\documentclass[10pt]{article}

\usepackage[margin=0.92in]{geometry}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{booktabs}
\usepackage{enumitem}
\usepackage{xcolor}
\usepackage{microtype}
\usepackage[hidelinks]{hyperref}
\usepackage{lmodern}

\definecolor{deepblue}{HTML}{173F5F}
\definecolor{muted}{HTML}{58636F}
\hypersetup{colorlinks=true,linkcolor=deepblue,citecolor=deepblue,urlcolor=deepblue}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{proposition}{Proposition}
\newtheorem{corollary}{Corollary}
\theoremstyle{definition}
\newtheorem{definition}{Definition}
\newtheorem{remark}{Remark}

\newcommand{\fixb}{\textsc{Fixb}}
\newcommand{\cmax}{C_{\max}}
\newcommand{\abs}[1]{\lvert #1\rvert}

\title{\vspace{-1.2cm}
  \textbf{Strong NP-completeness of two-machine \fixb}\\[2mm]
  \large A candidate Euler-tour reduction from NMTS}
\author{patrick\\\small\url{https://github.com/pwyhack}}
\date{23 July 2026}

\begin{document}
\maketitle

\begin{abstract}
Nicosia et al.\ left open the complexity of the two-machine flow shop with
inter-stage flexibility and blocking when the job order is free.  We give a
reduction from Numerical Matching with Target Sums and prove that the decision
problem is strongly NP-complete.  The reduction survives three severe
restrictions: every job has the same operation-to-machine eligibility pattern,
each shiftable operation takes the same time on \(M_1\) and \(M_2\) (durations
may differ between operations), and each job's total workload \(a+b\) is
independent of its selected mode.  The
proof turns each selected mode into a directed arc.  A simple identity shows
that the target makespan is attained exactly when those arcs form an Euler
tour.  We also record an elementary tight \(2\)-approximation and exact finite
audits of the construction.  This is a research draft and has not yet been
externally peer reviewed.
\end{abstract}

\section{The open case}

A \fixb\ input gives every job as an ordered chain of indivisible operations.
Every eligible operation--machine assignment has a strictly positive,
binary-encoded integer processing time; a flexible operation may have
different times on its two eligible machines. The first operation is
\(M_1\)-only, the last is \(M_2\)-only, and an intermediate operation may be
eligible on either machine. A feasible assignment chooses a cut: a prefix is
processed on \(M_1\), and the remaining suffix on \(M_2\).
Thus each cut induces one aggregate mode, and a job has a finite collection of
feasible modes
\[
  (a_{j1},b_{j1}),\ldots,(a_{jq_j},b_{jq_j}),
  \qquad
  a_{j1}<\cdots<a_{jq_j},\quad
  b_{j1}>\cdots>b_{jq_j}.
\]
Here \(a_{jr}\) and \(b_{jr}\) are the aggregate processing times assigned to
machines \(M_1\) and \(M_2\). We use the induced mode list as notation; the
hardness construction below supplies an actual operation chain for every such
list it creates. Given one mode per job and a common permutation
\(\pi=(\pi_1,\ldots,\pi_N)\), blocking implies
\begin{equation}
  \cmax(\pi)
  =a_{\pi_1}
   +\sum_{s=2}^{N}\max\{b_{\pi_{s-1}},a_{\pi_s}\}
   +b_{\pi_N}.
  \label{eq:makespan}
\end{equation}
The decision problem asks whether some mode vector and permutation have
\(\cmax\le K\).  Nicosia et al.\ identify its complexity as open when the shop
has two machines and the order is not fixed \cite{nicosia2025}.  Without
flexibility, the two-machine blocking/no-wait problem belongs to the
Gilmore--Gomory solvable class \cite{gilmore1964}.

\subsection{Boundary with the closest prior models}

Similar terminology is used for several non-equivalent scheduling models, so
the claim here is deliberately narrow. Dong et al.\ prove ordinary
NP-hardness for a nonpreemptive no-wait model in which the flexible final
operation may finish on \(M_1\), allowing a job to skip \(M_2\); their
PARTITION construction also uses zero-duration first operations
\cite{dong2021}. Zhong and Shi prove strong NP-hardness for an
idleness-dependent optional-work model motivated by recovery-room scheduling,
rather than indivisible intermediate operations bounded by mandatory visits
to both machines \cite{zhong2018}. Khorasanian and Moslehi prove strong
NP-hardness when preemption is permitted \cite{khorasanian2017}. Lin, Hwang,
and Gupta study the mandatory-endpoint/flexible-middle structure, but without
blocking and with the job sequence fixed \cite{lin2017}.

The heterogeneous three-operation model of Gupta et al.\ is structurally even
closer: it has a positive \(M_1\)-only prefix, an equal-duration flexible
middle operation, a positive \(M_2\)-only suffix, and a free job order
\cite{gupta2004}. Its flow shop has an intermediate buffer rather than FIXB
blocking; Della Croce, Salassa, and T'kindt retain that nonblocking model in
their exact approach \cite{dellacroce2022}. Crama and Gultekin study the same
operation pattern with zero buffer, but only for identical parts
\cite{crama2010}; Gultekin gives constant-time solutions for related
identical-job zero-buffer instances \cite{gultekin2012}.

None of these results establishes the strictly-positive, mandatory-visit,
nonpreemptive, blocking case with a free job permutation formulated by Nicosia
et al. A targeted search through 23 July 2026 located no exact prior theorem,
but this negative search is not a proof of priority. A fuller comparison and
its coverage limits are maintained with the public source repository.

\section{The deadhead identity}

The following identity is the entire lower-bound mechanism.

\begin{lemma}[Deadhead identity]
\label{lem:deadhead}
Suppose every selected job has endpoints \((a_j,b_j)\), and put
\(S=\sum_j(a_j+b_j)\).  For every permutation \(\pi\),
\begin{equation}
  2\cmax
  =S+
  \left(
    a_{\pi_1}
    +\sum_{s=2}^{N}\abs{b_{\pi_{s-1}}-a_{\pi_s}}
    +b_{\pi_N}
  \right).
  \label{eq:deadhead}
\end{equation}
\end{lemma}

\begin{proof}
Apply \(2\max\{p,q\}=p+q+\abs{p-q}\) to each internal term of
\eqref{eq:makespan} and collect the endpoint contributions.
\end{proof}

Interpret a mode \((a,b)\) as an arc copy \(a\to b\) on a set of numerical
labels. Jobs remain distinct arc copies even when endpoints coincide.
If \(S\) is mode-independent and all endpoints are at least a hub value
\(h\), Lemma~\ref{lem:deadhead} yields
\[
  \cmax\ge \frac{S}{2}+h.
\]
Equality holds if and only if the first tail and last head equal \(h\), and
every consecutive head and tail match. Equivalently, the chosen arc copies,
in job order, form a directed Euler circuit based at \(h\).

\section{Reduction from numerical matching}

\begin{definition}[NMTS]
An instance of \emph{Numerical Matching with Target Sums} consists of
three \(n\)-element multisets of positive integers,
\[
  X=\{x_1,\ldots,x_n\},\quad
  Y=\{y_1,\ldots,y_n\},\quad
  T=\{t_1,\ldots,t_n\}.
\]
It asks whether the occurrences in \(X\) and \(Y\) can be assigned
bijectively to the occurrences in \(T\), with \(x+y=t\) for every assigned
triple.
\end{definition}

NMTS is strongly NP-complete \cite[Problem SP17]{garey1979}; it remains
strongly NP-hard when all \(3n\) integers are distinct
\cite[Corollary 8]{hulett2008}. Every YES instance necessarily satisfies
\(\sum_i x_i+\sum_j y_j=\sum_k t_k\). We check this identity in polynomial
time and map a failure, or a target with no compatible pair, to a fixed NO
\fixb\ instance. Hence assume the identity below.

Let
\[
  P=\max(X\cup Y\cup T),\qquad
  h=1,\qquad
  u(x)=P+x,\qquad
  v(y)=3P+y.
\]
The three label bands are disjoint:
\[
  h<u(x)\le 2P<3P<v(y)\le4P.
\]
Construct \(3n\) jobs:
\begin{enumerate}[label=(\roman*),leftmargin=2em]
  \item for each target occurrence \(t_k\), a target job \(Z_k\) with the
        distinct modes
        \[
          u(x)\longrightarrow v(y)
          \qquad\text{for every numerical pair }x+y=t_k;
        \]
  \item for each occurrence \(x_i\in X\), one fixed connector
        \(A_i:h\to u(x_i)\);
  \item for each occurrence \(y_j\in Y\), one fixed connector
        \(B_j:v(y_j)\to h\).
\end{enumerate}

Each mode of \(Z_k\) has the constant sum
\[
  u(x)+v(y)=4P+t_k.
\]
As \(x\) increases, \(y=t_k-x\) decreases, so the target modes form a valid
strict \fixb\ frontier.  Moreover the total endpoint sum is independent of
all mode choices:
\begin{align}
  S
  &=\sum_k(4P+t_k)
    +\sum_i(1+P+x_i)
    +\sum_j(3P+y_j+1) \notag\\
  &=8nP+2n+2\sum_k t_k.
  \label{eq:sum}
\end{align}
It is even.  Set
\begin{equation}
  K=\frac{S}{2}+1
   =4nP+n+\sum_k t_k+1.
  \label{eq:threshold}
\end{equation}

\begin{theorem}
\label{thm:main}
The two-machine \fixb\ decision problem is strongly NP-complete.
\end{theorem}

\begin{proof}
All constructed endpoints are at least \(h=1\).  Lemma~\ref{lem:deadhead}
and \eqref{eq:threshold} show that every schedule has \(\cmax\ge K\), with
equality exactly when its selected arc copies form an exact-transition Euler
circuit based at \(h\).

Suppose the NMTS instance is YES.  If target \(t_k\) receives occurrences
\(x_i,y_j\), select \(u(x_i)\to v(y_j)\) for \(Z_k\).  The selected graph is
the union of \(n\) directed triangles
\[
  h\longrightarrow u(x_i)\longrightarrow v(y_j)\longrightarrow h.
\]
They share \(h\), so the graph is connected and balanced and therefore has
an Euler circuit.  The corresponding job order has makespan \(K\).

Conversely, suppose a schedule has makespan at most \(K\).  It must attain
equality, hence its selected arcs form an Euler circuit.  At label \(u(x)\),
the number of incoming fixed arcs is exactly the multiplicity of \(x\) in
\(X\); the only outgoing arcs are target arcs.  Degree balance therefore
forces exactly that many targets to use \(x\).  At label \(v(y)\), the only
incoming arcs are target arcs and the number of outgoing fixed arcs is
exactly the multiplicity of \(y\) in \(Y\).  Balance forces exact use of all
\(Y\)-occurrences.  Every selected target mode satisfies \(x+y=t_k\), so the
modes yield an NMTS solution.

The construction has \(3n\) jobs, \(O(n^2)\) modes and operations, and
numbers of magnitude \(O(P)\).  Thus strong NP-hardness follows.  The problem
is in NP because a mode choice and a permutation certify
\eqref{eq:makespan}.
\end{proof}

\section{Actual operation chains and a uniform pattern}

The reduction above is stated in aggregate mode notation.  The next lemma
shows that every such target frontier is produced by genuine \fixb\
operations.

\begin{lemma}[Anti-diagonal realization]
\label{lem:realize}
Let
\[
 (a_1,b_1),\ldots,(a_r,b_r),
 \qquad
 a_1<\cdots<a_r,\quad b_1>\cdots>b_r,\quad a_s+b_s=C.
\]
There is an \(r+1\)-operation two-machine \fixb\ job with exactly these modes.
Each shiftable operation has the same processing time on \(M_1\) and \(M_2\);
durations may differ between operations.
\end{lemma}

\begin{proof}
Use an \(M_1\)-only first operation of duration \(a_1\).  For
\(s=1,\ldots,r-1\), use a shiftable operation of duration
\[
 d_s=a_{s+1}-a_s=b_s-b_{s+1}>0
\]
on either machine.  Finish with an \(M_2\)-only operation of duration \(b_r\).
The feasible cut after the first \(s\) operations of the chain telescopes to
\((a_s,b_s)\), and there are no other cuts.
\end{proof}

Even the job lengths and eligibility patterns can be made identical.  After
the fixed-NO preprocessing, every job has \(1\le r_j\le n\) desired modes.
Set \(R=n\), \(M=2n+1\), scale every legitimate endpoint by \(M\), and write
\(H=M\).  If job \(j\) has unscaled constant mode-sum \(c_j\), add
\(R-r_j\) modes
\begin{equation}
  (H+q,\ Mc_j-H-q),
  \qquad q=1,\ldots,R-r_j.
  \label{eq:padding}
\end{equation}
Every unscaled constant mode-sum satisfies \(c_j\ge3\). Since
\(q\le n<M\), a padding head satisfies
\[
 Mc_j-H-q=M(c_j-1)-q\ge2M-n>H=M,
\]
while its tail \(H+q\) is also strictly larger than \(H\). Thus all desired
and padding modes lie on one positive anti-diagonal. Their first coordinates
are distinct, so after sorting Lemma~\ref{lem:realize} gives every job exactly
\(n+1\) operations: an \(M_1\)-only operation, \(n-1\) shiftable operations,
and an \(M_2\)-only operation.

Why can a padding mode not create a false YES?  Desired endpoints have
residue \(0\bmod M\).  Padding tails have residues in
\(\{1,\ldots,n\}\), while padding heads have residues in
\(\{n+1,\ldots,2n\}\). Thus no possible head equals a padding tail. A padding
arc cannot be internal to an exact-transition circuit, and it cannot be first
because equality requires the first tail to equal \(H\), not \(H+q\). Hence
no padding arc can occur. The lower bound and threshold scale by \(M\). This
proves the following strengthening. Since \(M=O(n)\), every padded endpoint
is \(O(nP)\), preserving polynomial boundedness on the strongly NP-hard NMTS
family.

\begin{corollary}
\label{cor:strong}
Two-machine \fixb\ is strongly NP-complete even when:
\begin{enumerate}[label=(\alph*),leftmargin=2em]
  \item all jobs have the same number of operations and the same eligibility
        pattern;
  \item each shiftable operation has the same duration on \(M_1\) and \(M_2\),
        though durations may differ between operations;
  \item every job has mode-independent total workload \(a+b\).
\end{enumerate}
\end{corollary}

\section{A tight elementary approximation}

Strong NP-completeness rules out an exact polynomial algorithm unless
\(\mathrm{P}=\mathrm{NP}\), but one simple guarantee is immediate.

\begin{proposition}
\label{prop:approx}
Selecting, independently for every job, a mode minimizing \(a+b\), and then
using any job order, is a polynomial \(2\)-approximation.  The factor is
asymptotically tight for this algorithm.
\end{proposition}

\begin{proof}
For any selected modes and order,
\[
  \cmax\le\sum_j(a_j+b_j).
\]
Let \((a_j^*,b_j^*)\) be the modes in an optimum schedule.  Its makespan is
at least the workload on either machine, so
\[
  \mathrm{OPT}
  \ge\max\left\{\sum_j a_j^*,\sum_j b_j^*\right\}
  \ge\frac12\sum_j(a_j^*+b_j^*).
\]
The independently selected sum is no larger than the last sum, which proves
the ratio.

For tightness, take \(2m\) identical jobs with the two modes
\[
  (1,L),\qquad(L+1,1),\qquad L\ge2.
\]
The first mode uniquely minimizes \(a+b\), so the algorithm has makespan
\(2mL+1\), regardless of order.  Alternating the two modes gives a feasible
schedule of makespan \(mL+2m+1\).  Hence the approximation ratio is at least
\[
  \frac{2mL+1}{mL+2m+1}\longrightarrow2
  \qquad(L\to\infty).
\]
The two modes are realized by mandatory endpoint operations of durations
\(1\) and \(1\), and one flexible operation whose duration is \(L\) on
\(M_1\) and \(L-1\) on \(M_2\). Thus they are valid \fixb\ jobs under the
general machine-specific processing-time convention.
\end{proof}

\section{Exact finite audit}

The proof is analytic; computation is used only as an adversarial audit.  The
included checker:
\begin{enumerate}[leftmargin=2em]
  \item solves NMTS directly by enumerating occurrence matchings;
  \item builds both the base and uniformly padded \fixb\ instances;
  \item solves each reduced instance with an exact Held--Karp dynamic program;
  \item compares the answers using integer arithmetic only.
\end{enumerate}
The current recorded run covers 795 canonical balanced two-item multiset
instances and 500 random three-item instances, including duplicate values and
repeated targets, with zero mismatches.  Separately, the Held--Karp oracle was
cross-checked against complete permutation/mode enumeration on 250 random
instances.

For a visible YES certificate, take
\[
 X=\{1,2\},\quad Y=\{3,4\},\quad T=\{5,5\},\quad P=5.
\]
Then \(K=53\), and the exact endpoint chain
\[
  1\to6\to19\to1\to7\to18\to1
\]
attains 53.  For a duplicate-heavy NO example, take
\[
 X=\{1,1,1\},\quad Y=\{1,2,3\},\quad T=\{3,3,3\}.
\]
Here \(K=49\), but exact optimization gives 50: the three target arcs all
enter label 11, whereas only one connector can leave it.

\paragraph{Status.}
The reduction, realization lemma, padding gadget, and exact checker have
received independent adversarial passes in this research session.  External
expert review remains necessary before treating the result as established
literature.

\begin{thebibliography}{10}

\bibitem{nicosia2025}
G.~Nicosia, A.~Pacifici, U.~Pferschy, A.~Russo Russo, and C.~Salvatore.
\newblock Flow shop scheduling with inter-stage flexibility and blocking
constraints.
\newblock \emph{Computers \& Operations Research}, 184:107219, 2025.
\newblock \url{https://doi.org/10.1016/j.cor.2025.107219}.

\bibitem{gilmore1964}
P.~C. Gilmore and R.~E. Gomory.
\newblock Sequencing a one state-variable machine: A solvable case of the
traveling salesman problem.
\newblock \emph{Operations Research}, 12(5):655--679, 1964.
\newblock \url{https://doi.org/10.1287/opre.12.5.655}.

\bibitem{garey1979}
M.~R. Garey and D.~S. Johnson.
\newblock \emph{Computers and Intractability: A Guide to the Theory of
NP-Completeness}.
\newblock W.~H. Freeman, 1979.

\bibitem{hulett2008}
H.~Hulett, T.~G. Will, and G.~J. Woeginger.
\newblock Multigraph realizations of degree sequences: Maximization is easy,
minimization is hard.
\newblock \emph{Operations Research Letters}, 36(5):594--596, 2008.
\newblock \url{https://doi.org/10.1016/j.orl.2008.05.004}.

\bibitem{dong2021}
J.~Dong, H.~Pan, C.~Ye, W.~Tong, and J.~Hu.
\newblock No-wait two-stage flowshop problem with multi-task flexibility of
the first machine.
\newblock \emph{Information Sciences}, 544:25--38, 2021.
\newblock \url{https://doi.org/10.1016/j.ins.2020.06.052}.

\bibitem{zhong2018}
W.~Zhong and Y.~Shi.
\newblock Two-stage no-wait hybrid flowshop scheduling with inter-stage
flexibility.
\newblock \emph{Journal of Combinatorial Optimization}, 35:108--125, 2018.
\newblock \url{https://doi.org/10.1007/s10878-017-0155-8}.

\bibitem{khorasanian2017}
D.~Khorasanian and G.~Moslehi.
\newblock Two-machine flow shop scheduling problem with blocking, multi-task
flexibility of the first machine, and preemption.
\newblock \emph{Computers \& Operations Research}, 79:94--108, 2017.
\newblock \url{https://doi.org/10.1016/j.cor.2016.09.023}.

\bibitem{lin2017}
B.~M.~T. Lin, F.~J. Hwang, and J.~N.~D. Gupta.
\newblock Two-machine flowshop scheduling with three-operation jobs subject to
a fixed job sequence.
\newblock \emph{Journal of Scheduling}, 20:293--302, 2017.
\newblock \url{https://doi.org/10.1007/s10951-016-0493-x}.

\bibitem{gupta2004}
J.~N.~D. Gupta, C.~P. Koulamas, G.~J. Kyparisis, C.~N. Potts, and
V.~A. Strusevich.
\newblock Scheduling three-operation jobs in a two-machine flow shop to
minimize makespan.
\newblock \emph{Annals of Operations Research}, 129:171--185, 2004.
\newblock \url{https://doi.org/10.1023/B:ANOR.0000030687.72169.c7}.

\bibitem{dellacroce2022}
F.~Della Croce, F.~Salassa, and V.~T'kindt.
\newblock Exact solution of the two-machine flow shop problem with three
operations.
\newblock \emph{Computers \& Operations Research}, 138:105595, 2022.
\newblock \url{https://doi.org/10.1016/j.cor.2021.105595}.

\bibitem{crama2010}
Y.~Crama and H.~Gultekin.
\newblock Throughput optimization in two-machine flowshops with flexible
operations.
\newblock \emph{Journal of Scheduling}, 13(3):227--243, 2010.
\newblock \url{https://doi.org/10.1007/s10951-008-0096-2}.

\bibitem{gultekin2012}
H.~Gultekin.
\newblock Scheduling in flowshops with flexible operations: Throughput
optimization and benefits of flexibility.
\newblock \emph{International Journal of Production Economics},
140(2):900--911, 2012.
\newblock \url{https://doi.org/10.1016/j.ijpe.2012.07.011}.

\end{thebibliography}

\end{document}