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

Atefeh Moghaddam (1) , Lionel Amodeo (1) , Farouk Yalaoui (1) , Behrooz Karimi (2)

1 LOSI - Laboratoire d'Optimisation des Systèmes Industriels
2 AUT - Amirkabir University of Technology

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.

Domaines: Recherche opérationnelle [math.OC]; Optimisation et contrôle [math.OC]

Atefeh Moghaddam, Lionel Amodeo, Farouk Yalaoui, Behrooz Karimi. Single Machine Scheduling with Rejection: Minimizing Total Weighted Completion Time and Rejection Cost. International Journal of Applied Evolutionary Computation, 2012, 3 (2), pp.42-61. ⟨10.4018/jaec.2012040103⟩. ⟨hal-02507770⟩