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 multiobjective 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 a-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.

A discrete differential evolution algorithm for multi-objective permutation flowshop scheduling

Santucci Valentino
2016-01-01

Abstract

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 multiobjective 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 a-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.
2016
Differential evolution; permutation flowshop scheduling; multi-objective optimization; combinatorial optimization
File in questo prodotto:
File Dimensione Formato  
ia16_baioletti_milani_santucci.pdf

accesso aperto

Tipologia: Documento in Pre-print
Licenza: Creative commons
Dimensione 503.52 kB
Formato Adobe PDF
503.52 kB Adobe PDF Visualizza/Apri
ia2016.pdf

non disponibili

Tipologia: Versione Editoriale (PDF)
Licenza: Creative commons
Dimensione 665.56 kB
Formato Adobe PDF
665.56 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.12071/11202
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
social impact