Approximation Scheme for Scheduling Resumable Proportionally Deteriorating Jobs

摘要

In this paper, we investigate the problem of scheduling resumable proportionally deteriorating jobs on a single machine with a non-availability constraint. The goal is to minimize the total completion time. We show the problem is NP-hard. Furthermore, we present a fully polynomial time approximation scheme (FPTAS).