Real-world versions of the permutation flowshop scheduling problem (PFSP) have a variety of objective criteria to be optimized simultaneously. Multi-objective PFSP is also a relevant combinatorial multi-objective optimization problem. In this paper we propose a multiobjective evolutionary algorithm for PFSPs by extending the previously proposed discrete differential evolution scheme for single-objective PFSPs. The novelties of this proposal reside on the management of the evolved Pareto front and on the selection operator. A preliminary experimental evaluation has been conducted on three bi-objective PFSPs resulting from all the possible bi-objective combinations of the criteria makespan, total flowtime and total tardiness.
The Permutation Flowshop Scheduling Problem (PFSP) is an important type of
scheduling problem which has many applications in manufacturing and large scale product
fabrication. In this problem there are n jobs J1; : : : ; Jn and m machines M1; : : : ; Mm.
Each job Ji is composed by m operations Oi1; : : : ; Oim. The generic operation Oij can
be executed only by the machine Mj and its given processing time is pij . Moreover,
the execution of any operation cannot be interrupted (no pre-emption) and job passing
is not allowed, i.e., the jobs must be executed using the same order in every machine.
The goal of PFSP is to find the optimal job permutation = h (
i=1 M S( ) =
max i=1;:::;n
C( (i); m) = C( (n); m)
(
C( (i); j) = p (i);j + maxfC( (i
1); j); C( (i); j
1)g
for i; j 1, while the terminal cases are C( (0); j) = C(i; 0) = 0. In equation (
The minimization of each one of these criteria is computationally hard. Indeed, both the TFT and TT problems are NP-hard for m 2, while the MS minimization becomes NP-hard when m > 2.
Many single-optimization algorithms exists, either exact or approximate, for instance: heuristic techniques, local searches or evolutionary algorithms [2]. Anyway, in this paper we investigate the PFSP problem as a multi-objective optimization problem, in which the goal is to find a set of job permutations which are good enough with respect to two or more contrasting criteria, i.e. a set of Pareto optimal solutions.
Given k objective functions f1; : : : ; fk, a solution x dominates a solution x0 (denoted by x x0) if fi(x) fi(x0) for i = 1; : : : ; k, and there exists at least an index j 2 f1; : : : ; kg such that fj (x) < fj (x0). A solution x is Pareto optimal if there exist no other solution x0 such that x0 x. The Pareto optimal set is the set of all the Pareto optimal solution. If two solutions x and x0 are such that neither x x0 nor x0 x, then x and x0 are incomparable.
Since the Pareto set is in general very large, the goal is to find an approximation of this set, i.e., a set composed by incomparable solutions which is as close as possible to the Pareto optimal set. One of the most promising approaches to solve multi-objective optimization problems is to use evolutionary algorithms [1].
In the context of multi-objective PFSP, many approaches have been proposed. The surveys [3, 7] describe and compare many algorithms for PFSP with all the three possible combinations of two objectives among TFT, MS and TT.
In this paper we describe an algorithm for multi-objective optimization which is based on Differential Evolution for Permutation (DEP) [6]. DEP is a discrete differential evolution algorithm which directly operates on the permutations space and hence is well suited for permutation optimization problems like PFSP. Indeed, in [6] and in [5], it was shown that DEP reaches state-of-the-art results with respect to total flowtime and makespan single objective optimization. Here, DEP has been extended in order to handle multi-objective problems. The preliminary experimental results show that its performances are comparable with state-of-the-art algorithms.
The rest of the paper is organized as follows. The second section describes the classical Differential Evolution algorithm. Its extension to the permutations space and multi-objective PFSP is introduced in the third section. An experimental investigation of the proposed approach is provided in the fourth section, while conclusions are drawn at the end of the paper.
In this section we provide a short introduction to Differential Evolution (DE) algorithm. For more detail see [4]. Differential Evolution (DE) is a powerful population-based evolutionary algorithm for optimizing non-linear and even non-differentiable real functions in Rn. The main peculiarity of DE is to exploit the distribution of the solutions’ differences in order to probe the search space.
DE initially generates a random population of N P candidate solutions x1; : : : ; xNP uniformly distributed in the solutions space. At each generation, DE performs mutation and crossover in order to produce a trial vector ui for each individual xi, called target vector, in the current population. Each target vector is then replaced in the next generation by the associated trial vector if and only if the produced trial is fitter than the target. This process is iteratively repeated until a stop criterion is met (e.g., a given amount of fitness evaluations has been performed).
The differential mutation is the core operator of DE and generates a mutant vector
vi for each target individual xi. The most used mutation scheme is “rand/1” and it is
defined as follows:
vi = xr0 + F (xr1
xr2 )
(
After the mutation, a crossover operator generates a population of N P trial vectors, i.e. ui, by recombining each pair composed by the generated mutant vi and its corresponding target xi. The most used crossover operator is the binomial one that builds the trial vector ui taking some components from xi and some other ones from vi according to the crossover probability CR 2 [0; 1].
Finally, in the selection phase, the next generation population is selected by a oneto-one tournament among xi and ui for 1 i N P .
In this section we describe the proposed Multi-Objective Differential Evolution for Permutation (MODEP) which directly evolves a population of N P permutations 1; : : : ; NP . With respect to the classical DE, important variations have been made to the genetic operators of mutation, crossover and selection. Moreover, an additional archive of solutions is introduced to maintain the evolved Pareto front.
To simplify our description, let us restrict to the case of two objective functions f1 and f2. A population of N P permutations 1; : : : ; NP is randomly generated at the beginning. At each iteration, a secondary population of trial elements 1; : : : ; NP is generated by means of the mutation and crossover operators. Then, a selection operator selects, for i = 1; : : : ; N P , which element among i and i should be part of the population for the next iteration.
The pseudo-code of MODEP is depicted in Alg. 1.
The mutation operator used is the same of DEP [6]. It produces a mutant i for each
population element i using some algebraic concepts related to the symmetric group of
permutations. Here we briefly recall its structure:
Algorithm 1 MODEP
1: Initialize Population
2: Update N D
3: while num fit eval max fit eval do
4: for i 1 to N P do
5: i DifferentialMutation(i)
6: i(
It is worth to notice that this operator works directly with permutations, simulating
from an algebraic point of view, the expression of equation (
The crossover operator for permutation representations is the same of DEP and
produces two children i(
The two permutations i(
The selection operator chooses the new population element i0 between the old element i and the trial i. If i i, then i0 becomes i, i.e., i remains in the population. Otherwise, if i i or it is equal to i, then i0 becomes i, that is i replaces i in the next generation population. However, if i and i are incomparable, then we use a probabilistic method somehow similar to the -selection described in [6].
Suppose first that f1( i) < f1( i) but f2( i) f2( i). Then, i0 becomes i with
probability maxf0; 2 i(
i(
Analogously, if f1( i) f1( i) and f2( i) < f2( i). Then, i0 becomes i with
(
f2( i)
f2( i)
(
f1( i) : f1( i)
The rationale behind this selection operator is that i enters the population if it dominates or is equal to i or, with a small probability, if it is not too worse than i in one of the objective functions, while it is better than i in the other objective function. Moreover, note that the probability of accepting a slightly worsening population element linearly shades from h, when i(h) = 0, to 0, when i(h) = h, for h = 1; 2.
Therefore, the parameters h regulates how worse i can be in order to be accepted in the new population: if 1 = 2 = 0 only better elements (in the Pareto sense) can replace old elements in the population.
The algorithm keeps updated the approximated Pareto front N D, which contains all
the non-dominated elements ever generated and evaluated. Initially N D contains all
the non-dominated population elements created during the random initialization. Then,
at each generation, all the couples of children i(
In this section we report some preliminary experimental results obtained with an implementation of MODEP.
The experiments have been performed by solving the well known Taillard’s instances with the additional due times given in [3]. These instances are divided in 11 groups of 10 instances with the same values of n and m. The values of n are in the set f20; 50; 100; 200g, while m lies in f5; 10; 20g. The combination (n = 200; m = 5) is not considered. The processing time pij of each instance are randomly generated in fP1;m: : : ; 99g, while the due date of each job Ji are generated by multiplying the value j=1 pij for a random factor in [1; 4]. MODEP has been run 10 times for each instance and the adopted stopping criterion is the maximum number of evaluations, which has been set to 2000 n m. Three combinations of objectives have been considered: (M S; T F T ), (M S; T T ), and (T F T; T T ). For each execution the obtained Pareto front (corresponding to N D) has been analyzed by computing two performance indices: the hypervolume IH and the unary multiplicative epsilon I1. IH is computed as the area delimited by the solutions of N D and a reference point. I1 compares N D with the best known Pareto front B and is computed as
I1 = max min max x2B y2ND j=1;2 fj (x) fj (y) :
The indices have been computed by averaging over the multiple executions and instances for every combination of n m.
The value for the parameter N P has been set to 100 after some preliminary experiments. The parameter F used in the mutation operator is, as in [6], self-adapted during the evolution. Instead, the values for the selection parameters 1 and 2 have been set after a calibration phase according to Table 1.
The results of the optimization of (M S; T F T ) are shown in Table 2. MODEP works well on this problem and the values of the second index I1 (whose optimal value is 1) are quite good, while the values for IH (whose optimal value is 1:44) are however good, compared to those reported in [3].It is worth to notice that, fixing n, IH seems to have a decreasing behavior as m increases (except when n = 20).
Finally, the results of the optimization of (T F T; T T ) are shown in Table 4. Here, while the performances as measured by I1 are still satisfactory, the results of IH are slightly worse than in the previous cases.
In this paper we have described an algorithm for optimization of multi-objective permutation flowshop scheduling problems. Some preliminary experimental results show that this approach is promising and reaches results which are comparable to the stateof-the-art algorithms. As a future line of research, we would like to add to our algorithm some method to enhance the diversity of the population, as done in other evolutionary multi-objective algorithms, like crowding distance or niching techniques.