Parallel-machine scheduling with machine unavailability to maximize total early work
研究了机器在特定时段不可用的平行机调度问题，目标是最大化所有作业在截止日期前完成的工作量总和，提出了动态规划算法、全多项式时间近似方案和2-近似启发式算法。
This article considers a parallel-machine scheduling problem in which machines are unavailable to process jobs for a specified period. The objective is to maximize the total amount of early work, where the early work of a job is the amount of processing time performed before its due date. Since this problem is NP-hard, we propose a pseudo-polynomial time dynamic programming algorithm, and based on it, we further provide a fully polynomial time approximation scheme. The time complexity of these two algorithms is relatively high; to this end, we also offer a 2-approximation ratio heuristic algorithm to help solve large-scale problems, and we show that the bound is tight.