A faster fully polynomial time approximation scheme for proportionate flow shop scheduling with step-deteriorating processing times

Abstract We consider a certain proportionate flow shop scheduling problem with step-deteriorating processing times and study two objective functions: makespan and sum of completion times. We reformulate these problems as monotone dynamic programs that fall into both FPTAS frameworks of Alon and Halman. Consequently, we get for each one of them an FPTAS and a strongly polynomial FPTAS, where the latter one improves upon the running time of the fastest FPTAS known to date.