Tight bounds for permutation flow shop scheduling

Abstract. In flow shop scheduling there are m machines and n jobs, such that every job has to be processed on the machines in the fixed order 1,...,m. In the permutation flow shop problem, it is also required that each machine processes the set of all jobs in the same order. For-mally, given n jobs along with their processing times on each machine, the goal is to compute a single permutation of the jobs σ: [n] → [n], that minimizes the maximum job completion time (makespan) of the sched-ule resulting from σ. The previously best known approximation guar-antee for this problem was O( m logm) [29]. In this paper, we obtain an improved O(min{√m,√n}) approximation algorithm for the permu-tation flow shop scheduling problem, by finding a connection between the scheduling problem and the longest increasing subsequence problem. Our approximation ratio is relative to the lower bounds of maximum job length and maximum machine load, and is the best possible such result. This also resolves an open question from [21], by algorithmically matching the gap between permutation and non-permutation schedules. We also consider the weighted completion time objective for the permuta-tion flow shop scheduling problem. Using a natural linear programming relaxation, and our algorithm for the makespan objective, we obtain an O(min{√m,√n}) approximation algorithm for minimizing the total weighted completion time, improving upon the previously best known guarantee of εm for any constant ε> 0 [30]. We give a matching lower bound on the integrality gap of our linear programming relaxation.