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.
Mennyire függ az első hely a késési súlytól?
A feldolgozási idők és határidők maradjanak változatlanok, de A súlyát most jelölje egy pozitív x pont/perc érték. A–B–C sorrendnél továbbra is csak B késik húsz percet, ezért az összpont 20. B–A–C sorrendnél A tízpercnyi késése 10x pont.
A két sorrend egyenlősége 20 = 10x, vagyis x = 2. Ha A súlya 1, B–A–C tíz pontot ad, és jobb az A–B–C húsz pontjánál. Kettes súlynál a két sorrend egyaránt húsz pont. A korábbi négyes súlynál A–B–C vezet húsz ponttal, B–A–C negyvennel követi.
A teljes hatos felsorolásból a többi sorrend képlete is ellenőrizhető:
| Sorrend | Súlyozott késési pont |
|---|---|
| A–B–C | 20 |
| A–C–B | 40 |
| B–A–C | 10x |
| B–C–A | 30x |
| C–A–B | 20x + 40 |
| C–B–A | 30x + 10 |
Pozitív x mellett a többi négy sor nem ad kisebb értéket, mint a két összehasonlított jelölt minimuma. Ezért a kettes küszöb a teljes, változatlan háromfeladatos modellre is érvényes. A pontosan nulla súly külön határeset volna, mert akkor további döntetlen is kialakulhat.
Ha viszont A 30. perces határideje kötelező korlát, a késését nem lehet ponttal kiváltani. Ebben az új feltételben A-nak elsőként kell elkészülnie; az A–B–C és A–C–B közül a húszpontos A–B–C jobb. Az ütemezés korlátait és célját külön kezelő leírás alapján ezért a súly és a kötelező határidő két külön mezőként szerepeljen a tervben.
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.
Záró tudáspróba
Válassz kérdésenként egy választ. A megoldások ellenőrzése után minden helyes válaszért 1 pontot adj magadnak; a hibás, kihagyott vagy több válasszal megjelölt kérdés 0 pont. Összesen 0–3 pont szerezhető.
1. Az eredeti A-súly négy pont/perc. Melyik sorrend ad kisebb súlyozott késést: A–B–C vagy B–A–C?
- A) B–A–C, mert B határideje korábbi.
- B) Mindkettő, mert a teljes idő 60 perc.
- C) A–B–C, húsz ponttal a negyven helyett.
2. Mekkora pozitív A-súlynál egyenlő a két fő sorrend pontja?
- A) 2 pont/perc.
- B) 4 pont/perc.
- C) 20 pont/perc.
3. A 30. perces befejezése kötelező. Megengedett a 40. percben befejeződő A egy nagyon kis késési súllyal?
- A) Igen, mert a kis súly feloldja a határidőt.
- B) Nem, a kötelező feltételt a pontozástól külön kell teljesíteni.
- C) Igen, ha C korábban elkészül.
Megoldások és pontszám
1. C. A–B–C-ben B húszperces, egyes súlyú késése számít. B–A–C-ben A tízperces késését négyszeresen súlyozzuk.
2. A. A–B–C pontja 20, B–A–C pontja 10x. A 20 = 10x egyenletből x = 2.
3. B. A kötelező határidő megengedhetőségi feltétel. Más feladat korai elkészülése vagy kisebb pontsúly nem teljesíti helyette.
3 pont: A súly érzékenységét és a kötelező feltételt is külön kezelted. Saját feladataidnál ellenőrizd, mely határidő puha pontozási tétel és melyik meg nem sérthető korlát.
2 pont: Az 1. kérdéshez a húsz és negyven pont eredetét, a 2.-hoz a 20 = 10x egyenletet, a 3.-hoz A kötelező határidejét nézd át.
0–1 pont: Írd fel minden sorrendben a befejezést és a pozitív késést. Ezeket szorozd a súlyokkal, miközben a kötelező feltételeket külön igen/nem ellenőrzéssel vizsgálod.