Minimising the makespan on parallel identical machines with log-linear position-dependent processing times
研究并行同速机上具有对数线性学习/老化效应的最小化最大完工时间调度问题，提出全多项式时间近似方案，通过动态规划实现可证明的ε加性近似。
This article studies the minimum makespan scheduling problem on parallel identical machines with the log-linear learning/ageing effect, also known as polynomial positional learning/ageing effect. To develop a Fully Polynomial Time Approximation Scheme to the problem, we start with an intermediate artificial variant that rounds the values to integers and restricts the solutions to instances sorted in the shortest/longest processing time order. To this end, we propose a dynamic programming algorithm and show that the difference between its returned value and the minimum makespan of the original problem is independent of the processing times. This then leads to an algorithm with provable guaranteed ϵ-additive approximation and pseudo-polynomial running time algorithm, resulting in the desired fully polynomial time approximation solution to the original, not restricted problem.