##
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|.|`C`_{max}
and F2|no-wait|`C`_{max}, 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.