Erőforrás- és munkaütemezés

Info

Mit tanulsz meg ebből a cikkből?

  • Mi az a hozzárendelési probléma (assignment problem), és hogyan oldja meg a magyar módszer
  • Mi a különbség a munkakiosztás (ki csinálja) és az ütemezés (mikor, milyen sorrendben) között
  • Mi az átfutási idő (makespan), és miért ezt akarjuk minimalizálni
  • Miért NP-nehéz a több munkát, több fázist tartalmazó ütemezés – és miért elég egy jó heurisztika
  • 💡 És hogyan ad a JobOptim munkanapló olyan naprakész képet a munkáidról, amire a jó ütemezési döntés épül

Egy kivitelező ritkán csinál egyszerre egy dolgot. Fut három fürdőszoba, egy térkövezés indul, egy tetőre ajánlatot kell adni, és közben két brigád között kell elosztani a hetet. A kérdés mindennap ugyanaz: melyik csapat melyik munkára menjen, és milyen sorrendben? Egy-két munkánál ez fejben is megy. Öt párhuzamos munkánál, változó határidőkkel már komoly fejtörő – és pontosan itt lép színre a matematika.

Két kérdés, két külön feladat

A „hogyan szervezzem a munkáimat?" valójában két különböző optimalizálási feladat, amelyeket érdemes szétválasztani:

  1. Hozzárendelés (assignment): ki csinálja az adott munkát – melyik brigád melyik feladatot kapja.
  2. Ütemezés (scheduling): mikor és milyen sorrendben – hogyan soroljuk időben a munkákat és a fázisokat, hogy az egész minél hamarabb kész legyen.

Mindkettő kombinatorikus optimalizálási feladat – ugyanabba a családba tartozik, mint a vágásoptimalizálás: sok lehetséges elrendezés közül keressük a legjobbat. A jó hír, hogy az elsőre van egy elegáns, egzakt megoldás.

A hozzárendelési probléma és a magyar módszer

Képzeld el, hogy 3 brigádod van és 3 munkád, és minden brigád minden munkát el tud végezni – csak nem ugyanannyi idő vagy költség alatt. Ezt egy költségmátrixba írjuk: minden sor egy brigád, minden oszlop egy munka, a cellában pedig a becsült idő (vagy költség).

Fürdőszoba Térkövezés Tetőjavítás
A brigád 4 nap 6 nap 3 nap
B brigád 5 nap 3 nap 4 nap
C brigád 7 nap 5 nap 2 nap

A kérdés: hogyan párosítsuk össze a brigádokat a munkákkal úgy, hogy mindenki pontosan egy munkát kapjon, és az összidő a lehető legkisebb legyen? A cél a költség minimalizálása:

Ahol = az brigád munkán töltött ideje, pedig a párosítás (melyik brigád melyik munkát kapja). Elsőre azt gondolnánk: próbáljuk ki az összes párosítást. brigádnál ez lehetőség – háromnál még csak 6, de tíz brigádnál már több mint 3,6 millió.

Szerencsére nem kell próbálgatni. A magyar módszer (angolul Hungarian algorithm, más néven Kuhn–Munkres-algoritmus) garantáltan megtalálja az optimális párosítást, méghozzá gyorsan – polinom időben. Nevét nem véletlenül kapta: Kőnig Dénes és Egerváry Jenő magyar matematikusok gráfelméleti eredményeire épül. A fenti példában az optimum: A → Fürdőszoba (4), B → Térkövezés (3), C → Tetőjavítás (2), összesen 9 nap – kézzel is leellenőrizheted, hogy nincs jobb párosítás.

Tip

A kulcs a jó költségmátrix A magyar módszer csak annyira jó, amennyire pontosak a becsléseid. Ha nem tudod, melyik brigád mennyi idő alatt végez egy munkafajtával, a mátrix tippelés. Itt jön képbe, hogy vezetsz-e naplót a korábbi munkákról: a valós átfutási idők adják a megbízható becslést.

