Information Technology Reference
In-Depth Information
tivariant condition of corresponding alternative
schedules. In fact the description and valuation
of alternative decisions are not naturally accom-
plished by only one criterion, but by several (
e.g.
makespan, flow-time, completion-time, tardiness,
inventory, utilization, etc.). This is certainly the
natural framework of the Multicriteria Decision
Making discipline (MDM). A solution which is
optimal with respect to a given criterion might
be a poor candidate for another. The trade-offs
involved in considering several different criteria
provide useful insights for the decision-maker.
Thus considering Combinatorial Optimization
(CO) problems with more than one criterion is
more relevant in the context of real-life schedul-
ing problems.
Most of the multicriterion approaches applied
to scheduling problems are based on Multi-Ob-
jective Optimization (MOO) models. Of course,
to expect to find the “Optimum” schedule must
usually be discarded. We would be satisfied to
find the set of non-dominated, also called Pareto
optimal, alternatives. At this point, we have to let
some subjective considerations intervene, such as
the decision-maker preferences. It is actually an
MDM problem, and at the present time, there is
no other rational tool to apply to discard alterna-
tives. MOO was originally conceived to find a set
of Pareto optimal alternative solutions. Only with
the breakthrough of metaheursitcs in solving CO
problems, did researchers begin to adapt them to
solve Multi-Objective Combinatorial Optimiza-
tion problems. Then, the acronym MOCO started
to appear in the scientific literature together with
the techniques developed to deal with them. Re-
search in this important field has been scarce when
compared to research in single-criterion schedul-
ing. Until the late 1980's, only one criterion was
considered in scheduling problems. Furthermore,
until the 1990's, most work in the area of multiple
criteria scheduling consists of bi-criteria studies
of the single machine case (Hoogeveen, 1992).
In this paper, an effort has been made to re-
view the publications concerning Multicriteria
Permutation Flow-Shop Scheduling problems,
from the late eighties to the most recent papers,
giving attention to the results that have not been
surveyed until now and suggesting directions for
future research (the detailed theorems and proofs
have been omitted to avoid a huge paper). In the
next section, the classical flow-shop scheduling
problem statement is presented. We will briefly
introduce MOO theory, general Multicriteria
Optimization methods and evaluating metrics
(section 3), followed by a survey on multicriteria
algorithms devoted to the scheduling problem
we are dealing with (section 4). We conclude, in
section 5, with a summary discussion on research
directions.
perMutAtion fLoW-shop
scheduLing probLeM
In the classical permutation flow-shop schedul-
ing problem, there are
n
jobs and
m
machines, or
stages. Each job needs to complete one operation
on each of the machines during a fixed process-
ing time. So, the aim is to find the schedule, or
job sequence, that optimizes certain performance
measures. In this paper, we focus attention on the
permutation flow-shop situation, where all jobs
must pass through all machines in the same order.
Potts et al. (1991) presents a comparative study
of permutation versus non-permutation flow-shop
scheduling problems.
The scheduling process involves just finding
the optimal job sequencing. Nevertheless, the
computational complexity usually grows expo-
nentially with the number of machines,
m
, making
the problem intractable. This problem, like almost
all deterministic scheduling problems, belongs to
the wide class of CO problems, many of which are
known to be NP-hard (Garey & Johnson, 1979).
What it means is that it is unlikely that efficient
exact optimization algorithms exist to solve them.
Only a few scheduling problems have been shown
to be tractable, in the sense that they are solvable
Search WWH ::
Custom Search