Minimizing flowtime in a flowshop scheduling problem with a biased random-key genetic algorithm

摘要

In this paper, we advance the state of the art for solving the Permutation Flowshop Scheduling Problem with total flowtime minimization. For this purpose, we propose a Biased Random-Key Genetic Algorithm (BRKGA) introducing on it a new feature called shaking. With the shaking, instead to full reset the population to escape from local optima, the shaking procedure perturbs all individuals from the elite set and resets the remaining population. We compare results for the standard and the shaking BRKGA with results from the Iterated Greedy Search, the Iterated Local Search, and a commercial mixed integer programming solver, in 120 traditional instances. For all algorithms, we use warm start solutions produced by the state-of-the-art Beam-Search procedure. Computational experiments show the efficiency of proposed BRKGA, in addition to identify lower and upper bounds, as well as some optimal values, among the solutions. (C) 2019 Elsevier Ltd. All rights reserved.