Supporting material for the article:

A Hybrid TP+PLS Algorithm for Bi-objective Flow-Shop Scheduling Problems


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

Table of Contents
  1. Abstract
  2. Instances used for experiments
  3. Instances and benchmark sets used for the final comparison
  4. Seeding of PLS
  5. PLS neighborhood operator
  6. Adaptive TPLS versus restart
  7. TPLS versus TPLS+CWstep
  8. TPLS+CWstep versus TPLS+PLS
  9. Comparison of HYBRID with benchmark sets
    1. HYBRID
    2. HYBRID (common parameters)
  10. Comparison of MOSA and MOGLS with benchmark sets
  11. Empirical Attainment Functions
    1. HYBRID versus MOSA
    2. HYBRID versus MOGLS
    3. HYBRID (common parameters) versus MOSA
    4. HYBRID (common parameters) versus MOGLS
  12. Dominance tables
    1. HYBRID versus MOSA
    2. HYBRID versus MOGLS
    3. HYBRID (common parameters) versus MOSA
    4. HYBRID (common parameters) versus MOGLS
    5. Detailed tables for the dominance percentage
  13. Parameters setting
    1. HYBRID (common parameters)
    2. HYBRID
  14. Reference sets produced by our algorithm





1. Abstract:

Jérémie Dubois-Lacoste, Manuel López-Ibáñez, and Thomas Stützle.
A Hybrid TP+PLS Algorithm for Bi-objective Flow-Shop Scheduling Problems.
Computers & Operations Research, 38(8):1219–1236, 2011.

[ Bibtex ] [ doi: 10.1016/j.cor.2010.10.008 ]

This paper presents the steps followed in the design of a new algorithm for bi-objective permutation flow shop scheduling problems. We consider five problems that arise from the pairwise combinations of the objectives (i) makespan, (ii) the sum of the completion times of the jobs, and (iii) both, the weighted and non-weighted total tardiness of all jobs. The proposed algorithm combines two search methods, two-phase local search and Pareto local search, which are representative of two different, but complementary, paradigms for multi-objective optimisation in terms of Pareto-optimality. The design of the hybrid algorithm is based on a careful experimental analysis of crucial algorithmic components of these two search methods. We compared our algorithm to the two best algorithms identified among a set of 23 candidates algorithms, in a recent review of the bi-objective permutation flow-shop scheduling problem. We have reimplemented carefully these two algorithms in order to assess the quality of the one proposed here. The experimental comparison in this paper shows that the proposed algorithm obtains non-dominated sets that often dominate the output of the two algorithms from the literature. Therefore, our analysis shows without ambiguity that the proposed algorithm is a new state-of-the-art algorithm for the five bi-objective permutation flow-shop problems studied in this paper.

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
Additional instances used for tuning Additional instances

3. Instances and benchmark sets used for the final comparison

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
benchmark sets Original archive of benchmark sets provided by Minella et al.

4. Seeding of PLS

Plots of the EAF obtained when PLS is seeded with random, heuristic or IG solutions.
pls_seeding.tar.gz

5. PLS neighborhood operator

Comparison of PLS using different neighborhood operators.
pls_seeding.tar.gz

6. Adaptive TPLS versus restart

Comparison of the Adaptive anytime strategy and a simple restart strategy.
adaptive_against_restart.tar.gz

7. TPLS versus TPLS+CWstep

Comparison of the raw solutions provided by TPLS and the output sets after appliying a CW-step.
tpls_vs_tplscwstep.tar.gz

8. TPLS+CWstep versus TPLS+PLS

Comparison of the non-dominated sets obtained from the application of a CW-step against a full PLS.
tplscwstep_tplspls.tar.gz

9. Comparison of HYBRID with benchmark sets

(i) HYBRID

Archive with all combinations of objectives hybrid_against_bench_sets.tar.gz

(ii) HYBRID (common parameter)

Archive with all combinations of objectives hybrid_cp_against_bench_sets.tar.gz

10. Comparison of MOSA and MOGLS with benchmark sets

