Information Technology Reference
In-Depth Information
surVeY of MuLticriteriA fLoW-
shop scheduLing ALgorithMs
When two algorithms are compared,
C
(
A
,
B
)
and
C
(
B
,
A
) must be computed, because they are
not necessary complementary. Unless
C
(
A
,
B
)=1
and
C
(
B
,
A
)<1, it is not possible to establish that
A
weakly outperfoms
B
.
The non-cardinal measures
Dist
1
R
and
Dist
2
R
require
R
to be obtained. Their computations,
although more complicated than
C
, do not imply
a high complexity. They are based on an achieve-
ment scalarizing function:
In this section we will focus on published algo-
rithms devoted to multicriteria flow-shop schedul-
ing problems. For further information on general
multicriteria scheduling algorithms, we refer to
the following papers:
•
Nowicki & Zdrzałka (1990) presents a sur-
vey of the field of scheduling with control-
lable processing times.
{
}
d X Y
(
,
) max
=
0
l
,
(
z Y
( )
−
z X
(
))
k
k
k
k
=
1
,...
K
•
Gordon et al. (2002) focuses on due date
assignment models.
•
Hoogeveen (2005) includes an overview of
the bi-criteria worst-case analysis.
where
X
R
,
Y
PE
, and
∈
∈
1
•
Landa-Silva et al. (2004) reviews meta-
heuristics for general multi-objective prob-
lems and presents the application of these
techniques to scheduling problems.
l
k
=
(
)
( )
−
( )
max
z X
min
z X
k
k
X R
∈
X R
∈
Dist
1
R
is defined as:
1
For exhaustive surveys of multicriteria sched-
uling problems, see:
{
}
{
}
(
)
=
(
)
∑
min
Dist
1
PE
d X Y
,
R
R
Y PE
∈
x R
∈
•
Ruiz-Díaz & French (1983)
•
Nagar et al. (1995a)
While
Dist
1
R
measures the mean distance, over
the points in
R
, of the nearest point in
PE
,
Dist
2
R
gives the worst case distance, thus it is defined as:
•
T'kindt & Billaut (2001)
The topic of T'kindt & Billaut (2006) can be
useful as a good comprehensive reference work
on multicriteria scheduling.
Permutation flow-shop scheduling research
has been mostly restricted to the treatment of one
objective at a time. Furthermore, attention focused
on the makespan criterion. However, the total flow
time performance measure has also received some
attention. These two measures, each of which is
a regular performance measure, constitute a con-
flicting pair of objectives (Rinnooy Kan, 1976).
Specifically, the total flow time criterion is a
work in process inventory performance measure
whereas the makespan criterion is equivalent to
the mean utilization performance measure. While
total flow time is a customer-oriented performance
{
}
{
}
2
(
)
=
(
)
Dist
PE
max min
d X Y
,
R
X R
∈
Y PE
∈
The lower the values the better
PE
approxi-
mates
R
. Moreover, the lower the ratio
Dist
2
R
/
Dist
1
R
the more uniform the distribution of solu-
tions from
PE
over
R
.
Dist
1
R
induces a complete
ordering and let to weak outperformance relations.
Combining
PE
yielded by different algorithms
for an instance problem, a net set of non-dominated
solutions,
N
, is obtained. The
N
set is very useful as
R
for the evaluation of the new developments. An
important contribution is updating the published
N
set obtained for benchmark instances.
Search WWH ::
Custom Search