Egyetlen gépen három munka vár feldolgozásra. Ha minden munka ugyanabban a pillanatban rendelkezésre áll, és nincs átállási idő, a teljes befejezési idő minden sorrendben azonos lehet. A határidők és a késések következménye miatt mégis számít, melyik feladat kerül előre.
A következő saját példa a súlyozott késési pontot minimalizálja. Ez egy megnevezett tervezési cél, nem általános szabály minden gyártásra. A munkák nem szakíthatók meg, nincs párhuzamos gép, előzményfeltétel vagy szünet; az időt az indulástól számított percben mérjük.
Írd fel a három munka adatait
Az A munka feldolgozása 30 perc, határideje a 30. perc, késési súlya 4 pont/perc. A B munka 10 percig tart, határideje a 20. perc, késési súlya 1 pont/perc. A C munka 20 perces, határideje a 70. perc, súlya 1 pont/perc.
Késésként csak a határidőn túli befejezést számítjuk: max(0, befejezés − határidő). A korai elkészülés nem ad negatív büntetést és nem törli el másik munka késését. A feladat pontja a késési percek és a hozzá tartozó súly szorzata.
A teljes feldolgozási idő 30 + 10 + 20 = 60 perc. Ezt mindegyik megszakítás nélküli, üresjárat nélküli sorrendnél megkapjuk. A keresett különbség a munkánkénti befejezésből adódik.
Két kézenfekvő sorrend összehasonlítása
Határidő szerint először B, utána A, végül C következne. A befejezési idők 10, 40 és 60 perc. B időben elkészül, A tíz percet késik, C időben végez. A súlyozott késési pont 10 × 4 = 40.
Ha először A, utána B, majd C készül, a befejezések 30, 40 és 60 perc. A pontosan határidőre kész, B húsz percet késik, C időben végez. Az összes pont 20 × 1 = 20.
A második sorrendben több a késési perc, mégis kisebb a választott súlyozott büntetés. Ezért a „legkevesebb késési perc” és a „legkisebb súlyozott késés” célját külön kell megnevezni.
Három munkánál mind a hat sorrend ellenőrizhető
Az A–B–C sorrend 20 pontot ad. Az A–C–B és B–A–C egyaránt 40 pontot. A B–C–A és C–A–B 120 ponttal jár, míg a C–B–A 130 pontot eredményez.
Így a hat lehetséges sorrend között az A–B–C az egyértelműen legjobb a saját célfüggvényünk szerint. Ez a kicsi modell teljes felsorolásával igazolt eredmény. Több gépre, átállásokra vagy közben érkező munkákra változtatás nélkül nem vihető át.
A Google ütemezési dokumentációja megkülönbözteti a műveleti korlátokat és az optimalizálási célt. A fenti egységes gépes, súlyozott késési példa saját levezetés; nem a dokumentáció mintafeladatának átvétele.
A tervezőt ugyanazzal a céllal értékeld
A gyártási sorrend tervezőben a ténylegesen elérhető idő- és sorrendbeállításokat használd. Ne nevezd egy eszköz által ajánlott sorrendet a fenti pontfüggvény optimumának, ha az eszköz más célt vagy heurisztikát követ.
A saját ellenőrző táblában munkánként őrizd meg az indulást, a befejezést, a határidőt, a pozitív késést és a súlyt. Ha a pontokat forintra szeretnéd fordítani, ahhoz igazolt üzleti költségfüggvény kell. Az itt választott 4 és 1 súly szemléltető tervezési feltétel.
Gyakori kérdések
A legrövidebb munka előrevétele mindig jó megoldás?
Más mutatót javíthat, de a súlyozott késésre nem általános garancia. A célfüggvényt és a korlátokat előre rögzíteni kell.
Miért ugyanaz mindegyik sorrend teljes ideje?
A példában nincs üresjárat, átállás vagy megszakítás. Ugyanazt a három feldolgozási időt adjuk össze; a munkánkénti határidő-teljesítés változik.
Három helyett ötven munkánál is soroljak fel mindent?
A sorrendek száma rendkívül gyorsan nő. Nagyobb feladatnál megfelelő ütemezési módszer és ellenőrizhető korlátkezelés szükséges.