Information Technology Reference
In-Depth Information
still useful in saving computational effort when
looking for non-dominated solutions (Mokotoff,
2009). Potts (1980) presents a branching rule.
Selen & Hott (1986) proposes a Goal Programming
formulation. Taillard (1993) presents, besides a
set of very useful benchmarks, a lower bound for
the makespan. Carlier & Rebaï (1996) presents
two B&B algorithms.
Heuristics and metaheuristics have been mainly
developed for CO problems. In contrast to exact
methods that guarantee optimality, heuristic meth-
ods seek near optimal solutions in a reasonably
bounded time. Metaheuristics are more general
than heuristics, in the sense that they are applicable
to different problems, while heuristics are usually
problem-dependent.
A constructive algorithm builds a solution,
starting from the input data (without it being
necessary to know a previous feasible solution),
following a set of rules. There is a class of algo-
rithms which share a similar way of making a
schedule: a sorting list with all the jobs is made.
The accuracy of any
list scheduling
algorithm is
intimately related to the priority rule applied. There
are more than one hundred dispatching rules, as
can be seen in Panwalkar & Iskander (1977) and
Haupt (1989).
The most important constructive algorithms
dedicated to the
F//Cmax
problem can be clas-
sified by their design as a list scheduling algo-
rithm. In order to minimize the makespan, the
list of jobs must be made in such a way as to
give higher priority to the jobs consuming more
total processing time. That is to say, the jobs
with the longest total processing time should not
be placed at the last positions of the list. Based
on this premise, a simple algorithm is presented
by Nawaz et al. (1983) (NEH algorithm, in the
following). NEH algorithm produces very good
sequences in comparison with heuristics existing
even up to the present. The results of the proposed
algorithm show that it performs especially well
on large flow-shop problems, in both the static
and dynamic sequencing environments. Taillard
(1990) presents an important improvement in sav-
ing computational effort for the NEH algorithm.
Gupta (1972) presents three algorithms to deal
with total flow time and maximum flow time (not
simultaneously). Laha & Chakraborty (2009) and
Rajendran (1993) present constructive algorithms
for the
F
//
ΣC
i
problem. The first one is based on
the principle of job insertion, and the second one
could be thought as an extension of the NEH
algorithm and performs very well.
Improvement algorithms need a feasible solu-
tion as starting-point and are intended to improve
it by iterative small changes. This iterative im-
provement can be achieved by means of many
different processes.
Threshold algorithms are designed accord-
ing to three techniques: Iterative Improvement,
Threshold Accepting and Simulated Annealing
(SA), the most popular one.
Considering
F
//
C
max
, Osman & Potts (1989)
presents four SA algorithms varying the neigh-
bouring generating method. Their results show
that insertion performs better than swapping. The
SA algorithms presented by Nowicki & Zdrzałka
(1990) have similar performance than Osman &
Potts (1989). Only the algorithm presented in
Ishibuchi et al. (1995) seems to perform better
for large instances. Laha & Chakraborty (2007)
introduces SA in the NEH algorithm and Wodecki
& Bozejko (2002) presents a parallel SA.
Parthasarathy & Rajendran (1997) presents an
application of SA to the
F//Σw
i
T
i
. In this paper,
the authors introduced the Random Insertion
Perturbation Scheme that is employed in some
later papers.
In Laha & Chakraborty (2008) SA is applied
to solve the
F//ΣC
i
problem. Liu & Reeves (2001)
and Rajendran & Ziegler (2004 and 2005) consider
also this problem, Liu & Reeves (2001) using pair-
wise exchange and Rajendran & Ziegler (2004
and 2005) using Ant Colony Optimization (ACO).
Rajendran & Ziegler (1997) presents heuristics
dealing with the total weighted flow time.
Search WWH ::
Custom Search