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

• Autorzy: Moghaddam Atefeh , Teghem Jacques , Tuyttens Daniel , Yalaoui Farouk , Amodeo Lionel

Identyfikatory

DOI

10.2478/fcds-2019-0010

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

production scheduling; bi-objective optimization; single-machine; rejection cost

• Wydawca: Wydawnictwo Politechniki Poznańskiej
• Czasopismo: Foundations of Computing and Decision Sciences
• Rocznik: 2019
• Tom: Vol. 44, No. 2
• Strony: 179--211
• Opis fizyczny: Bibliogr. 12 poz., tab.

Twórcy

autor

Moghaddam Atefeh

• Siemens Mobility SAS, 150 Avenue de la Rápublique, 92323 Chatillon Cedex France

autor

Teghem Jacques

• Mathematics and Operational Research Unit, University of Mons, Polytechnic Faculty, Belgium

autor

Tuyttens Daniel

• Mathematics and Operational Research Unit, University of Mons, Polytechnic Faculty, Belgium

autor

Yalaoui Farouk

• Charles Delaunay Institute (ICD-LOSI), University of Technology of Troyes, France

autor

Amodeo Lionel

• Charles Delaunay Institute (ICD-LOSI), University of Technology of Troyes, France

Bibliografia

• [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).
• [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).
• [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).
• [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).
• [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).
• [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).
• [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).
• [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).
• [9] V. T’Kindt, J.-Ch. Billaut, “Multicriteria scheduling. Theory, Models and Algorithms”, Springer-Verlag Berlin Heidelberg New York (2002).
• [10] E.L. Ulungu, J. Teghem, Ph. Fortemps, D. Tuyttens, “MOSA method : A tool for solving multiobjective combinatorial optimization problems”, Journal of Multi-Criteria Decision Analysis 8(4), 221-236, (1999).
• [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).
• [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).

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).