Research Article

An efficient genetic algorithm for a hybrid flow shop scheduling problem with time lags and sequence-dependent setup time

¹ Department of Mathematic, Payame Noor University, Tehran, Iran
² Department of Industrial Engineering, Bu-Ali Sina University, Hamedan, Iran
³ Department of Industrial Engineering, Birjand University of Technology, Birjand, Iran

^* e-mail: m.farahmand.m@gmail.com

Received: 24 November 2013
Accepted: 23 November 2014

Abstract

In this paper, a hybrid flow shop scheduling problem with a new approach considering time lags and sequence-dependent setup time in realistic situations is presented. Since few works have been implemented in this field, the necessity of finding better solutions is a motivation to extend heuristic or meta-heuristic algorithms. This type of production system is found in industries such as food processing, chemical, textile, metallurgical, printed circuit board, and automobile manufacturing. A mixed integer linear programming (MILP) model is proposed to minimize the makespan. Since this problem is known as NP-Hard class, a meta-heuristic algorithm, named Genetic Algorithm (GA), and three heuristic algorithms (Johnson, SPTCH and Palmer) are proposed. Numerical experiments of different sizes are implemented to evaluate the performance of presented mathematical programming model and the designed GA in compare to heuristic algorithms and a benchmark algorithm. Computational results indicate that the designed GA can produce near optimal solutions in a short computational time for different size problems.