Az ütemezés: sorrend és átfutási idő

A hozzárendelés megmondta, ki mit csinál. De ha egy brigádnak több munkája van egymás után, akkor jön a második kérdés: milyen sorrendben? És ha több brigád dolgozik párhuzamosan, mikor lesz kész az egész?

Itt a kulcsmérőszám az átfutási idő, angolul makespan (): az az időpont, amikor az utolsó munka is elkészül.

Ahol = az munka befejezési ideje. A lényeg a max: nem az számít, hogy egy-egy munka külön milyen gyors, hanem hogy a leglassabb ág mikor ér véget. Egy projekt akkor kész, amikor a legutolsó darabja is kész.

Az ütemezés célja jellemzően minimalizálása. Ez viszont már NP-nehéz: ha munkát kell sorba rendezni, a lehetséges sorrendek száma

ami ugyanúgy kombinatorikusan robban, mint a vágásoptimalizálásnál. Már 15 munkánál több mint sorrend van. A tökéletes ütemezést tehát a gyakorlatban nem számoljuk ki – heurisztikákkal keresünk nagyon jó megoldást:

Heurisztika Szabály Mire jó
SPT (Shortest Processing Time) a legrövidebb munka megy előre átlagos várakozás csökkentése
LPT (Longest Processing Time) a leghosszabb munka megy előre párhuzamos brigádok terhének kiegyenlítése
Kritikus út (CPM) a függőségi lánc leghosszabb ága kap prioritást határidős, több fázisú projektek
  • Az SPT a rövid munkákat engedi előre – így kevesebb munka vár sokat.
  • Az LPT a nagy munkákat kezdi előbb, hogy a végén ne egy óriási feladat húzza el az egészet; több párhuzamos brigádnál ez egyenletesebb terhelést ad.
  • A kritikus út módszer (Critical Path Method) a fázisok közti függőségeket veszi figyelembe: egy fürdőszobánál a burkolás nem kezdődhet a vízszigetelés előtt. A leghosszabb kötött láncot hívjuk kritikus útnak – ez határozza meg a leghamarabbi befejezést.

A terhelés kiegyenlítése

Több párhuzamos brigádnál van még egy hasznos mérőszám: a kihasználtság, vagyis mennyire egyenletesen oszlik el a munka. Ha egy brigád agyon van terhelve, a másik meg áll, az egész projekt lassú lesz.

Ahol = az egyes munkák ideje, = a brigádok száma, = az átfutási idő. Minél közelebb van az 1-hez (100%), annál kevesebb az állásidő és annál kiegyensúlyozottabb a beosztás. Ha az egyik brigád kihasználtsága 100%, a másiké 50%, tudjuk, hogy átcsoportosítással rövidebb lehetne az egész.

Kézzel vagy rendszerrel? A láthatóság a lényeg

Néhány munkánál a fejben tartott terv is elég. De amint belép a valóság – több egyszerre futó munka, több brigád, változó határidők, megrendelőre váró fázisok, csúszások –, a kézi követés összeomlik. Nem az a baj, hogy nem tudod kiszámolni az optimumot; az a baj, hogy nem látod tisztán az állapotot: melyik munka hol tart, ki a felelős, mi a ma lejárt teendő, melyik áll anyagra várva.

Itt a lényeg nem egy varázsgomb, hanem a naprakész, megosztható kép. A matematika megmondja, mi az elvi optimum (magyar módszer a kiosztásra, makespan az ütemezésre) – de a jó döntéshez pontos, valós idejű adat kell a munkáidról. Ezt adja egy munkanapló-rendszer.

Tip

Próbáld ki a JobOptim munkanaplót A JobOptim online munkanapló kivitelezőknek: a munkákat szakaszonként (érdeklődés → felmérés → ajánlat → folyamatban → átadás) követed, teendőket és felelősöket osztasz ki, a terepen pedig csak fotózol és diktálsz – a bejegyzésekből riport áll össze, a megrendelő pedig linken vagy QR-kóddal látja, hol tart a munka. Telefonról, app telepítése nélkül, magyarul. Ez az a láthatóság, amire a jó ütemezés épül. 👉 Nyisd meg a joboptim.com-ot

