.png){kind=icon}
.png){kind=icon}
Return
A faster fully polynomial time approximation scheme for proportionate flow shop scheduling with step-deteriorating processing times
.png){kind=icon}
OA
AI
DOI：10.1007/s10951-025-00859-8.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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.
Keywords:
Scheduling
Approximation schemes
Proportionate flow shop
Monotone dynamic programming.
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.