Ládapakolási és ütemezési algoritmusok - Az optimális közelítése

– A „szép matematika” számomra azt jelenti, mikor a gyakorlati problémára készítünk egy modellt, amelynek megoldása kristálytiszta matematikán alapul, s eredményét alkalmazzuk a gyakorlatban – jelenti ki Galambos Gábor. Az SZTE Juhász Gyula Pedagógusképző Kar Informatika Alkalmazásai Tanszékét vezető egyetemi tanár ilyen élményre példaként említi, amikor friss diplomásként a tervező vállalatnál az orosházi húsüzem térbeli szerkezetének méretezését kellett megoldania Cross-módszerrel.

 

Galambos_Gabor
Könyvfejezet születik. Galambos Gábor az elmúlt 15 évben ládapakolási algoritmusokkal foglalkozik – tapasztalatait összegzi. Fotó: Frank Yvette
Az optimalizálás mint matematikai feladvány irányába lökte Galambos Gábort az orosházi síküveggyárban a kétdimenziós táblák szabászati problémája. A 70-es évek második felében úgy jutott el a megoldáshoz, hogy kiindulópontnak a rudak egydimenziós modell alapján elvégezhető szabását tekintette. E matematikai módszert nevezik ládapakolási modellnek.

– Ha az a feladat, hogy rudakat szabjak kisebb darabokra úgy, hogy a lehető legkisebb legyen a selejt, akkor ezt úgy is meg tudom oldani, hogy egyrészt vannak olyan méretű ládáim, amekkora a rúd; másrészt vannak kisméretű tárgyaim, amelyeket csak egymás tetejére rakhatok a ládában. A cél az, hogy a tárgyak elrendezéséhez a lehető legkevesebb ládát használjam, miközben nem rakodhatok púposra – ismertette a matematikával foglalkozók körében ismert feladványt Galambos professzor. – E problémáról kiderült: ha mindenáron arra törekszem, hogy optimális megoldást adjak minden egyes problémára, és sok tárgyam van, akkor nagyon sok időre lenne szükség. Ezért közelítő algoritmusokat használnak a matematikusok. Ám ezzel megváltoznak a prioritások.

 

Kapacitások: járathoz buszt és sofőr

Az ütemezési algoritmus kicsit más, de a ládapakolási feladvány rokonproblémája. A Tisza Volán Zrt. számára dolgoztunk ki a pillanatnyilag létezőnél jobb megoldást arra, hogy ha a cég megkapja a várostól a menetrendet, akkor az abban szereplő járatokhoz miként lehet hozzárendelni a járműveket és sofőröket – gazdaságilag a legoptimálisabban. Az ilyen típusú K+F megbízatásokat Krész Miklós, az Informatika Alkalmazásai Tanszék főiskolai docense irányítja.

 

Egzakt algoritmusnál a feltételek között az idő nem számít, mert az optimumot akarjuk megkapni. A közelítő algoritmusnál viszont számít az idő – még akkor is, ha az eredmény távolabb esik az optimumtól. Ha e „gyors algoritmust” akarják gyártási folyamatba illeszteni, akkor meg kell határozni azt is, hogy a megoldás milyen messze van az optimumtól. Ezért vizsgálják a matematikusok, hogy a különböző algoritmusok a legrosszabb esetben milyen távol lehetnek az optimális megoldástól. Így aztán az az algoritmus a legjobb, amelyik a legrosszabb esetben is még viszonylag közeli megoldást ad az optimumhoz.

Újszászi Ilona

forrás: delmagyar.hu