A hybrid genetic algorithm for no-wait flowshop scheduling problem

Lin-Yu Tseng and Ya-Tai Lin

International Journal of Production Economics, 2010, vol. 128, issue 1, 144-152

Abstract: In this paper, a hybrid genetic algorithm is proposed to solve the no-wait flowshop scheduling problem with the makespan objective. The proposed algorithm hybridizes the genetic algorithm and a novel local search scheme. The OA-crossover operator is designed to enhance the capability of intensification in the genetic algorithm. The proposed local search scheme combines two local search methods: the Insertion Search (IS) and a novel local search method called the Insertion Search with Cut-and-Repair (ISCR). These two local search methods play different roles in the search process. The Insertion Search is responsible for searching a small neighborhood while the Insertion Search with Cut-and-Repair is responsible for searching a large neighborhood. The experimental results show the advantage of combining the two local search methods. Extensive experiments were conducted to evaluate the proposed hybrid genetic algorithm and the results revealed that the proposed algorithm is very competitive. It obtained the same best solutions that were reported in the literature for all problems in the benchmark provided by Carlier (1978). Also, it improved 5 out of the 21 current best solutions reported in the literature and achieved the current best solutions for 14 of the remaining 16 problems in the benchmark presented by Reeves (1995). Furthermore, the proposed algorithm was applied to effectively solve the 120 problems in the benchmark provided by Taillard (1990).

Keywords: Genetic; algorithm; Local; search; Hybrid; genetic; algorithm; No-wait; flowshop; scheduling (search for similar items in EconPapers)
Date: 2010
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0925-5273(10)00214-8
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:proeco:v:128:y:2010:i:1:p:144-152

Access Statistics for this article

International Journal of Production Economics is currently edited by Stefan Minner

More articles in International Journal of Production Economics from Elsevier
Bibliographic data for series maintained by Catherine Liu ().