13.2. 13.2. Algoritmus a „futószalag” feladat megoldására

Kézenfekvő az alábbi egyszerű algoritmus, amelynek lényege, hogy a „futószalag” feladatot „házasság” feladatok sorozatával oldjuk meg.

1. lépés: Kezdeti hozzárendelés készítése ( ).

Ezt végezhetjük például a legkisebb időértékeken keresztül.

2. lépés: A hozzárendeléshez tartozó ütemidő meghatározása.

Jelöljük -al a futószalag ütemidejét, amely

tehát a hozzárendelésben szereplő idők maximuma.

3. lépés: Új hozzárendelés készítése.

Próbáljunk meg olyan új hozzárendelést készíteni, amelynél a futószalag ütemideje az előzőnél kisebb. Ez tulajdonképpen egy olyan „házasság” feladat, amelyben ott lehetséges a hozzárendelés, ahol . A „házasság” feladat megoldhatósága szerint két esetet vizsgálunk:

  1. Ha nem tudtuk az összes személyt hozzárendelni a munkákhoz, akkor az előző hozzárendelés a legjobb. Vége az algoritmusnak.

  2. Ha minden személyt hozzá tudtunk rendelni a munkákhoz, akkor egy olyan új hozzárendelést kaptunk, amelyhez tartozó ütemidő biztosan jobb (kisebb), mint az előző. A 2. és a 3. lépéseket addig ismételjük, amíg az (1) esetet nem kapjuk.

Nyilvánvaló, hogy az eljárás véges lépésben végetér.