|Reference : Optimization of Surface Allocation using Heuristic Approaches|
|Scientific congresses and symposiums : Paper published in a book|
|Engineering, computing & technology : Civil engineering|
Engineering, computing & technology : Mechanical engineering
|Optimization of Surface Allocation using Heuristic Approaches|
|[fr] Optimisation de l'allocation de surface en utilisant une approche heuristique|
|Langer, Yves [ > > ]|
|Bay, Maud [Université de Liège - ULg > HEC-Ecole de gestion de l'ULg : UER > Recherche opérationnelle et gestion de la production >]|
|Crama, Yves [Université de Liège - ULg > HEC-Ecole de gestion de l'ULg : UER > Recherche opérationnelle et gestion de la production >]|
|Bair, Frédéric [Université de Liège - ULg > Département ArGEnCo > Constructions hydrauliques et navales >]|
|Caprace, Jean-David [Université de Liège - ULg > Département Argenco : Secteur TLU+C > ANAST (Systèmes de transport et constructions navales) >]|
|Rigo, Philippe [Université de Liège - ULg > Département ArGEnCo > Constructions hydrauliques et navales >]|
|Edt V Bertram|
|COMPIT 2005 , Hambourg, Germany|
|[en] Optimization ; Surface Allocation|
|[en] In this paper, we present a scheduling problem that arises in factories producing large building
blocks (in our case, a shipyard workshop producing prefabricated keel elements). The factory is
divided in several equal size areas. The blocks produced in the factory are very large, and, once a
building block is placed in the factory, it cannot be moved until all processes on the building block
are finished. The blocks cannot overlap. The objective is to maximize the number of building
blocks produced in the factory during a certain time window.
To solve this problem, we propose heuristics inspired by techniques initially developed for the
three-dimensional bin packing problem, e.g. Faroe and al. (2003), since constraints for both
problems are quite similar.
Starting from an unfeasible solution, where blocks can overlap, a Guided Local Search (GLS)
heuristic is used to minimize the sum of total overlap. If a solution with zero overlap is found,
then it is a feasible solution; otherwise the block with the biggest overlap is removed and the
procedure is restarted. The GLS algorithm has been improved by Fast Local Search (FST) tech-
niques in order to speed up convergence to a local minimum. Additionally, neighborhoods are
restricted to their smallest size so as to allow their evaluation in polynomial-time.
In a last step, we explain the additional real-life issues arising in the industrial application and
how firm-specific constraints can be conveniently considered by the model.
|Researchers ; Professionals|
|File(s) associated to this reference|
All documents in ORBi are protected by a user license.