A linear time approximation algorithm for permutation flow shop scheduling

In the last 40 years, the permutation flow shop scheduling (PFS) problem with makespan minimization has been a central problem, known for its intractability, that has been well studied from both theoretical and practical aspects. The currently best performance ratio of a deterministic approximation algorithm for the PFS was recently presented by Nagarajan and Sviridenko, using a connection between the PFS and the longest increasing subsequence problem. In a different and independent way, this paper employs monotone subsequences in the approximation analysis techniques. To do this, an extension of the Erdös–Szekeres theorem to weighted monotone subsequences is presented. The result is a simple deterministic algorithm for the PFS with a similar approximation guarantee, but a much lower time complexity.