Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(9)
Branch and Bound Algorithm
Computational Complexity
Computer Experiment
Constraint Programming
Flow Shop Scheduling
Genetic Algorithm
memetic algorithm
Task Scheduling
Local Search
Subscribe
Academic
Publications
Hybrid FlowShop: a Memetic Algorithm Using ConstraintBased Scheduling for Efficient Search
Hybrid FlowShop: a Memetic Algorithm Using ConstraintBased Scheduling for Efficient Search,10.1007/s1085200891011,Journal of Mathematical Modelli
Edit
Hybrid FlowShop: a Memetic Algorithm Using ConstraintBased Scheduling for Efficient Search
(
Citations: 2
)
BibTex

RIS

RefWorks
Download
Antoine Jouglet
,
Ceyda Oguz
,
Marc Sevaux
The paper considers the hybrid flowshop
scheduling problem
with multiprocessor tasks. Motivated by the
computational complexity
of the problem, we propose a
memetic algorithm
for this problem in the paper. We first describe the implementation details of a genetic algorithm, which is used in the memetic algorithm. We then propose a
constraint programming
based branchandbound algorithm to be employed as the
local search
engine of the memetic algorithm. Next, we present the new memetic algorithm. We lastly explain the computational experiments carried out to evaluate the performance of three algorithms (genetic algorithm,
constraint programming
based branchandbound algorithm, and memetic algorithm) in terms of both the quality of the solutions produced and the efficiency. These results demonstrate that the
memetic algorithm
produces better quality solutions and that it is very efficient.
Journal:
Journal of Mathematical Modelling and Algorithms  JMMA
, vol. 8, no. 3, pp. 271292, 2009
DOI:
10.1007/s1085200891011
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
www.springerlink.com
)
(
www.springerlink.com
)
(
dx.doi.org
)
(
www.informatik.unitrier.de
)
(
www.springerlink.com
)
(
www.springerlink.com
)
More »
Citation Context
(2)
...Jouglet et al. [
21
] proposed a memetic algorithm (MA), in which a constraint programmingbased branchandbound algorithm is used as the local search engine to solve the FkðPm1;...;PmkÞjsizeijjCmax problem...
...On the other hand, a good initial solution will also influence the search efficiency of the SA as recognized by many researchers; therefore, we generated 20×n job sequences, which include the four obtained by the bestperforming priority rules, as suggested by Jouglet et al. [
21
], whereas, the rest of the job sequences were generated randomly...
...There are five algorithms compared, including GAOE [15], GA [
21
], MA [21], and SAs (SA2 with and SA1 without the deduced predecessor–successor relationship of jobs) in this experiment...
...There are five algorithms compared, including GAOE [15], GA [21], MA [
21
], and SAs (SA2 with and SA1 without the deduced predecessor–successor relationship of jobs) in this experiment...
...The average makespan and the average computation time of GAOE, GA, and MA are taken directly from the study of Jouglet et al. [
21
] and the stopping conditions...
...ed on a PC Pentium 4, 1.8GHz processor with 512 MB memory, and the experimental results are presented by Jouglet et al. [
21
]...
...for GAOE, GA algorithms, and MA in the study of Jouglet et al. [
21
] were 1,800 and 900 s of the CPU time, respectively...
...3. PSO: A particle swarm optimization algorithm proposed by Tseng and Liao [19], and 4. MA: A memetic algorithm proposed by Jouglet, Oğuz, and Sevaux [
21
] Inthefirst three algorithms [16, 17, 19], the authors applied the percentage deviation of the makespan values from lower bound values to measure the performance of the algorithms, that is, ðPD¼ðCmax� LBÞ LB� 100%Þ , where LB is a lower bound value and is ...
...In the study of Jouglet et al. [
21
], GASU and MA were measured using the average makespan...
...GASU and MA are compared with the proposed SAs, and the results of these (GASU and MA) are taken directly from the paper [
21
]...
HuiMei Wang
,
et al.
A simulated annealing for hybrid flow shop scheduling with multiproces...
...This benchmark is widely used in the literature [20], [
11
], [18]...
...Furthermore, it shows the results obtained by Jouglet et al. in [
11
]...
...We contrast our results only versus those presented in [
11
]...
...Hence, we recalculated the average percentage deviation for all methods given in [
11
]...
...Indeed, CDADS takes between less than 0.1 seconds (for small problems) and 47.3 seconds (for large problems) to find their solutions, while methods proposed in [
11
] converge much more slower [0.7 sec, 900 sec]...
Asma Lahimer
,
et al.
Climbing DepthBounded Adjacent Discrepancy Search for Solving Hybrid ...
References
(26)
Satisfiability Tests and TimeBound Adjustments for Cumulative Scheduling Problems
(
Citations: 40
)
PHILIPPE BAPTISTE
,
WIM NUIJTEN
Journal:
Annals of Operations Research  Annals OR
, 1997
A practical use of Jackson''s preemptive schedule for solving the JobShop problem
(
Citations: 113
)
J. Carlier
,
E. Pinson
Published in 1990.
AN EXACT METHOD FOR SOLVING THE MULTIPROCESSOR FLOWSHOP
(
Citations: 21
)
Jacques CARLIER
,
Emmanuel NERON
Journal:
Rairooperations Research
, vol. 34, no. 1, pp. 125, 2000
General multiprocessor task scheduling
(
Citations: 35
)
Jianer Chen
Journal:
Naval Research Logistics  NAV RES LOG
, vol. 46, no. 1, pp. 5774, 1999
Genetic Algorithms in Search Optimization and Machine Learning
(
Citations: 17426
)
David E. Goldberg
Published in 1989.
Sort by:
Citations
(2)
A simulated annealing for hybrid flow shop scheduling with multiprocessor tasks to minimize makespan
(
Citations: 2
)
HuiMei Wang
,
FuhDer Chou
,
FulChiang Wu
Journal:
International Journal of Advanced Manufacturing Technology  INT J ADV MANUF TECHNOL
, vol. 53, no. 5, pp. 761776, 2011
Climbing DepthBounded Adjacent Discrepancy Search for Solving Hybrid Flow Shop Scheduling Problems with Multiprocessor Tasks
Asma Lahimer
,
Pierre Lopez
,
Mohamed Haouari
Conference:
International Conference on Integration of AI and OR Techniques in Constraint Programming  CPAIOR
, pp. 117130, 2011