Single Machine Scheduling with Rejection: Minimizing Total Weighted Completion Time and Rejection Cost

Problem Definition

We are given n jobs j=1,..., n, each with a nonnegative processing time p_j, a weight value w_j, and a rejection penalty r_j in an off-line environment. For each job j we must decide whether to accept and schedule it (on a machine that can handle only one job at a time) or to reject it. If we schedule job j, we denote its completion time by C_j. Preemption is not allowed, that is, once processing on a job has been started, we must finish it without interruption. If we reject job j, we pay its rejection penalty r_j.

Our goal is to choose a subset S of the n jobs to schedule on a single machine so as to minimize the sum of weighted completion times of the scheduled jobs and penalties of the rejected jobs. We denote the set of rejected jobs by. Engels et al. (2003) have considered the summation of these two objective functions and treated the problem as a single objective one. They have denoted the overall optimality criterion as . It has been shown that adding the option of rejection makes the problem NP-hard (Engels et al., 2003).