Analysis shows a faster polynomial time approximation scheme for makespan and completion times in scheduling, suggesting efficiency gains.
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.
No takes yet. Share an insight, caveat, or question.
Nir Halman (2025) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: