Parallel-machine scheduling with machine unavailability to maximize total early work

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.