A JobOptim a CutOptim készítőitől van, az Optim család tagjaként: a CutOptimmal az anyagot tervezed meg, a JobOptimmal a kivitelezést dokumentálod – tervtől az átadásig.

Kapcsolódó olvasmányok és számítások

GYIK

Mi az a hozzárendelési (assignment) probléma?

A hozzárendelési probléma azt a kérdést oldja meg, hogyan párosítsunk össze erőforrásokat (pl. csapatokat, brigádokat) feladatokkal (pl. munkákkal) úgy, hogy a teljes költség vagy idő a lehető legkisebb legyen, és mindenki pontosan egy feladatot kapjon. Klasszikus kombinatorikus optimalizálási feladat, amelyet a magyar módszerrel (Kuhn–Munkres) hatékonyan, polinom időben meg lehet oldani.

Mi az a magyar módszer?

A magyar módszer (Hungarian algorithm, Kuhn–Munkres-algoritmus) a hozzárendelési probléma egzakt megoldója. Nevét Kőnig Dénes és Egerváry Jenő magyar matematikusok munkája után kapta. Egy költségmátrixból – ahol minden sor egy csapat, minden oszlop egy munka, a cellák pedig a költséget/időt jelölik – garantáltan megtalálja a minimális összköltségű párosítást, kipróbálás nélkül.

Mi a különbség a hozzárendelés és az ütemezés között?

A hozzárendelés (assignment) azt mondja meg, KI csinálja az adott munkát – melyik csapat melyik feladatot kapja. Az ütemezés (scheduling) azt mondja meg, MIKOR és MILYEN SORRENDBEN – hogyan sorold időben a munkákat és fázisokat, hogy a teljes átfutási idő (makespan) a legrövidebb legyen. A kettő együtt adja a teljes tervet.

Miért nehéz probléma az ütemezés?

Míg a tiszta 1:1 hozzárendelés polinom időben megoldható, a több munkát, több fázist és sorrendi függőségeket tartalmazó ütemezés (job shop scheduling) NP-nehéz: a lehetséges sorrendek száma faktoriálisan robban. Már néhány tucat feladatnál annyi variáció van, hogy a tökéletes terv kimerítő kereséssel kiszámíthatatlan. Ezért a gyakorlatban heurisztikákkal keresünk közel optimális ütemezést.

Mi az a makespan (átfutási idő)?

A makespan a teljes munkahalmaz befejezési ideje: az az időpont, amikor az UTOLSÓ munka is elkészül. Ha több csapat párhuzamosan dolgozik, a makespan a leglassabban elkészülő ág ideje. Az ütemezés célja jellemzően ennek minimalizálása – vagyis hogy az egész projekt minél hamarabb kész legyen, ne csak az egyes munkák külön-külön.

Megéri szoftverrel szervezni a munkákat?

Néhány párhuzamos munkánál a fejben vagy papíron tartott terv is működik. De több csapatnál, több egyszerre futó munkánál és változó határidőknél a kézi követés gyorsan összeomlik: elvész, hogy ki hol tart, mi a lejárt teendő, melyik munka áll megrendelőre várva. Egy munkanapló-rendszer naprakész, megosztható képet ad – és ez a láthatóság az, ami jó ütemezési döntéseket egyáltalán lehetővé tesz.

A JobOptim optimalizálja helyettem az ütemezést?

Nem automatikusan – és ez tudatos. A JobOptim nem egy fekete doboz, amely eldönti helyetted a sorrendet; egy online munkanapló, amely a munkák állapotát, a teendőket, a felelősöket és a határidőket tartja naprakészen és megoszthatóan. A matematika megmondja, mi az elvi optimum; a JobOptim adja a pontos, valós idejű adatot, amire a jó döntést alapozod.

Frissítve: