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)

Table of Contents
  1. Abstract
  2. Instances used for experiments
  3. Instances and Reference sets used for the final comparison
  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

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 ]

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

These instances have been generated using the same procedure described in the paper below.
Instances used for experiments experiments_instances.tar.gz

3. Benchmark instances and Reference sets

This material we used for the final comparison has been provided together with the paper:

G. Minella, R. Ruiz and M. Ciavotta. A review and evaluation of multi-objective algorithms for the flowshop scheduling problem,
INFORMS Journal on Computing 20(3), 451-471, 2008.
Benchmark set of instances Original archive of instances
Reference sets Original archive of reference sets

4. Seeding of PLS

Plots of the EAF obtained when PLS is seeded with random, heuristic or IG solutions.
Given the number of plots, they are available as a whole archive (2.5 Mb).

5. PLS neighborhood operator

Comparison of PLS using different neighborhood operators.
Eps plots (1.3 Mb).

6. TPLS versus TPLS+CWstep

Comparison of the raw solutions provided by TPLS and the output sets after appliying a CW-step.
Eps plots (88 Kb).

7. TPLS+CWstep versus TPLS+PLS

Comparison of the non-dominated sets obtained from the application of a CW-step against a full PLS.
Eps plots (288 Kb).

8. Final comparison with reference sets

All these plots can be downloaded in eps format. You may prefer png format.
Makespan and Sum of flowtimes
DD_Ta081_MSFT.png
DD_Ta081
DD_Ta082_MSFT.png
DD_Ta082
DD_Ta083_MSFT.png
DD_Ta083
DD_Ta084_MSFT.png
DD_Ta084
DD_Ta085_MSFT.png
DD_Ta085
DD_Ta086_MSFT.png
DD_Ta086
DD_Ta087_MSFT.png
DD_Ta087
DD_Ta088_MSFT.png
DD_Ta088
DD_Ta089_MSFT.png
DD_Ta089
DD_Ta090_MSFT.png
DD_Ta090
Makespan and Total Tardiness
DD_Ta081_MTT.png
DD_Ta081
DD_Ta082_MTT.png
DD_Ta082
DD_Ta083_MTT.png
DD_Ta083
DD_Ta084_MTT.png
DD_Ta084
DD_Ta085_MTT.png
DD_Ta085
DD_Ta086_MTT.png
DD_Ta086
DD_Ta087_MTT.png
DD_Ta087
DD_Ta088_MTT.png
DD_Ta088
DD_Ta089_MTT.png
DD_Ta089
DD_Ta090_MTT.png
DD_Ta090
Total Tardiness and Sum of Flowtimes
DD_Ta081_SFTTT.png
DD_Ta081
DD_Ta082_SFTTT.png
DD_Ta082
DD_Ta083_SFTTT.png
DD_Ta083
DD_Ta084_SFTTT.png
DD_Ta084
DD_Ta085_SFTTT.png
DD_Ta085
DD_Ta086_SFTTT.png
DD_Ta086
DD_Ta087_SFTTT.png
DD_Ta087
DD_Ta088_SFTTT.png
DD_Ta088
DD_Ta089_SFTTT.png
DD_Ta089
DD_Ta090_SFTTT.png
DD_Ta090

Valid HTML 4.01 Transitional Valid CSS!