Performance Comparison of Cuckoo Search Algorithm to Solve the Hybrid Flow Shop Scheduling Benchmark Problems with Makespan Criterion

Performance Comparison of Cuckoo Search Algorithm to Solve the Hybrid Flow Shop Scheduling Benchmark Problems with Makespan Criterion

M.K. Marichelvam, Ömür Tosun
Copyright: © 2016 |Pages: 14
DOI: 10.4018/IJSIR.2016040101
(Individual Articles)
No Current Special Offers


In this work, the performance of cuckoo search algorithm (CSA) is measured solving the multistage hybrid flow shop (HFS) scheduling problems with parallel machines. The objective is the minimization of makespan. The HFS scheduling problems are proved to be strongly non-deterministic polynomial time-hard (NP-hard). Proposed CSA algorithm has been tested on benchmark problems addressed in the literature against other well-known algorithms. The results are presented in terms of percentage deviation (PD) of the solution from the lower bound. The results indicate that the proposed CSA algorithm is quite effective in reducing makespan because average PD is observed as 1.531, whereas the next best algorithm has result of average PD of 2.295 which is in general nearly 50% worse and other algorithms start from 3.833.
Article Preview

1. Introduction

Scheduling is one of the most important decision making process in production and operation management. The hybrid flow shop (HFS) environment is a combination of parallel machine and flow shop environments. The HFS scheduling problem was first addressed by Arthanari and Ramamurthy (Arthanari & Ramamurthy, 1971). The HFS scheduling problems are NP-hard type combinatorial optimization problems (Gupta 1988; Hoogeveen et al. 1996). The HFS is also called as flow shop with multiple processors (machines), flexible flow shop (FFS), multiprocessor flow shop, or flow shop with parallel machines (Ribas et al. 2010). Researchers applied branch and bound method (Brah & Hunsuchker, 1991; Moursli & Pochet, 2000) and heuristics (Haouari & M’Hallah, 1997; Riane et al. 1998; Oguz et al. 2003; Wang & Liu, 2013) to solve the problems. Many metaheuristics such as genetic algorithm (GA) (Hou et al. 1994; Serifoglu & Ulusoy, 2004; Oguz & Ercan, 2005; Shenassa & Mahmoodi, 2006; Shiau et al. 2008; Kahraman et al. 2008; Engin et al. 2011), simulated annealing (SA) algorithm (Serifoglu & Tiryaki, 2002; Low 2005; Naderi et al. 2009; Wang et al. 2010), ant colony optimization (ACO) algorithm (Ying & Lin, 2006; Alaykiran et al. 2007), artificial immune system (AIS) algorithm (Alisantoso et al. 2003; Engin & Döyen, 2004; Niu et al. 2009; Ying 2012) and particle swarm optimization (PSO) algorithm (Liao et al. 2012; Chou 2013; Li et al. 2014) are utilized by the researchers to solve the HFS problems. Tabu search (TS) algorithm (Bozejko et al. 2013), greedy algorithm (Kahraman et al. 2010) and water flow algorithm (Tran & Ng, 2013) are also applied to solve the HFS scheduling problems. The detailed review on HFS scheduling problems and comparison of different algorithms can be found in (Ruiz & Vazquez-Rodriguez, 2010; Jungwattanakit et al., 2009; Syam & Al-Harkan, 2012, respectively).

Complete Article List

Search this Journal:
Volume 14: 3 Issues (2023)
Volume 13: 4 Issues (2022)
Volume 12: 4 Issues (2021)
Volume 11: 4 Issues (2020)
Volume 10: 4 Issues (2019)
Volume 9: 4 Issues (2018)
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing