Supporting material for the article:

Effective Hybrid Stochastic Local Search Algorithms
for Biobjective Permutation Flowshop Scheduling

By Jérémie Dubois-Lacoste, Manuel López-Ibáñez and Thomas Stützle
November 2009 (last update: January 2010)

1. Abstract:

Jérémie Dubois-Lacoste, Manuel López-Ibáñez, and Thomas Stützle. Effective hybrid stochastic local search algorithms for biobjective permutation flowshop scheduling. In Hybrid Metaheuristics - 6th International Workshop, HM 2009, volume 5818 of Lecture Notes in Computer Science, pages 100-114. Springer, Heidelberg, 2009.
[ Bibtex ] [ doi: 10.1007/978-3-642-04918-7_8 ]

@INPROCEEDINGS{DubLopStu09:hm-bfsp,
        author = { J{\'e}r{\'e}mie Dubois-Lacoste  and  Manuel L{\'o}pez-Ib{\'a}{\~n}ez  and  Thomas St{\"u}tzle },
        title = {Effective Hybrid Stochastic Local Search Algorithms
               for Biobjective Permutation Flowshop Scheduling},
        pages = {100--114},
        crossref = {HM2009}
}

@PROCEEDINGS{HM2009,
        title = {Hybrid Metaheuristics -- 6th International Workshop, HM 2009},
        booktitle = {Hybrid Metaheuristics -- 6th International Workshop, HM 2009},
        year = 2009,
        series = {Lecture Notes in Computer Science},
        volume = 5818,
        publisher = {Springer, Heidelberg}
}

This paper presents the steps followed in the design of hybrid stochastic local search algorithms for biobjective permutation flow shop scheduling problems. In particular, this paper tackles the three pairwise combinations of the objectives (i) makespan, (ii) the sum of the completion times of the jobs, and (iii) the weighted total tardiness of all jobs. The proposed algorithms are combinations of two local search methods: two-phase local search and Pareto local search. The design of the algorithms is based on a careful experimental analysis of crucial algorithmic components of the two search methods. The final results show that the newly developed algorithms reach very high performance: The solutions obtained frequently improve upon the best nondominated solutions previously known, while requiring much shorter computation times. The Probabilistic Traveling Salesman Problem (PTSP) that we tackle in this paper is a central problem in stochastic vehicle routing. Recently, it has been shown that empirical estimation is a promising approach to tackle the PTSP. Based on this approach, a high performing local search algorithm has been developed. In this paper, we customize several metaheuristics to solve the PTSP. This customization consists in using the estimation approach to evaluate the solutions and the recently developed estimation-based local search to improve them. We experimentally evaluate the performances of the customized estimation-based metaheuristics. The experimental results show that a customized memetic algorithm is highly effective and it outperforms the current state-of-the-art algorithms on a number of instances.

Keywords: Metaheuristics, Two-Phase Local Search, Pareto Local Search, Scheduling, Flow-shop

2. Instances used for experiments

3. Benchmark instances and Reference sets

4. Seeding of PLS

5. PLS neighborhood operator

6. TPLS versus TPLS+CWstep

7. TPLS+CWstep versus TPLS+PLS

8. Final comparison with reference sets

Makespan and Sum of flowtimes
DD_Ta081	DD_Ta082
DD_Ta083	DD_Ta084
DD_Ta085	DD_Ta086
DD_Ta087	DD_Ta088
DD_Ta089	DD_Ta090
Makespan and Total Tardiness
DD_Ta081	DD_Ta082
DD_Ta083	DD_Ta084
DD_Ta085	DD_Ta086
DD_Ta087	DD_Ta088
DD_Ta089	DD_Ta090
Total Tardiness and Sum of Flowtimes
DD_Ta081	DD_Ta082
DD_Ta083	DD_Ta084
DD_Ta085	DD_Ta086
DD_Ta087	DD_Ta088
DD_Ta089	DD_Ta090