Paper published in a book (Scientific congresses and symposiums)
Optimization of Surface Allocation using Heuristic Approaches
Langer, Yves; Bay, Maud; Crama, Yves et al.
2005In COMPIT 2005 , Hambourg, Germany
Peer reviewed
 

Files


Full Text
Article OPTI.pdf
Author postprint (156.5 kB)
Download
Annexes
Présentation OPTI05.ppt
Publisher postprint (7.13 MB)
Request a copy

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
Optimization; Surface Allocation
Abstract :
[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.
Disciplines :
Civil engineering
Mechanical engineering
Author, co-author :
Langer, Yves
Bay, Maud ;  Université de Liège - ULiège > HEC-Ecole de gestion : UER > Recherche opérationnelle et gestion de la production
Crama, Yves  ;  Université de Liège - ULiège > HEC-Ecole de gestion : UER > Recherche opérationnelle et gestion de la production
Bair, Frédéric ;  Université de Liège - ULiège > Département ArGEnCo > Constructions hydrauliques et navales
Caprace, Jean-David ;  Université de Liège - ULiège > Département Argenco : Secteur TLU+C > ANAST (Systèmes de transport et constructions navales)
Rigo, Philippe  ;  Université de Liège - ULiège > Département ArGEnCo > Constructions hydrauliques et navales
Language :
English
Title :
Optimization of Surface Allocation using Heuristic Approaches
Alternative titles :
[fr] Optimisation de l'allocation de surface en utilisant une approche heuristique
Publication date :
May 2005
Event name :
OPTI'05
Event place :
Bruxelles, Belgium
Audience :
International
Main work title :
COMPIT 2005 , Hambourg, Germany
Edition :
Edt V Bertram
ISBN/EAN :
3-00-014981-3
Pages :
9
Peer reviewed :
Peer reviewed
Available on ORBi :
since 09 September 2009

Statistics


Number of views
117 (22 by ULiège)
Number of downloads
74 (5 by ULiège)

Bibliography


Similar publications



Contact ORBi