Günter Rote and Gerhard J. Woeginger:
Time complexity and linear-time approximation of the ancient two machine
flow shop
Journal of Scheduling 1 (1998), 149–155.
doi:10.1002/(SICI)1099-1425(1998100)1:3<149::AID-JOS10>3.0.CO;2-4
Abstract
We consider the scheduling problems F2|.|Cmax
and F2|no-wait|Cmax, i.e.
makespan minimization in a two machine flow shop, with and without no
wait in process. For both problems solution algorithms based on sorting
with O(n log n) running time are known, where n denotes
the number of jobs
[Johnson 1954, Gilmore and Gomory 1964].
We prove that no asymptotically faster algorithms can solve these problems.
This is done by establishing Ω(n log n) lower bounds
in the algebraic
computation tree model of computation. Moreover, we develop for every
ε>0 approximation algorithms with linear running time
O(n log(1/ε))
that deliver feasible schedules whose makespan is at
most 1+ε times the
optimum makespan.