Scheduling with Rejection to Minimize the Total Weighted Completion Time

摘要

In this paper, we address the scheduling problem with rejection in which we can choose a subset of jobs to process. Choosing not to process any job incurs a corresponding penalty. We consider the following problem for the first time: scheduling with rejection to minimize the total weighted completion time with the constraint of total penalties on identical parallel machines, where the number of identical parallel machines is constant. We show that it is NPhard and design a pseudo-polynomial time algorithm as well as an FPTAS through dynamic programming.