Toward an Efficient Resolution for a Single-machine Bi-objective Scheduling Problem with Rejection

Moghaddam, Atefeh; Teghem, Jacques; Tuyttens, Daniel; Yalaoui, Farouk; Amodeo, Lionel

doi:10.2478/fcds-2019-0010

Abstract

We consider a single-machine bi-objective scheduling problem with rejection. In this problem, it is possible to reject some jobs. Four algorithms are provided to solve this scheduling problem. The two objectives are the total weighted completion time and the total rejection cost. The aim is to determine the set of efficient solutions. Four heuristics are described; they are implicit enumeration algorithms forming a branching tree, each one having two versions according to the root of the tree corresponding either to acceptance or rejection of all the jobs. The algorithms are first illustrated by a didactic example. Then they are compared on a large set of instances of various dimension and their respective performances are analysed.

References

[1] Y. Bartal, S. Leonardi, A. Marchetti-Spaccamela, J. Sgall, L. Stougie, “Multiprocessor scheduling with rejection”, Journal of Discrete Mathematics 13(1), 64–78, (2000).10.1137/S0895480196300522
Search in Google Scholar Back to article
[2] J. Blazewicz, K.H. Ecker, E. Pesch, G. Schmidt, J. Weglarz, “Handbook on scheduling : From theory to applications”, Springer Berlin Heidelberg New York (2007).
Search in Google Scholar Back to article
[3] K. Deb, S. S. Agrawal, A. Pratap, T. Meyarivan, “A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II”, Lecture Notes in Computer Sciences, 1917, 849–858, (2000).10.1007/3-540-45356-3_83
Search in Google Scholar Back to article
[4] F. Dugardin, F. Yalaoui, L. Amodeo “New multi-objective method to solve reentrant hybrid flow shop scheduling problem”, European Journal of Operational Research 203(1), 22–31, (2010).10.1016/j.ejor.2009.06.031
Search in Google Scholar Back to article
[5] Z.-H. Jia, M.-L. Pei, J.Y.-T. Leung “Multi-objective ACO algorithms to minimize the makespan and the total rejection cost on BPMs with arbitrary job weights”, International Journal of Systems Science 48 (16), 3542–3557, (2017).10.1080/00207721.2017.1387314
Search in Google Scholar Back to article
[6] A. Moghaddam, F. Yalaoui, L. Amodeo, “Lorenz versus Pareto dominance in a single machine scheduling problem with rejection”, Lecture Notes in Computer Science 6576, 520–534, (2011).10.1007/978-3-642-19893-9_36
Search in Google Scholar Back to article
[7] A. Moghaddam, L. Amodeo, F. Yalaoui, B. Karimi “Single machine scheduling with rejection minimizing total weighted completion time and rejection cost”, International Journal of Applied Evolutionary Computation 3 (2), 42–61, (2012).10.4018/jaec.2012040103
Search in Google Scholar Back to article
[8] A. Moghaddam, F. Yalaoui, L. Amodeo, “Efficient meta-heuristics based on various dominance criteria for a single-machine bi-criteria scheduling problem with rejection”, Journal of Manufacturing Systems 34(C), 12–22, (2015).10.1016/j.jmsy.2014.09.006
Search in Google Scholar Back to article
[9] V. T'Kindt, J.-Ch. Billaut, “Multicriteria scheduling. Theory, Models and Algorithms”, Springer-Verlag Berlin Heidelberg New York (2002).10.1007/978-3-662-04986-0_4
Search in Google Scholar Back to article
[10] E.L. Ulungu, J. Teghem, Ph. Fortemps, D. Tuyttens, “MOSA method : A tool for solving multi-objective combinatorial optimization problems”, Journal of Multi- Criteria Decision Analysis 8(4), 221–236, (1999).10.1002/(SICI)1099-1360(199907)8:4<;221::AID-MCDA247>3.0.CO;2-O
Search in Google Scholar Back to article
[11] D.-J. Wang, Y. Yin, M. Liu, “Bicriteria scheduling problems involving job rejection, controllable processing times and rate-modifying activity”, International Journal of Production Research 54(12), 3691–3705, (2016).10.1080/00207543.2015.1136081
Search in Google Scholar Back to article
[12] L. Zhang, L. Lu, S. Li, “New results on two-machine flow-shop scheduling with rejection”, Journal of Combinatorial Optimization 31 (4), 1493–1504, (2016).10.1007/s10878-015-9836-3
Search in Google Scholar Back to article

Toward an Efficient Resolution for a Single-machine Bi-objective Scheduling Problem with Rejection

Abstract

Paradigm

My account