Academic
Publications
Hybrid Flow-Shop: a Memetic Algorithm Using Constraint-Based Scheduling for Efficient Search

Hybrid Flow-Shop: a Memetic Algorithm Using Constraint-Based Scheduling for Efficient Search,10.1007/s10852-008-9101-1,Journal of Mathematical Modelli

Hybrid Flow-Shop: a Memetic Algorithm Using Constraint-Based Scheduling for Efficient Search   (Citations: 2)
BibTex | RIS | RefWorks Download
The paper considers the hybrid flow-shop 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 branch-and-bound 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 branch-and-bound 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. 271-292, 2009
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.
    • ...Jouglet et al. [21] proposed a memetic algorithm (MA), in which a constraint programming-based branch-andbound 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.8-GHz 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]...

    Hui-Mei Wanget 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 Lahimeret al. Climbing Depth-Bounded Adjacent Discrepancy Search for Solving Hybrid ...

Sort by: