Solving permutation flowshop scheduling problems with a discrete differential evolution algorithm

Issue title: 21st RCRA International Workshop on “Experimental evaluation of algorithms for solving problems with combinatorial explosion”

Guest editors: Toni Mancini, Marco Maratea and Francesco Ricca

Article type: Research Article

Authors: Santucci, Valentino^{a; *} | Baioletti, Marco^a | Milani, Alfredo^{a; b}

Affiliations: [a] Department of Mathematics and Computer Science, University of Perugia, Perugia, Italy. E-mails: [email protected], [email protected], [email protected] | [b] Department of Computer Science, Hong Kong Baptist University, Hong Kong, China

Correspondence: [*] Corresponding author. E-mail: [email protected].

Abstract: In this paper a new discrete Differential Evolution algorithm for the Permutation Flowshop Scheduling Problem with the total flowtime and makespan criteria is proposed. The core of the algorithm is the distance-based differential mutation operator defined by means of a new randomized bubble sort algorithm. This mutation scheme allows the Differential Evolution to directly navigate the permutations search space. Experiments were held on a well known benchmarks suite and they show that the proposal reaches very good performances compared to other state-of-the-art algorithms. The results are particularly satisfactory on the total flowtime criterion where also new upper bounds that improve on the state-of-the-art have been found.

Keywords: Permutation flowshop scheduling problem, differential evolution, permutation-based optimization

DOI: 10.3233/AIC-150695

Journal: AI Communications, vol. 29, no. 2, pp. 269-286, 2016