A Populated Local Search with Differential Evolution for Blocking Flowshop Scheduling Problem

Abstract

This paper presents a populated local search algorithm through a differential evolution algorithm for solving the blocking flowshop scheduling problem under makespan criterion. Iterated greedy and iterated local search algorithms are simple but extremely effective in solving scheduling problems. However these two algorithms have some parameters to be tuned for which it requires a design of experiments with expensive runs. In this paper we propose a novel multi-chromosome solution representation for both local search and differential evolution algorithm which is responsible for providing the parameters of IG and ILS algorithms. In other words these parameters are learned by the differential evolution algorithm in order to guide the local search process. We also present the greedy randomized adaptive search procedure (GRASP) for the problem on hand. The performance of the populated local search algorithm with differential evolution algorithm and the GRASP heuristic is tested on Taillard's benchmark suite and compared to the best performing algorithms from the literature. Ultimately 90 out of 120 problem instances are further improved.