Supporting material for the article:
A Hybrid TP+PLS Algorithm for Biobjective FlowShop Scheduling Problems
By Jérémie DuboisLacoste, Manuel
LópezIbáñez and Thomas
Stützle
July 2010 (last update: July 2010)
1. Abstract:
Jérémie DuboisLacoste,
Manuel LópezIbáñez, and Thomas Stützle.
A Hybrid TP+PLS Algorithm
for Biobjective FlowShop 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 DuboisLacoste and Manuel L{\'o}pezIb{\'a}{\~n}ez and Thomas St{\"u}tzle },
title = "A Hybrid {TP+PLS} Algorithm for Biobjective
FlowShop Scheduling Problems",
journal = "Computers & Operations Research,
year = 2011,
volume = 38,
number = 8,
pages = {12191236},
doi = {10.1016/j.cor.2010.10.008},
}
This paper presents the steps followed in the design of a new
algorithm for biobjective 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 nonweighted total
tardiness of all jobs. The proposed algorithm combines
two search methods, twophase local search and Pareto local
search, which are representative of two different, but complementary,
paradigms for multiobjective optimisation in terms of Paretooptimality.
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
biobjective permutation flowshop 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 nondominated 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
stateoftheart algorithm for the five biobjective permutation
flowshop problems studied in this paper.
Keywords: Metaheuristics, TwoPhase Local Search,
Pareto Local Search, Scheduling, Flowshop
2. Instances used for experiments
These instances have been generated using the same procedure described in the
paper below.
3. Instances and benchmark sets used for the final comparison
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
6. Adaptive TPLS versus restart
7. TPLS versus TPLS+CWstep
8. TPLS+CWstep versus TPLS+PLS
Comparison of the nondominated sets obtained from the application of a
CWstep against a full PLS.
tplscwstep_tplspls.tar.gz
9. Comparison of HYBRID with benchmark sets
(i) HYBRID
(ii) HYBRID (common parameter)
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.
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)
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
nondominated sets produced by the hybrid algorithm using constant parameters,
to benchmark any new
algorithm for any combination of objectives.