Asymptotically optimal linear time algorithms for two-stage and three-stage flexible flow shops

We consider two-stage and three-stage flexible flow shops with parallel machines in each stage and the minimum makespan objective. We develop linear time algorithms for these problems with absolute worst-case bounds either sharper or no worse than the currently available ones and we accomplish this with lower complexity algorithms. We also demonstrate the asymptotic optimality of a class of algorithms for multistage flexible flow shop problems (which includes the proposed algorithms) under certain probabilistic assumptions on the job processing times.