Cuckoo Search Algorithm for Solving Real Industrial Multi-Objective Scheduling Problems

Cuckoo Search Algorithm for Solving Real Industrial Multi-Objective Scheduling Problems

Mariappan Kadarkarainadar Marichelvam (Mepco Schlenk Enginering College, India) and Mariappan Geetha (Kamaraj College of Engineering and Technology, India)
Copyright: © 2018 |Pages: 13
DOI: 10.4018/978-1-5225-2255-3.ch379
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

A multistage hybrid flow shop scheduling problem is considered in this chapper with the objective of minimizing the makespan and mean flow time. Since the problem is NP-hard in nature, many heuristics and meta-heuristics were developed by the researchers. cuckoo search algorithm is one of the recently developed meta–heuristic algorithms inspired by the social behavior of cuckoos. The cuckoo search algorithm is presented in this paper to solve the hybrid flow shop scheduling problems. To illustrate the proposed algorithm, data sets from a steel furniture manufacturing company are used. The computational results show that the proposed algorithm is better than many other algorithms.
Chapter Preview
Top

Introduction

Scheduling is an essential task in our day-to-day life that helps us to shape up our daily activities. The arrival and the departure of airplanes have to be scheduled in an airport. The class hours and the examinations are scheduled in the schools and Universities. Schedules are prepared in industries too. Today, industries need meticulous planning and scheduling to meet the customer demands. Due to globalization and liberalization the attributes of the customers have changed. Hence, industries ought to satisfy them by improving the quality, reducing the price and despatching the goods on time. Scheduling is one of the most important decision making processes. Scheduling is defined as a process of allocating resources over time to perform the assigned tasks effectively (Baker & Trietsch 2009). The machines, equipment, facilities, computers and operators are the important resources in all organizations. Effective scheduling leads to improve the productivity, reduce the inventory, improve the production efficiency, minimize the production time and cost and hence increase the efficiency of the production system. Different types of scheduling environments were addressed by Pinedo (1995). Among them the hybrid flow shop (HFS) environment plays a vital role as many industries resemble it. The HFS has also been called as a flexible flowshop, multiprocessor flow shop, flexible flow line, flow shop with multiple processors or a flow shop with parallel machines by Ribas et al. (2010). Different operations are performed in different machines in a simple flow shop. The HFS consists of a set of production stages in which each stage has multiple parallel machines. An HFS consists of both the flow shop and parallel machine environments. The parallel machine scheduling system involves the scheduling of a set of immediately available jobs, each on one of the parallel machines. The simple flow shop scheduling system is described as the sequencing of a set of immediately available jobs through each of the ordered work centers. There are two or more work centers in this system but only one machine at each work center. In the HFS, some stages may have only one machine. But, at least one stage should have two or more parallel machines. The machines may be identical, uniform or non-uniform. Some of the jobs may skip some of the stages in the HFS environment. The jobs flow in unidirectional in the HFS environment. Though many researchers have addressed the HFS scheduling problems for more than 40 years, only a few researchers have addressed the real-industrial scheduling problems with multiple objectives which are conflicting naturally with each other. Hence, in this paper a bi-objective HFS scheduling problem is considered. The objective is to minimize the makespan and mean flow time. The layout of an M–stage hybrid flow shop environment is given in figure 1.

Figure 1.

Layout of the hybrid flow shop environment

Hoogeveen et al. (1996) proved that a two-stage hybrid flow shop scheduling problem is NP-hard in the strong sense even if there is only one machine on the first stage and two machines on the second stage. Hence, we cannot find the optimal solutions for these problems in a reasonable time. As the hybrid flow shop scheduling problems are NP-hard problems, the problems cannot be solved by exact algorithms. Researchers proposed many heuristics and meta-heuristics to solve the hybrid flow shop scheduling problems. Cuckoo search algorithm is a recently developed meta-heuristic algorithm. In this chapter, the cuckoo search algorithm is proposed to solve the multi-objective hybrid flow shop scheduling problems.

Top

Background

Hybrid flow shop scheduling problem was first proposed by Arthanari and Ramamurthy (1971). Researchers have developed many heuristics and meta-heuristics to solve such problems and to obtain optimal or near optimal solutions with considerably less computational time. Lee and Vairaktarakis (1994) proposed heuristics to minimize makespan for hybrid flow shop scheduling problems. Riane et al. (1998) proposed efficient heuristics to minimize makespan for a three-stage flow shop problem. Brah and Loo (1999) proposed a heuristic for flow shop scheduling problems with multiple processors. Oğuz et al. (2003) also proposed some heuristics to solve multiprocessor task scheduling in a two-stage flow shop scheduling problems.

Key Terms in this Chapter

NP-Hard Problems: Non – deterministic polynomial time hard problems.

Scheduling: Scheduling is defined as a process of allocating resources over time to perform a collection of tasks.

Mean Flow Time: Mean flow time is defined as the average time spent by the jobs in the production system.

Makespan: Makespan is defined as the completion time of the last job to leave the system.

Cuckoo Search Algorithm: A recently developed meta-heuristic algorithm to solve the optimization problems.

Complete Chapter List

Search this Book:
Reset