Nowe heurystyczne metody rozwiązywania jednowymiarowego problemu bin-packing

• Autorzy: Fleszar K.

Warianty tytułu

EN

New heuristics for one-dimensional bin-packing

• Konferencja: XIII Krajowa Konferencja Automatyzacji Procesów Dyskretnych
• Języki publikacji: PL

Abstrakty

PL

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.

EN

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

PL

upakowanie optymalne; bin-packing; algorytmy; metoda heurystyczna

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Zeszyty Naukowe. Automatyka / Politechnika Śląska
• Rocznik: 2002
• Tom: z. 136
• Strony: 45--54
• Opis fizyczny: Bibliogr. 8 poz.

Twórcy

autor

Fleszar K.

• Politechnika Warszawska, Warszawa