Transformer rozwiązuje problem harmonogramowania warsztatów lepiej niż klasyczne heurystyki

Naukowcy z zespołu Faezeh Ardali opracowali nowatorską metodę rozwiązywania problemu harmonogramowania otwartego warsztatu (OSSP) przy użyciu architektury Transformer w połączeniu z głębokim uczeniem ze wzmocnieniem. Badanie, opublikowane w arXiv, przedstawia alternatywę dla klasycznych metod heurystycznych w jednym z najbardziej złożonych problemów optymalizacyjnych w przemyśle.

Problem harmonogramowania otwartego warsztatu występuje w wielu środowiskach przemysłowych i usługowych, ale pozostaje obliczeniowo trudny wraz ze wzrostem liczby zadań i maszyn. Podczas gdy dokładne metody szybko stają się niewykonalne, klasyczne reguły dyspozycyjne i metaheurystyki mogą wymagać znacznego dostrajania, aby utrzymać jakość rozwiązań na dużą skalę.

Kluczowe wnioski

• Metoda oparta na architekturze Transformer z enkoder-dekoder i mechanizmem wielogłowicowej uwagi osiąga rozwiązania w zakresie 15–30% od najlepszych znanych wartości dla instancji benchmarkowych Taillard.
• Model wytrenowany na małych instancjach (4x4 do 10x10) skutecznie generalizuje na znacznie większe problemy (40x40 do 100x100) bez konieczności ponownego trenowania.
• W porównaniu z klasycznymi heurystykami SPT, LPT, MWKR i EST, Transformer osiąga średnie odchylenia 12,89–15,12% względem standardowych dolnych granic.
• Metoda wymaga jedynie macierzy czasów przetwarzania jako wejścia, oferując rozwiązanie o niskim zapotrzebowaniu na cechy w porównaniu z tradycyjnymi podejściami.
• System pozostaje konkurencyjny względem heurystyki EST przy jednoczesnym znacznym przewyższeniu metod SPT i LPT.

Architektura i metodologia

Opracowany system wykorzystuje architekturę enkoder-dekoder z mechanizmem wielogłowicowej uwagi, charakterystyczną dla modeli Transformer. Kluczową zaletą tego podejścia jest minimalistyczne wymaganie dotyczące danych wejściowych — model potrzebuje jedynie macierzy czasów przetwarzania, co znacznie upraszcza implementację w porównaniu z metodami wymagającymi złożonych cech inżynieryjnych.

Model był trenowany na instancjach benchmarkowych Taillard o rozmiarach 4x4, 5x5, 7x7 i 10x10. Te relatywnie małe przykłady treningowe okazały się wystarczające do nauczenia modelu ogólnych zasad harmonogramowania, które następnie można było zastosować do znacznie większych problemów.

Wyniki i porównania

Zespół badawczy przeprowadził kompleksową ocenę skalowalności, testując wytrenowany model na losowo generowanych instancjach od 40x40 do 100x100 maszyn i zadań. Porównano wyniki z czterema klasycznymi heurystykami dyspozycyjnymi: SPT (Shortest Processing Time), LPT (Longest Processing Time), MWKR (Most Work Remaining) oraz EST (Earliest Start Time).

Transformer osiągnął średnie odchylenia w zakresie 12,89–15,12% względem standardowych dolnych granic dla dużych instancji. Szczególnie imponujące jest to, że model pozostał konkurencyjny względem heurystyki EST, uważanej za jedną z najskuteczniejszych w tej klasie problemów, jednocześnie znacznie przewyższając prostsze metody SPT i LPT.

Implikacje dla przemysłu

Wyniki wskazują, że polityka harmonogramowania oparta na Transformer, wytrenowana na małych instancjach OSSP, może skutecznie generalizować na znacznie większe problemy rzeczywiste. To oznacza potencjalną rewolucję w podejściu do optymalizacji procesów produkcyjnych, gdzie tradycyjne metody często wymagają czasochłonnego dostrajania parametrów dla każdego nowego środowiska.

Badanie otwiera drogę do zastosowania nowoczesnych architektur uczenia maszynowego w klasycznych problemach optymalizacji kombinatorycznej, oferując alternatywę opartą na danych dla tradycyjnych reguł heurystycznych w harmonogramowaniu przemysłowym.