Multicriteria Flow Shop Scheduling Problem - Enterprise Information Systems Design, Implementation and Management: Organizational Applications - page 217

MuLticriteriA AnALYsis
for coMbinAtoriAL
optiMizAtion probLeMs

Based on Johnson's rule, Koulamas (1998)
proposes an improvement heuristic which uses
job passing.
Tabu Search (TS) is probably the most tested
local search concerned with scheduling problems.
Some applications to the flow-shop schedul-
ing problem have been presented in: Taillard
(1990) and Reeves (1993) and, more recently, in
Grabowski & Wodecki (2004).
Unlike the previously-mentioned techniques,
Genetic and Evolutionary Algorithms (GA and
EA, respectively, in the following) start with a set
of solutions instead of only one: Reeves (1995)
applies GA to the flow-shop scheduling problem.
Differential evolutionary optimization is applied
to permutation flow-shop scheduling problem for
minimizing makespan, mean flow time and total
tardiness, individually considered, in Onwubolu
& Davendra (2006).
Research on metaheuristics is quite extensive.
Ruiz & Maroto (2005) and Dorn et al. (1996)
survey this field.
Real-life scheduling problems require more
than one criterion. Nevertheless, the complex
nature of flow-shop scheduling has prevented the
development of models with multiple criteria. In
the following, we will consider the Multicriterion
Flow-Shop Scheduling problems.
For further information about deterministic
scheduling and flow-shop, considering only
single-criterion problems, we refer the reader to the
topics and PhD thesis of: Blazewicz et al. (2007);
Brucker (2004); Ruiz (2003); Pinedo (2002); An-
drés (2001); Schulz (1996) and Parker (1995); or
the survey papers of: Lawler et al. (1993); Dudek
et al. (1992); Monma & Rinnooy Kan (1983) and
the earliest Baker (1975).

Quality is, in real-life, a multidimensional notion.
A schedule is valued on the basis of a number of
criteria, for example: makespan, work-in-process
inventories, idle times, observance of due dates,
etc. If only one criterion is taken into account, no
matter what criterion is considered, some aspect
of the quality of the schedule will result regard-
less. An appropriate schedule can not be obtained
unless one observes the whole set of important
criteria. The multidimensional nature of the prob-
lem at hand leads us to the area of Multicriteria
Optimization (see Ehrgott & Wiecek, 2005, for
a state of the art).
When a problem appears as a multicriteria
case, it is necessary to take into account different
objective functions. The solution may vary accord-
ing to the criterion considered individually. If the
criteria are not conflicting, it is possible to obtain
a global optimal solution. In the vast majority of
cases, they are conflicting and thus the knowledge
of the decision-maker preferences is necessary to
solve the problem.
Considering only one regular criterion, general
scheduling problems belong to the CO field and
they have been shown to be NP-hard (except for
restricted special cases).
Even though MDM, as well as CO, have been
intensively studied by many researchers for many
years, it is surprising that a combination of both,
i.e. MOCO, was not widely studied until the last
decade, as it is not long since interest in this field
has been shown. The proliferation of metaheuristic
techniques has encouraged researchers to apply
them to this highly complex problem.
In this section, we will present a brief intro-
duction to MOCO problems, including a general
problem formulation, the most important theoreti-
cal properties, the existing methods for dealing
with them, and the analysis of performance.