Two-machine flow scheduling with downtime approximation and limits
Two-Machine Flow Shop with a Fixed Non-Availability Interval on the Second Machine
Discrete Mathematics
Summary
This work looks at a job scheduling problem where two machines work in order but the second machine is unavailable during a fixed time period. If a job is interrupted during that downtime, it has to start again when the machine is ready. The authors provide an approximation method that runs quickly and also an exact method that takes longer but finds the best schedule. They also prove it's impossible to find an efficient algorithm that always gets arbitrarily close to the best solution unless a major computer science question is resolved.
What this means in practice
- •For manufacturing schedulers: Schedule production lines where one machine temporarily stops working and tasks must restart if interrupted, improving planning accuracy.
- •For industrial automation planners: Optimize workflows with unavoidable maintenance periods on a key machine that require restarting interrupted jobs for better throughput estimation.
A theory result. No direct application yet.
Authors
Hao Lu, Yuan Yuan, Xingwu Liu, Xin Han
Abstract
This paper investigates a two-machine permutation flow shop in which the second machine is unavailable during one fixed interval $[s,t]$. We consider the non-resumable setting: an operation interrupted by the interval must restart from the beginning after the machine becomes available. The objective is to minimize the makespan. We establish three results. First, we give a polynomial-time $10/7$-approximation algorithm. Second, we develop a pseudopolynomial-time exact dynamic program. Third, we prove that the problem does not admit a fully polynomial-time approximation scheme (FPTAS) unless $\mathrm{P}=\mathrm{NP}$, even when the non-availability interval has unit length. Together, these results characterize a distinctive complexity profile: exact optimization is possible in pseudopolynomial time, whereas the usual route from such an algorithm to an FPTAS is impossible unless $\mathrm{P}=\mathrm{NP}$. They also reveal an approximability separation from the corresponding non-resumable problem with the interval on the first machine.