A polynomial-time approximation scheme for maximizing the minimum machine completion time

We consider the problem of assigning a set of n jobs to a system of m identical parallel machines so as to maximize the earliest machine completion time (without using idle times). This problem has applications in the sequencing of maintenance actions for modular gas turbine aircraft engines. Up to now, only approximation algorithms were known whose worst case ratio was bounded strictly away from one. In this note, we derive the first polynomial-time approximation scheme for this problem. The time complexity of our algorithms is O(cnlogm), where c is a constant that depends on the desired precision .