Abstract: We study the early work scheduling problem on identical parallel machines in order to maximize the total early work, i.e., the parts of non-preemptive jobs that are executed before a common due date. By preprocessing and constructing an auxiliary instance which has several good properties, for any desired accuracy ε, we propose an efficient polynomial time approximation scheme with running time O (f (1/ε) n), where n is the number of jobs and f (1/ε) is exponential in 1/ε, and a fully polynomial time approximation scheme with running time O (1/ε^2m+1 + n) when the number of machines is fixed.

Key words: Scheduling, Early work, Polynomial time approximation scheme, Efficient polynomial time approximation scheme, Fully polynomial time approximation scheme