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
http://hdl.handle.net/2268/21589
Optimization of Surface Allocation using Heuristic Approaches
English
[fr] Optimisation de l'allocation de surface en utilisant une approche heuristique
Langer, Yves [ > > ]
Bay, Maud mailto [Université de Liège - ULg > HEC-Ecole de gestion de l'ULg : UER > Recherche opérationnelle et gestion de la production >]
Crama, Yves mailto [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 mailto [Université de Liège - ULg > Département Argenco : Secteur TLU+C > ANAST (Systèmes de transport et constructions navales) >]
Rigo, Philippe mailto [Université de Liège - ULg > Département ArGEnCo > Constructions hydrauliques et navales >]
May-2005
Edt V Bertram
COMPIT 2005 , Hambourg, Germany
9
Yes
No
International
3-00-014981-3
OPTI'05
Bruxelles
Belgique
[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
http://hdl.handle.net/2268/21589

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Open access
Article OPTI.pdfAuthor postprint152.83 kBView/Open

Additional material(s):

File Commentary Size Access
Restricted access
Présentation OPTI05.ppt6.96 MBRequest copy

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.