An Improved Discrete Artificial Bee Colony Algorithm for Hybrid Flow Shop Problems - Intelligent Computing for Sustainable Energy and Environment - page 295

Compared with a large number of literatures on the classic flow shop schedul-
ing problem, the HFS problem has not been well studied. Santos et al. [3] pre-
sented a global lower bound for makespan minimization that has been used to
analyze the performance of other algorithms. Neron et al. [4] used the satisfia-
bility tests and time-bound adjustments based on the energetic reasoning and
global operations to enhance the eciency of another kind of B&B method pro-
posed in Carlier and Neron [5]. With advanced statistical tools, Ruiz et al. [6]
tested several heuristics in the realistic HFS problem and suggested that the
modified NEH heuristic [7] outperformed the other dispatching rules. The ge-
netic algorithm (GA) was applied by researchers to solve the HFS problem under
the criterion of makespan minimization [8]. On the basis of vertebrate immune
system, Engin and Doyen [9] proposed the artificial immune system (AIS) tech-
nique that incorporated the clonal selection principle and anity maturation
mechanism. Inspired by the natural mechanism of the ant colony, Alaykyran et
al. [10] introduced an improved ant colony optimization (ACO) algorithm. Niu
et al. [11] presented a quantum-inspired immune algorithm (QIA) for the HFS
problem to minimize makespan. Liao et al. [12] developed a particle swarm op-
timization (PSO) algorithm. This algorithm hybridized the PSO and bottleneck
heuristic to fully exploit the bottleneck stage, and further introduced simulated
annealing to help escape from local optima. In addition, a local search is embed-
ded to further improve its performance.
The artificial bee colony (ABC) algorithm, simulating the intelligent foraging
behaviors of honey bee colonies, is one of the latest population-based evolu-
tionary meta-heuristics [13]. Basturk and Karaboga suggested that the ABC
algorithm has a better performance than the other population-based algorithms
for solving continuous problems [14], [15]. Nevertheless, on account of its contin-
uous nature, the studies on the ABC algorithm for combinatorial optimization
problems is very limited.
As we know, there is no published work using the ABC-based algorithm for the
HFS problem. In this paper, we firstly establish the model of the HFS problem
by employing the vector representation, and then an improved discrete artificial
bee colony (IDABC) algorithm is proposed for the problem to minimize the
makespan. The rest of the paper is organized as follows. In Section 2, the model
of the HFS problem is formulated. Section 3 presents the details of the proposed
IDABC algorithm. The simulation results are provided in Section 4. Finally,
conclusions are drawn in Section 5.

2 Problem Statement

2.1 Description of the Problem

The HFS problem can be described as follows. There are n jobs J= { 1,2,..., i ,..., n -

1, n , and each stage

s has m s identical machines. These identical machines are continuously available
from time zero and have the same effect. At least one stage j must has more
than one machine. Every job has to visit all of the stages in the same order

} that have to be performed on s stages S= { 1,2,..., j ,..., s -1, s }