Parallel Machine Scheduling of Deteriorating Jobs With Rejection and An Availability Constraint

In this paper, we explored the nonresumable deteriorating job scheduling with machine availability constraints and rejection. The research presented here has focused on two key issues. First, it is assumed that jobs have a different basic processing time and the same deterioration rate. The objective is to minimize the total completion times of the accepted jobs plus the total penalty of the rejected jobs. We present a pseudopolynomial‐time dynamic programming exact algorithm and subsequently develop it into a fully polynomial‐time approximation scheme for the case where machine disruptions occur only on one of the machines. Second, we consider the scheduling problem in which the actual processing time of the job is a proportional function of its starting time. The objective is to minimize the weighted sum of completion times of the accepted jobs plus the total penalty of the rejected jobs. We present an alternative fully polynomial‐time approximation scheme for the case where machine disruptions occur only on one of the machines.