SEMINAIRES DU  GOTHA
			____________________

	vendredi 30 mars au LIP6 (Site Scott) Salle C769 à 10h00.

	Exposé de Federico Della Croce, D.A.I., Politecnico di Torino

TITRE : 

Recovering Beam Search, a hybrid heuristic framework for combinatorial
optimization problems: application to machine scheduling problems.

RESUME :

We propose a framework for the development of polynomial time
heuristics for combinatorial optimization (CO) problems.  This
framework combines different classical techniques such as tree search
procedures (in a beam search context), bounding schemes and local
search.  The main structure of the proposed approach is the following:
a beam search with constant beam size is applied where the nodes
evaluation process is based on the weighted sum of the nodes upper and
lower bounds.  Peculiarity of the approach is that, for each node, the
lower and upper bounds are computed through an iterative approach
which generates a significant number of solutions causing an in-depth
exploration of the solutions space.  Once a node selected by the beam
and the corresponding partial solution are derived, the available
dominance conditions for the considered problem are applied to the
current partial solution x to see whether it is dominated by another
partial solution y with the same level of the search tree. If this is
the case, y becomes the new current partial solution.  Notice that by
keeping the same level of the search tree we guarantee to explore a
polynomial number of nodes.  This step allows to recover from previous
wrong decisions of the beam search procedure and can be seen as a
local search step on the partial solution.  We present here the
application to two well known machine scheduling problems: the
two-machine total completion time flow shop scheduling problem and the
single machine dynamic total completion time scheduling problem.  The
proposed framework seems reasonably general-purpose and applicable to
a wide range of CO problems.