Approximation Schemes for Parallel Machine Scheduling to Maximize Total Weighted Early Work With a Common Due Date

ABSTRACT In this article, we study a parallel machine scheduling problem with a common due date to maximize total weighted early work. We present the first EPTAS (efficient polynomial time approximation scheme) for this scheduling problem. In the EPTAS, we first schedule the large jobs with rounded processing times via an integer programming formulation and a network‐flow‐based algorithm, followed by further scheduling the small jobs via a greedy method. For the special case in which the number of machines is fixed, we design an FPTAS (fully polynomial time approximation scheme).