Information Technology Reference
In-Depth Information
F2 //f(C max ,T max )
measure, the makespan criterion is a firm-oriented
performance measure. Therefore, the set of ef-
ficient solutions to a bi-criteria model that seeks
to optimize both measures simultaneously would
contain valuable trade-off information, crucial to
the decision-maker, who has to identify the most
preferable solution, according to her preferences.
Solving a bi-criteria model for a general num-
ber of machines implies heavy computational
requirements, since both criteria makespan and
total flow time, lead to NP-hard problems even
when they are treated individually ( F3 // C max and
F2 // ΣC i are NP-hard in the strong sense). The
majority of initial research on bi-criteria flow-
shop problems concerns the two-machine case, in
which some combination of ΣC i and C max has to be
minimized. Because any lexicographic approach
including ΣC i will be NP-hard, research effort is
being concentrated on approximate algorithms.
In the following, we summarize the published
results for each case problem.
Daniels & Chambers (1990) presents an exact
B&B.
F2 //f(C max ,ΣU i ) and F2 //f(C max ,ΣT i )
Liao et al. (1997) presents B&B algorithms.
F//f(ΣC i ,C max )
Selen & Hott (1986) and Wilson (1989), pres-
ent a Mixed Integer Formulation considering a
linear combination of makespan and flow time.
Chang et al. (2002) proposes a MOGA algo-
rithm based on the concept of gradual priority
weighting. The search process starts along the
direction of the first selected objective function,
and progresses such that the weight for the first
objective function decreases gradually, and the
weight for the second objective function increases
gradually.
F2//ΣC i ,C max
F//ΣC i ,C max
Rajendran (1992), Neppalli et al. (1996), Gupta
et al. (2001) and T'kindt et al. (2003), present
lexicographical approaches, where the total flow
time has to be minimized among the schedules
that minimize the makespan.
Local search algorithms based on ACO have
been proposed by T'kindt et al (2002).
Huang & Lim (2003) presents a technique
named Local Dynamic Programming.
T'kindt et al. (2003) presents a B&B algorithm,
which can solve problem instances of up to 35
jobs to optimality.
Sayin & Karabati (1999) presents an a poste-
riori approach based on B&B.
Bagchi (1999) presents a MOGA that improves
a previous MOGA presented by Srinivas & Deb
(1995). Pasupathy et al. (2006) presents a MOGA
based on ranks that are computed by means of
crowding distances.
Varadharajan & Rajendran (2005) and Mokot-
off (2009), present MOSA algorithms. The first
one is based on a similar idea than Chang et al.
(2002), whereas the second one is based on the
concept of Pareto dominance.
Framinan et al. (2002) investigates a priori and
a posteriori heuristics. The a posteriori heuristic
uncovers non-dominated solutions by varying the
weight criteria in an effective way.
Rajendran & Ziegler (2009) applies ACO
techniques.
F2 //f(ΣC i ,C max )
Nagar et al. (1995b) and Sivrikaya-Serifoglu
& Ulusoy (1998), present heuristics and B&B
algorithms.
F//C max ,ΣT i
Search WWH ::




Custom Search