Approximating the $2$-Machine Flow Shop Problem with Exact Delays Taking Two Values
2017
In the $2$-Machine Flow Shop problem with exact delays the operations of each job are separated by a given time lag (delay). Leung et al. (2007) established that the problem is strongly NP-hard when the delays may have at most two different values. We present further results for this case: we prove that the existence of $(1.25-\varepsilon)$-approximation implies P$=$NP and present a $2$-approximation algorithm.
- Correction
- Cite
- Save
- Machine Reading By IdeaReader
7
References
0
Citations
NaN
KQI