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

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 dispatching 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.

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.