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)

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 ]

@Article{DubLopStu2011cor,
  author =       { J{\'e}r{\'e}mie Dubois-Lacoste  and  Manuel L{\'o}pez-Ib{\'a}{\~n}ez  and  Thomas St{\"u}tzle },
  title =        "A Hybrid {TP+PLS} Algorithm for Bi-objective
                  Flow-Shop Scheduling Problems",
  journal =      "Computers & Operations Research,
  year =         2011,
  volume =       38,
  number =       8,
  pages =        {1219--1236},
  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

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

(i) HYBRID

(ii) HYBRID (common parameter)

10. Comparison of MOSA and MOGLS with benchmark sets

11. Empirical Attainment Functions

(i) HYBRID versus MOSA

(ii) HYBRID versus MOGLS

(iii) HYBRID (common parameter) versus MOSA

(iv) HYBRID (common parameter) versus MOGLS

12. Dominance tables

(i) HYBRID versus MOSA

(ii) HYBRID versus MOGLS

(iii) HYBRID (common parameters) versus MOSA

(iv) HYBRID (common parameters) versus MOGLS

(v) Detailed tables for the dominance percentage

13. Parameters setting

(i) HYBRID (common parameters)

(ii) HYBRID

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.