Using Cuckoo Search Algorithm for Hybrid Flow Shop Scheduling Problems Under Makespan Criterion

Using Cuckoo Search Algorithm for Hybrid Flow Shop Scheduling Problems Under Makespan Criterion

M. K. Marichelvam (Mepco Schlenk Engineering College, India) and Ömür Tosun (Akdeniz University, Turkey)
Copyright: © 2018 |Pages: 22
DOI: 10.4018/978-1-5225-5134-8.ch015


In this chapter, cuckoo search algorithm (CSA) is used to solve 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 2.645.
Chapter Preview

Problem Definition

In a HFS scheduling problem, a set of n jobs are available simultaneously to be processed sequentially on different stages. Each job j has its fixed processing time for every stage s, and at each stage there is a set of identical parallel machines where some production stages may have only one machine, but at least one production stage must have multiple machines. Each job may consist of different operations. These operations will be performed by any one of the machines at different stages. The jobs arrive at first stage where the corresponding operations are to be performed and the jobs are delivered to the next stage for the completion of succeeding operations. The jobs have to pass through all the stages sequentially. The objective of scheduling is to assign jobs to the machines at the corresponding stages and determine the processing sequences on the machines so that the makespan (Cmax), i.e., the maximum completion time is minimized.

Complete Chapter List

Search this Book: