Approximation Schemes for Parallel Machine Scheduling to Maximize Total Weighted Early Work With a Common Due Date
研究了并行机调度问题，目标是在共同截止日期下最大化总加权提前工作，提出了首个高效多项式时间近似方案（EPTAS），并针对机器数固定的特殊情况设计了完全多项式时间近似方案（FPTAS）。
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).