Information Technology Reference
In-Depth Information
every criterion, or it may present a more complex
composition. Despite the apparent simplicity of
the methods, it conceals two difficulties:
the makespan, subject to a determined flow time
level (the first one is devoted to preemptive job
models). González & Johnson (1980) proposes
minimizing the makespan, subject to a bound on
the number of preemptions. Sin (1989) consid-
ers the problem of minimizing the makespan
and the number of preemptions, for a set of jobs,
constrained to due dates.
When a set of goals for each criterion is known,
the target vector approaches are appropriate. The
most popular is
Goal Programming
(introduced
by Charnes & Cooper, 1961), for which the
minimization of the deviation from the specified
goals is the aim.
Non-scalarizing approaches do not explic-
itly use this kind of scalarizing function. For
example,
Lexicographic
and
Max-ordering
are
non-scalarizing approaches.
Max-ordering chooses the alternative with
the minimum value of the worst values. After a
normalization process,
z
j
is the worst value of
X
,
if and only if,
1. The difficulty of expressing the decision-
maker preferences by means of a function.
Interactive approaches overcome this draw-
back,
e.g. Analytic Hierarchy Process
could
be useful (Saaty, 1980).
2. The computational complexity of minimiz-
ing the function in a direct manner.
The set of all SE solutions can be found
considering a wide diversified set of weights
(Parametric Programming may be used to solve
this problem). Selen & Hott (1986) and Wilson
(1989) apply this technique to the
F//f(ΣC
i
,C
max
)
,
where
f
is a linear combination. Shmoys & Tar-
dos (1993) proposes a linear combination of the
makespan and a total cost function, for unrelated
parallel machine models.
The
distance to the ideal point
approach
(Horsky & Rao, 1984) consists in minimizing
the distance to an ideal solution. The ideal point
is settled according to the optimum of each in-
dividual single-criterion. It is also known as the
compromise solution
method.
The
ε-constraint
(Chankong & Haimes, 1983)
and the
Target-Vector
approaches are scalariza-
tion as well as hierarchical methods. A constraint
system representing levels ε
i
of satisfaction, for
some criteria, is established, and the objective
is to find a solution, which provides a value, as
close as possible, to the pre-defined goal for each
objective. A single-objective minimization subject
to constraints of levels ε
i
for the other objective
functions is formulated. The formulation is solved
for different levels ε
i
, to generate the entire Pareto
optimal set. Some authors consider that the main
criteria must be fixed by constraints, others put
the main criteria in the objective of the formula-
tion by turn. It would depend on the mathematical
programs to solve. Leung & Young (1989) and Eck
& Pinedo (1993) present algorithms to minimize
{
}
( )
=
( )
( )
( )
z X
max
z X z X
,
, ...,
z X
j
1
2
K
Then,
X
is the best alternative, if, and only if,
there is not
Y
such that
z
j(y)
(
Y
)
<z
j(x)
(
X
).
The
two phases
method by Ulungu (1993)
consists in determining the set of SE solutions by
means of a weighted sum scalarization algorithm,
and then, in the second phase, searching for the
NE solutions, following a specific problem-
dependent method.
Only a few algorithms have been developed
based on B&B techniques for MOCO problems
(Ehrgott & Gandibleux, 2001). On the other
hand, approximation for MOO is a research area
which has gained increasing interest in recent
years. Multi-objective metaheuristics seek an
approximate set of Pareto optimal solutions. The
main question is how to ensure that the obtained
non-dominated set covers the Pareto front as
Search WWH ::
Custom Search