Checking of the quality of our implementation of MOSA and MOGLS, compared to the benchmark sets of Minella et al.
Archive with all combinations of objectives mosa_and_mogls_versus_benchsets.tar.gz

11. Empirical Attainment Functions

(i) HYBRID versus MOSA

Archive with all combinations of objectives eaf_comp_hybrid_vs_mosa.tar.gz

(ii) HYBRID versus MOGLS

Archive with all combinations of objectives eaf_comp_hybrid_vs_mogls.tar.gz

(iii) HYBRID (common parameter) versus MOSA

Archive with all combinations of objectives eaf_comp_hybridcp_vs_mosa.tar.gz

(iv) HYBRID (common parameter) versus MOGLS

Archive with all combinations of objectives eaf_comp_hybridcp_vs_mogls.tar.gz

12. Dominance tables

(i) HYBRID versus MOSA

hybrid versus mosa

(ii) HYBRID versus MOGLS

hybrid versus mogls

(iii) HYBRID (common parameters) versus MOSA

hybrid constparam versus mosa

(iv) HYBRID (common parameters) versus MOGLS

hybrid constparam versus mogls

(v) Detailed tables for the dominance percentage

Archive with all tables
(HYBRID, HYBRID_CP, MOSA, MOGLS)
detailed_dominance_tables.tar.gz

13. Parameters setting

(i) HYBRID (common parameters)

Objectives of the IG d, tempParam, numScan
Sum of flowtimes 5, 0.5, 3
Total tardiness 6, 0.9, 3
Weighted tardiness 5, 1.2, 2
Makespan, Sum of flowtimes 5, 6.0, 1
Makespan, Total tardiness 4, 5.0, 1
Makespan, Weighted tardiness 4, 4.0, 1
Sum of flowtimes, Total tardiness 6, 5.0, 1
Sum of flowtimes, Weighted tardiness 6, 30, 1

(ii) HYBRID

Objectives of the IG d, tempParam, numScan
20 jobs
Sum of flowtimes 6, 0.6, 2
Total tardiness 8, 1.3, 3
Weighted tardiness 6, 1.8, 1
Makespan, Sum of flowtimes 5, 8.5, 1
Makespan, Total tardiness 4, 7.0, 1
Makespan, Weighted tardiness 4, 5.9, 1
Sum of flowtimes, Total tardiness 5, 6.0, 1
Sum of flowtimes, Weighted tardiness 5, 6.0, 1
50 jobs
Sum of flowtimes 6, 0.4, 3
Total tardiness 4, 1.8, 4
Weighted tardiness 3, 2.3, 4
Makespan, Sum of flowtimes 4, 5.0, 1
Makespan, Total tardiness 5, 3.0, 1
Makespan, Weighted tardiness 3, 2.3, 1
Sum of flowtimes, Total tardiness 6, 5.0, 1
Sum of flowtimes, Weighted tardiness 6, 3.1, 3
100 jobs
Sum of flowtimes 5, 0.4, 3
Total tardiness 4, 0.2, 3
Weighted tardiness 6, 0.3, 3
Makespan, Sum of flowtimes 5, 4.0, 1
Makespan, Total tardiness 4, 3.5, 1
Makespan, Weighted tardiness 4, 2.1, 1
Sum of flowtimes, Total tardiness 6, 5.5, 1
Sum of flowtimes, Weighted tardiness 6, 1.5, 3
200 jobs
Sum of flowtimes 5, 0.5, 3
Total tardiness 3, 0.1, 4
Weighted tardiness 4, 0.1, 3
Makespan, Sum of flowtimes 4, 3.0, 1
Makespan, Total tardiness 4, 4.0, 1
Makespan, Weighted tardiness 9, 3.0, 2
Sum of flowtimes, Total tardiness 6, 4.5, 1
Sum of flowtimes, Weighted tardiness 10, 1.3, 3


14. Reference sets produced by our algorithm

You can find on this page reference non-dominated sets produced by the hybrid algorithm using constant parameters,
to benchmark any new algorithm for any combination of objectives.





Valid HTML 4.01 Transitional Valid CSS!