Document Description

* Corresponding author. Tel./fax: +98-21-77240482.
E-mail addresses: Reza_Ramezanian@ind.iust.ac.ir (R. Ramezanian),
International Journal of Industrial Engineering Computations 1 (2010) 1–10
Contents lists available at GrowingScience
International Journal of Industrial Engineering Computations
homepage: www.GrowingScience.com/ijiec
A discrete firefly meta-heuristic with local search for makespan minimization in permutation
flow shop scheduling problems
Mo

Document Share

Document Tags

Document Transcript

* Corresponding author. Tel./fax: +98-21-77240482.E-mail addresses: Reza_Ramezanian@ind.iust.ac.ir (R. Ramezanian),
International Journal of Industrial Engineering Computations 1 (2010) 1–10
Contents lists available at GrowingScience
International Journal of Industrial Engineering Computations
homepage:www.GrowingScience.com/ijiec
A discrete firefly meta-heuristic with local search for makespan minimization in permutationflow shop scheduling problems
Mohammad Kazem Sayadi
a
, Reza Ramezanian
a*
and Nader Ghaffari-Nasab
a
a
Department of Industrial Engineering, Iran University of Science and Technology, Tehran, Iran
A R T I C L E I N F O A B S T R A C T
Article history
:Received 23 January 2010Received in revised form23 April 2010Accepted 26 April 2010Available online 26 April 2010
During the past two decades, there have been increasing interests on permutation flow shopwith different types of objective functions such as minimizing the makespan, the weightedmean flow-time etc. The permutation flow shop is formulated as a mixed integer programmingand it is classified as NP-Hard problem. Therefore, a direct solution is not available and meta-heuristic approaches need to be used to find the near-optimal solutions. In this paper, we present a new discrete firefly meta-heuristic to minimize the makespan for the permutation flowshop scheduling problem. The results of implementation of the proposed method are comparedwith other existing ant colony optimization technique. The preliminary results indicate that thenew proposed method performs better than the ant colony for some well known benchmark problems.
©
2010
Growing
Science
Ltd.
All
rights
reserved.
Keywords
:Meta-heuristicFirefly meta-heuristicAnt colonyPermutation flow shopSchedulingCombinatorial optimizationMixed integer programming
1.
Introduction
The flow shop scheduling problem (FSSP) is normally classified as a complex combinatorial optimization problem, in which there is a set of
n
jobs (
1, …, n
) to be processed in a set of
m
machines (
1, …, m
) in the sameorder. We normally look for a special sequence of processing the jobs in the machines to minimize one or more criteria such as minimization of makespan, mean flow, etc. There are different most commonly usedcriteria such as the minimization of the total completion time or makespan of the schedule (
max
C
) which issometimes referred to as maximum flow time or
max
F
. The processing times needed for the jobs on themachines are assumed to be non-negative and deterministic denoted as
ij
p
, with
i = 1 …,n
and
j = 1,…,m
.Although the optimal solution of the flow shop scheduling problem can be determined in polynomial timewhen
m=2
(Johnson, 1954), the general form of this kind of problem is known to be NP-Complete in thestrong sense when
m
≥
3 (see Garey et al., 1976) and generally
m
n
)!(
schedules need to be considered. That iswhy the problem is somewhat restricted in by not allowing job passing. In this case, “only”
n
! schedules must be considered and the problem is then known as permutation flow shop which is classified as
n/m
/
P
/
max
F
or as
F/prmu
/
max
C
(see Pinedo, 2002) and the primary focus of the work of this paper is the last type of flow shopenvironment. Johnson (1954) is believed to be the first who introduced flow shop scheduling. Since then, flowshop scheduling has become one of the most interesting topics among researchers and practitioners. There aredifferent forms of flow shop optimization such as minimization of the makespan which is one of the most popular one. The solution procedure for the flow shop problem is often either heuristic or meta-heuristics.
2
Turner and Booth (1987) compared two famous heuristics with a set of 350 random problems. Ponnambalamet al. (2001) compared five different heuristics against only 21 typical test problems. Ruiz and Maroto (2005) presented a review and comparative evaluation of heuristics and meta-heuristics for the permutation flow shop problem with the makespan criterion. They compared 25 methods, ranging from the classical Johnson’salgorithm to the most recent meta-heuristics. Lian et al. (2006) applied an efficient similar particle swarmoptimization algorithm (SPSOA) to the PFSS problem with the objective of minimizing the makespan.Tasgetiren et al. (2007) solved the permutation flow shop sequencing problem (PFSP) with a particle swarmoptimization algorithm (PSO). They considered the objectives of minimizing makespan and the total flow timeof jobs. Ruiz and Stutzle (2007) presented a new iterated greedy algorithm that applies two phases iteratively,named destruction, where some jobs are eliminated from the incumbent solution, and construction, where theeliminated jobs are reinserted into the sequence using the well known NEH construction heuristic. Naderi andRuiz (2010) studied a new generalization of the regular permutation flow shop scheduling problem (PFSP)referred to as the distributed permutation flow shop scheduling problem or DPFSP. Under this generalization,they assumed that there are a total of F identical factories or shops, each one with
m
machines disposed inseries. A set of
n
available jobs have to be distributed among the
F
factories and then a processing sequencehas to be derived for the jobs assigned to each factory. Their optimization criterion was the minimization of themaximum completion time or makespan among the factories. Dong et al. (2009) presented an integrated localsearch algorithm to solve the permutation flow shop sequencing problem with total flow time criterion. Theyshowed the effectiveness and superiority of their method over three constructive heuristics, three ant-colonyalgorithms and a particle swarm optimization algorithm. Vallada and Ruiz (2009) worked on a cooperativemeta-heuristic method for the permutation flow shop scheduling problem considering two objectivesseparately: total tardiness and makespan. They adopted the island model where each island runs an instance of the method and communications begin when the islands are reached to a certain level of evolution. FarahmandRad et al. (2009) showed five new methods that outperform the well-known NEH heuristic as supported bycareful statistical analyses using the well-known instances of Taillard. The proposed methods attempt tocounter the excessive greediness of NEH by carrying out re-insertions of already inserted jobs at some pointsin the construction of the solution. Vallada and Ruiz (2010) presented three genetic algorithms for the permutation flow shop scheduling problem with total tardiness minimization criterion. The algorithms includeadvanced techniques like path re-linking, local search and a procedure to control the diversity of the population.In this paper, we consider a permutation flow shop scheduling problem with the objective of minimizing themakespan. The method is then solved using a discrete firefly algorithm (DFA) and it is employed to solve the problem. Firefly algorithm, developed by Xin-She Yang (2008), is a novel population based technique for solving continues optimization problem, especially for continues NP-hard problems and has been motivated bythe simulation of the social behavior of fireflies. The flashing light of fireflies is a fantastic sight in the sky andfireflies normally attract mating partners and potential prey by using such flashes. Both genders join together by the rhythmic flash, the rate of flashing and the amount of time of flashing. Females respond to a male’sunique and peerless pattern of flashing. It is possible to formulate optimization algorithms because the flashinglight can be formulated in such a way that it is associated with the objective function to be optimized. Basedon the Xin-She Yang’s paper, firefly algorithm is very efficient in finding the global optima with high successrates. Xin-She Yang’s simulation results for finding the global optima of various test functions suggest that particle swarm optimization often outperforms customary algorithms such as genetic algorithms, while thefirefly algorithm is superior to both PSO and GA in terms of both efficiency and success rate (2009). In 2009,Lukasik and Zak (2009) deliberate the firefly algorithm for continuous constrained optimization task. Their experimental evaluation demonstrates efficiency of the firefly algorithm.The remainder of the paper is organized as follows: In section 2
,
a mathematical model for permutation flowshop scheduling problems is presented. Section 3 describes our proposed discrete firefly algorithm for solving
R. Ramezanian et al./ International Journal of Industrial Engineering Computations 1 (2010)
3
the model. Section 4 presents the computational results acquired and, finally, section 5 provides conclusionsand suggestions for further research.
2.
Mathematical formulation
In this section, a mathematical model for permutation flow shop scheduling problem is presented. Theassumptions of the model are as follows:
ã
All
n
jobs to schedule are independent and available for processing at time zero.
ã
Machine cannot process two jobs at the same time.
ã
Each job is processed on at most one machine at a time.
ã
Setup times for the operations are sequence-independent and are included in processing times.
ã
There is only one of each type of machine.
ã
No more than one operation of the same job can be executed at a time.Parameters:
n
: Number of jobs
m
: Number of machines
i
: Machine index, (
i=
1
,..,m
)
j
: Job index, (
j
=1,…,
n
)
k
: Order index, (
k
=1,…,
n
)
ij
t
: Processing time of job
j
on machine
i
Decision variables:
ijk
q
: Completion time of job
j
on machine
i
in
k
th order
jk
x
: Binary variable taking value 1 if job
j
is processed in
k
th order and 0, otherwise.The mathematical model for minimizing the makespan is as follow:(1)
∑
=
n j jnmjn
xq
1
.min
subject to(2)
n jmi xq xt q
nk jk ijk jk ji
nk jk i
,..,1;1,...,1)(
1)1(1)1(
=−=≥−
∑∑
=+=+
(3)
)1(,..,1;,...,1,0)(
11)1()1(
−==≥−−
∑∑
==++
nk mi xq xt q
n j jk ijk n jk jijk ij
(4)
k i x
n j jk
,,1
1
∀=
∑
=
(5)
ji x
nk jk
,,1
1
∀=
∑
=
(6)
k ji Mxq
jk ijk
,,,
∀≤
4
(7)
k , j ,i ,0q
ijk
∀≥
(8)
k , j ,i },1 ,0{ x
ijk
∀=
The objective function (1) represents the minimization of the makespan. Constraints (2) and (3) certify that a job does not start on a machine until it finishes processing on the previous machine and its predecessor hascompleted processing on that machine. Constraint (4) insures that each sequence position is filled with onlyone job and constraint (5) insures that each job is assigned to only one position in the job sequence. Theconstraint set (6) is a relationship between the binary variables and the completion time variables. Note thatwhen each binary variable becomes zero, then its completion time variable will be also equal to zero. Finally,(7) and (8) are logical constraints.
3.
Discrete firefly algorithm
3.1.
Methodology
Nature-inspired methodologies are among the most powerful algorithms for optimization problems. Fireflyalgorithm is a novel nature-inspired algorithm inspired by social behavior of fireflies. Fireflies are one of themost special, captivating and fascinating creature in the nature. There are about two thousand firefly species,and most fireflies produce short and rhythmic flashes. The rate and the rhythmic flash, and the amount of timeform part of the signal system which brings both sexes together. Therefore, the main part of a firefly's flash isto act as a signal system to attract other fireflies. By idealizing some of the flashing characteristics of fireflies,firefly-inspired algorithm was presented by Xin-She Yang (2008). Firefly-inspired algorithms use thefollowing three idealized rules: 1) All fireflies are unisex which means that they are attracted to other firefliesregardless of their sex; 2) The degree of the attractiveness of a firefly is proportion to its brightness, thus for any two flashing fireflies, the less brighter one will move towards the brighter one and the more brightnessmeans the less distance between two fireflies. If there is no brighter one than a particular firefly, it will moverandomly; 3) The brightness of a firefly is determined by the value of the objective function. For amaximization problem, the brightness can be proportional to the value of the objective function. Other formsof brightness can be defined in a similar way to the fitness function in genetic algorithms (2009). Based on theeffectiveness of the firefly algorithm in optimizing continues problems, it is predictable that this algorithmwould be impressive to solve discrete optimization problems which creates the motivation for proposing adiscrete firefly algorithm. In the discrete firefly algorithm, there are four important issues:
Attractiveness
: In the firefly algorithm, the main form of attractiveness function
β
(r) can be anymonotonically decreasing functions such as the following generalized form:(9)
βrβ
e
, m1
where
r
is the distance between two fireflies,
β
is the attractiveness at
r
= 0 and
γ
is a fixed light absorptioncoefficient.
Distance
: The distance between any two fireflies
i
and
j
at
X
and
X
is the Cartesian distance as follows,(10)
r
x
x
∑x
,
x
,
,where
x
,
is the k-th component of the i-th firefly(
X
).
Movement
: The movement of a firefly,
i
is attracted to another more attractive (brighter) firefly
j
, isdetermined by

We Need Your Support

Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks

SAVE OUR EARTH

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...Sign Now!

We are very appreciated for your Prompt Action!

x