Erőforrás- és munkaütemezés
InfoMit 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:
- Hozzárendelés (assignment): ki csinálja az adott munkát – melyik brigád melyik feladatot kapja.
- Ü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.
TipA 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.
TipPró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
- Vágásoptimalizálás: anyagspórolás szabászati algoritmusokkal – a másik klasszikus kombinatorikus feladat, a CutOptimmal a gyakorlatban
- Műszakbeosztás optimalizálása – rokon ütemezési probléma: emberek és műszakok hozzárendelése
- Építési napló: hogyan dokumentáld a kivitelezést – a gyakorlati oldal a Házépítési Kalauzon
- Árrés és haszonkulcs kalkulátor – egy munka nyereségének becsléséhez
- Százalékszámítás kalkulátor – a kihasználtság és a csúszás arányának számításához
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.