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 com pletion time (without using idle times). This problem has applications in the sequencing of maintenance actions for modular gas turbine airc raft engines. Up to now, only approximation algorithms were known whos e worst case ratio was bounded strictly away from one. In this note, w e derive the first polynomial-time approximation scheme for this probl em. The time complexity of our algorithms is O(c(epsilon)n log m), whe re c(epsilon) is a constant that depends on the desired precision E. ( C) 1997 Elsevier Science B.V.