Ingeniería y Gestión Industrial

The Permutation Flow-Shop Scheduling Using a Genetic Algorithm-based Iterative Method

Abstract

Mahdi Eskenasi and Mehran Mehrandezh

The objective is to investigate a well-known scheduling problem, namely the Permutation Flow-Shop Scheduling with the makespan as the objective function to be minimized. Various techniques, ranging from the simple constructive algorithms to the state-of-the-art techniques, such as Genetic Algorithms (GA), have been cited in the pertinent literature to solve this type of scheduling problem. A new GA-based solution methodology was developed and implemented. In this context, the performance of a stand-alone genetic algorithm (referred to as the non-hybrid genetic algorithm) and a novel hybridized genetic algorithm amalgamated with an iterative greedy algorithm were studied. The parameters of the hybrid and the non-hybrid genetic algorithms were tuned using a Full Factorial Experimental Design and Analysis of Variance. The performance of the properly tuned hybridized GA-based algorithm was examined on the existing standard benchmark problems of Taillard and it was shown that the proposed hybridized genetic algorithm performs very well on the benchmark problems.