A Bat Algorithm with Generalized Walk for the Two-Stage Hybrid Flow Shop Problem

A Bat Algorithm with Generalized Walk for the Two-Stage Hybrid Flow Shop Problem

Latifa Dekhici (Mathematics and Computer Sciences Faculty, University of Sciences and the Technology of Oran, Oran, Algeria) and Khaled Belkadi (Mathematics and Computer Sciences Faculty, University of Sciences and the Technology of Oran, Oran, Algeria)
Copyright: © 2015 |Pages: 16
DOI: 10.4018/IJDSST.2015070101
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

In the last years, a set of bio-inspired metaheuristics has proved their efficiencies in combinational and continues optimization areas. This paper intends to hybrid a discrete version of Bat Algorithm (BA) with Generalized Evolutionary Walk Algorithm (GEWA) to solve the mono-processors two stages Hybrid Flow Shop scheduling. The authors compare the modified bat algorithm with the original one, with Particle Swarm Optimization (PSO) and with others results taken from literature. Computational results on a standard two-stage hybrid flow shop benchmark of 70 cases, and about 1700 instances, indicate that the proposed algorithm finds the best makespan (Cmax) in a good processing time comparing to the original bat algorithm and other algorithms.
Article Preview

2. Hybrid Flow Shop Problem

2.1. Presentation

A Hybrid Flow Shop (HFS) also called flexible flow shop is a system composed of a set of stages, where each stage is composed of one or more parallel machines (see Figure 1). The different jobs visit the stages in the same order. On each stage, a job is treated by one machine only. Between each stage, the jobs can wait or not in limited or unlimited buffers (Vignier et al., 1999, Billaut et al., 2000). Moreover, all jobs are assumed to be available at the system entrance with release date with value 0.

Scheduling in the HFS consists to find an adequate sequence of the jobs in entrance and an assignment of the jobs on the various machines at the various stages. The objective is optimization of a criterion of performance among the criteria. One can quote the makespan or Cmax (the completion time of the last job on the last stage), max flow time (Fmax), (Srivastava 1998, Dessouky et al., 1998, Portman et al.1998, Lamica 2000, Kyparisis and Koulamas, 2006, Jin et al., 2006, Tang et al., 2006) and due date related objective (Bank et al.,2001, Kim et al., 2002, 2003, Tang et al.2002). This problem can have many constraints (Dekhici and Belkadi, 2010).

2.2. Notation

  • M: Number of stages scheduled is M;

  • N: Number of tasks scheduled is N;

  • lk: The number of machines in stage k is lk.

The processing time of job I in stage j if machines are identical is noted tij.

Figure 1.

Schema of two stages HFS (l1=3, l2=2) Cmax

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 10: 4 Issues (2018): 1 Released, 3 Forthcoming
Volume 9: 4 Issues (2017)
Volume 8: 4 Issues (2016)
Volume 7: 4 Issues (2015)
Volume 6: 4 Issues (2014)
Volume 5: 4 Issues (2013)
Volume 4: 4 Issues (2012)
Volume 3: 4 Issues (2011)
Volume 2: 4 Issues (2010)
Volume 1: 4 Issues (2009)
View Complete Journal Contents Listing