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

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

Atefeh Moghaddam (University of Technology of Troyes, France), Lionel Amodeo (University of Technology of Troyes, France), Farouk Yalaoui (University of Technology of Troyes, France) and Behrooz Karimi (Amirkabir University of Technology, Iran)
Copyright: © 2012 |Pages: 20
DOI: 10.4018/jaec.2012040103
OnDemand PDF Download:
No Current Special Offers


In this paper, the authors consider a single machine scheduling problem with rejection. In traditional research, it is assumed all jobs must be processed. However, in the real-world situation, certain jobs can be rejected. In this study, the jobs can be either accepted and scheduled or be rejected at the cost of a penalty. Two objective functions are considered simultaneously: (1) minimization of the sum of weighted completion times for the accepted jobs, and (2) minimization of the sum of penalties for the rejected jobs. The authors apply two-phase method (TPM), which is a general technique to solve bi-objective combinatorial optimization problems, to find all supported and non-supported solutions for small-sized problems. The authors present a mathematical model for implementing both phases. On the other hand, three different bi-objective simulated annealing algorithms have also been developed to find a good estimation of Pareto-optimal solutions for large-sized problems. Finally the authors discuss the results obtained from each of these algorithms.
Article Preview

Problem Definition

We are given n jobs j=1,..., n, each with a nonnegative processing time pj, a weight value wj, and a rejection penalty rj 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 Cj. 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 rj.

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 byjaec.2012040103.m01. 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 jaec.2012040103.m02. It has been shown that adding the option of rejection makes the problem NP-hard (Engels et al., 2003).

Complete Article List

Search this Journal:
Open Access Articles: Forthcoming
Volume 13: 4 Issues (2022): Forthcoming, Available for Pre-Order
Volume 12: 4 Issues (2021): 3 Released, 1 Forthcoming
Volume 11: 4 Issues (2020)
Volume 10: 4 Issues (2019)
Volume 9: 4 Issues (2018)
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing