Warianty tytułu
New heuristics for one-dimensional bin-packing
Konferencja
XIII Krajowa Konferencja Automatyzacji Procesów Dyskretnych
Języki publikacji
Abstrakty
Zadanie upakowania danego zestawu elementów w możliwie małej liczbie jednakowych pojemników, zwane bin-packing, występuje często w problemach dystrybucji i produkcji. W referacie opisuję kilka nowych metod heurystycznych rozwiązywania jednowymiarowej wersji tego problemu. Część metod opiera się na heurystyce MBS (minimum bin slack) autorstwa Gupty i Ho, która znajduje rozwiązanie wyznaczając najlepsze możliwe wypełnienie kolejnych pojemników. Inna metoda bazuje na metaheurystyce VNS (variable neighbourhood search) Mladenovićia i Hansena, stosowanej do rozwiązywania wielu problemów optymalizacji dyskretnej. Eksperymenty wykonane z wykorzystaniem standardowych testów porównawczych pokazują, że prezentowane metody mogą konkurować nie tylko z innymi heurystykami, ale również z metodami dokładnymi.
Several new heuristics for solving the one-dimensional bin packing problem are presented. Some of these are based on the minimum bin slack (MBS) heuristic of Gupta and Ho. A different algorithm is one based on the variable neighbourhood search metaheuristic of Miadenovic and Hansen. When tested on standard benchmark problem instances, algorithms proved capable of achieving very good results in comparison to other methods, both heuristic and optimum seeking.
Słowa kluczowe
Rocznik
Tom
Strony
45-54
Opis fizyczny
Bibliogr. 8 poz.
Twórcy
autor
- Politechnika Warszawska, Warszawa
Bibliografia
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.baztech-article-BSL6-0008-0036