The more practical and interesting versions of the permutation flowshop scheduling problem (PFSP) have a variety of objective criteria to be optimized simultaneously. Multi-objective PFSP is also a relevant combinatorial multi-objective optimization problem. In this paper we propose a multi-objective evolutionary algorithm for PFSP by extending the previously proposed discrete differential evolution (DE) scheme for single-objective PFSP. This is the first application of the algebraic-based discrete DE to multi-objective problems. The algorithm is extended by adopting a variety of crossover and multi-objective selection operators. Among these, the multi-objective α-selection is a novelty of this work and can be decoupled from DE and used also in other evolutionary algorithms. The other crossover and selection operators have been taken from the existing literature and, where required, have been adapted to the problem at hand. An experimental evaluation has been conducted on all the three bi-objective PFSPs among the makespan, total flowtime and total tardiness criteria. The results show that the proposed approach is competitive with respect to the state-of-the-art algorithms.
AffenzellerM., WagnerS., WinklerS. and BehamA., Genetic algorithms and genetic programming: Modern concepts and practical applications, Crc Press, 2009.
2.
ArmentanoV.A. and ClaudioJ.E., An application of a multi-objective tabu search algorithm to a bicriteria flowshop problem, Journal of Heuristics10(5) (2004), 463–481.
3.
ArroyoJ.E.C. and ArmentanoV.A., Genetic local search for multi-objective flowshop scheduling problems, European Journal of Operational Research167(3) (2005), 717–738.
4.
BagchiT.P., Pareto-Optimal Solutions for Multi-objective Production Scheduling Problems, SpringerBerlin, Heidelberg, 2001, pp. 458–471.
5.
BaiolettiM., MilaniA. and SantucciV., Linear ordering optimization with a combinatorial differential evolution. In 2015 IEEE International Conference on Systems, Man, and Cybernetics (SMC), 2015, pp. 2135–2140.
6.
BaiolettiM., MilaniA. and SantucciV., An extension of algebraic differential evolution for the linear ordering problem with cumulative costs. In Proc of PPSN XIV - Parallel Problem Solving from Nature 2016, Springer International Publishing, 2016, pp. 123–133.
7.
ChakravarthyK. and RajendranC., A heuristic for scheduling in a flowshop with the bicriteria of makespan and maximum tardiness minimization, Production Planning & Control10(7) (1999), 707–714.
8.
CoelloC.A., AguirreA.H. and ZitzlerE., Evolutionary multi-objective optimization, European Journal of Operational Research181(3) (2007), 1617–1619.
9.
CorneD.W., JerramN.R., KnowlesD.J. and OatesM.J., PESA-II: Region-based selection in evolutionary multiobjective optimization, Morgan Kaufmann, San Francisco, 2001, pp. 283–290.
10.
CorneD.W., KnowlesJ.D. and OatesM.J., The Pareto Envelope-Based Selection Algorithm for Multiobjective Optimization, SpringerBerlin Heidelberg, 2000, pp. 839–848.
11.
DebK., PratapA., AgarwalS. and MeyarivanT., A fast and elitist multiobjective genetic algorithm: Nsga-ii, IEEE Transactions on Evolutionary Computation6(2) (2002), 182–197.
12.
DebK., Multi-objective optimization using evolutionary algorithms, volume 16. John Wiley & Sons, 2001.
13.
DebK., AgrawalS., PratapA. and MeyarivanT., A fast and elitist multiobjective genetic algorithm: NSGA-II, IEEE Trans Evolutionary Computation6(2) (2002), 182–197.
14.
EibenA.E. and SmithJ.E., Introduction to Evolutionary Computing. Springer-VerlagBerlin Heidelberg, 2003.
15.
GeigerM.J., On operators and search space topology in multi-objective flow shop scheduling, European Journal of Operational Research181(1) (2007), 195–206.
16.
GoldbergD.E. and LingleR.Jr., Alleles loci and the traveling salesman problem. In Proceedings of the 1st International Conference on Genetic Algorithms, Hillsdale, NJ, USA, 1985, pp. 154–159. L. Erlbaum Associates Inc.
17.
GuptaJ. and StaffordJ.E., Flowshop scheduling research after five decades, European Journal of Operational Research169(3) (2006), 699–711.
18.
GuptaJ.N.D. and StaffordE.F.Jr, Flowshop scheduling research after five decades, European Journal of Operational Research169(3) (2006), 699–711.
19.
HoosH.H. and StützleT., Stochastic local search: Foundations & applications, Elsevier, 2004.
20.
KimM., HiroyasuT., MikiM. and WatanabeS., Spea2+: Improving the performance of the strength pareto evolutionary algorithm 2. In International Conference on Parallel Problem Solving from Nature, Springer, 2004, pp. 742–751.
21.
KnowlesJ.D. and CorneD.W., Approximating the nondominated front using the pareto archived evolution strategy, Evol Comput8(2) (2000), 149–172.
22.
KollatJ.B. and ReedP.M., The Value of Online Adaptive Search: A Performance Comparison of NSGAII, ɛ-NSGAII and ɛMOEA, SpringerBerlin Heidelberg, 2005, pp. 386–398.
23.
KukkonenS. and LampinenJ., An extension of generalized differential evolution for multi-objective optimization with constraints. In Proc of PPSN VIII - Parallel Problem Solving from Nature 2004, 2004, pp. 752–761.
24.
López-IbáñezM., Dubois-LacosteJ., StützleT. and BirattariM., The irace package, iterated race for automatic algorithm configuration. Technical Report TR/IRIDIA/2011-004, IRIDIA, Université Libre de Bruxelles, Belgium, 2011.
25.
MilaniA. and SantucciV., Community of scientist optimization: An autonomy oriented approach to distributed optimization, AI Communications25(2) (2012), 157–172.
26.
MinellaG., RuizR. and CiavottaM., A review and evaluation of multiobjective algorithms for the flowshop scheduling problem, INFORMS Journal on Computing20(3) (2008), 451–471.
27.
MuhlenbeinH., Evolution in time and space-the parallel genetic algorithm. In Foundations of genetic algorithms, 1991, pp. 316–337.
28.
MurataT., IshibuchiH. and GenM., Specification of Genetic Search Directions in Cellular Multi-objective Genetic Algorithms, Springer Berlin Heidelberg, Berlin, Heidelberg, 2001, pp. 82–95.
29.
MurataT., IshibuchiH. and TanakaH., Multiobjective genetic algorithm and its applications to flowshop scheduling, Computers & Industrial Engineering30(4) (1996), 957–968.
30.
PasupathyT., RajendranC. and SureshR.K., A multi-objective genetic algorithm for scheduling in flow shops to minimize the makespan and total flow time of jobs, The International Journal of Advanced Manufacturing Technology27(7) (2006), 804–815.
31.
PriceK.V., StornR.M. and LampinenJ.A., Differential Evolution: A Practical Approach to Global Optimization. Springer, Berlin, 2005.
32.
RobičT. and FilipičB., DEMO: Differential evolution for multiobjective optimization. In Evolutionary Multi-Criterion Optimization, Third International Conference, EMO 2005, Guanajuato, Mexico, Proceedings, 2005, pp. 520–533.
33.
SantucciV., BaiolettiM. and MilaniA., Algebraic differential evolution algorithm for the permutation flowshop scheduling problem with total flowtime criterion, IEEE Transactions on Evolutionary Computation20(5) (2016), 682–694.
34.
SantucciV., BaiolettiM. and MilaniA., Solving permutation flowshop scheduling problems with a discrete differential evolution algorithm, AI Communications29(2) (2016), 269–286.
35.
SantucciV., BaiolettiM. and MilaniA., A differential evolution algorithm for the permutation flowshop scheduling problem with total flow time criterion. In Proc of PPSN XIII - Parallel Problem Solving from Nature 2014, 2014, pp. 161–170.
36.
SantucciV., BaiolettiM. and MilaniA., An algebraic differential evolution for the linear ordering problem. In Proceedings of Genetic and Evolutionary Computation Conference (GECCO 2015), 2015, pp. 1479–1480.
37.
SantucciV., BaiolettiM. and MilaniA., A discrete differential evolution algorithm for multi-objective permutation flowshop scheduling. In Proceedings of IPS 2015 - Italian Workshop on Planning and Scheduling, 2015, pp. 80–87.
38.
SantucciV., MilaniA. and VellaF., A study on the synchronization behaviour of differential evolution and a self-adaptive extension, Journal of Artificial Intelligence and Soft Computing Research2(4) (2012), 279–301.
39.
SchiavinottoT. and StützleT., A review of metrics on permutations for search landscape analysis, Computers and Operational Research34(10) (2007), 3143–3153.
40.
SrinivasN. and KalyanmoyD., Muiltiobjective optimization using nondominated sorting in genetic algorithms, Evol Comput2(3) (1994), 221–248.
41.
SureshR.K. and MohanasundaramK.M., Pareto archived simulated annealing for permutation flow shop scheduling with multiple objectives. In Cybernetics and Intelligent Systems, 2004 IEEE Conference on, volume 2, 2004, pp. 712–717.
42.
SyswerdaG., Schedule optimization using genetic algorithms. In
DavisLawrence, editor, Handbook of Genetic Algorithms, Van Nostrand Reinhold, New York, NY, 1991, pp. 332–349.
43.
TateD.M. and SmithA.E., A genetic approach to the quadratic assignment problem, Computers and Operations Research22(1) (1995), 73–83.
44.
VaradharajanT.K. and RajendranC., A multi-objective simulated-annealing algorithm for scheduling in flowshops to minimize the makespan and total flowtime of jobs, European Journal of Operational Research167(3) (2005), 772–795.
45.
WhitleyL.D., StarkweatherT. and FuquayD., Scheduling problems and traveling salesmen: The genetic edge recombination operator. In Proceedings of the 3rd International Conference on Genetic Algorithms, San Francisco, CA, USA, 1989, pp. 133–140. Morgan Kaufmann Publishers Inc.
46.
YeniseyM.M. and YagmahanB., Multi-objective permutation flow shop scheduling problem: Literature review, classification and current trends, Omega45 (2014), 119–135.
47.
ZitzlerE. and ThieleL., Multiobjective evolutionary algorithms: A comparative case study and the strength pareto approach, IEEE Transactions on Evolutionary Computation3(4) (1999), 257–271.
48.
ZitzlerE. and KünzliS., Indicator-Based Selection in Multiobjective Search, SpringerBerlin Heidelberg, 2004, pp. 832–842.
