Denní rozvrhování, plánování a řízení výroby
Aplikace Johnsonova pravidla
 Tisk

Zadání

Seřaďte optimálně následujících 6 výrobních příkazů (úloh) s požadavky na kapacity pracovišť.


Úloha     Prac1     Prac2

          (hod)     (hod)

------------------------------------

A         5         5

B         4         3

C         8         9

D         2         7

E         6         8

F        12        15




Tipy pro řešení

Použijte Johnsonovo pravidlo.




šipka Návrh řešení

FIFO


Zkusíme nejdříve FIFO řešení ABCDEF:


Prac1 AAAAABBBBCCCCCCCCDDEEEEEEFFFFFFFFFFFF

Prac2      AAAAABBB    CCCCCCCCCDDDDDDDEEEEEEEEFFFFFFFFFFFFFFF

      0123456789012345678901234567890123456789012345678901234567

      0000000000011111111122222222223333333333444444444455555555


Diskuse: Můžeme posunout začátek práce 2. pracoviště, abychom vyloučili prostoj, celkový konec práce je v 56. hodině.


LIFO


Zkusíme nejdříve LIFO řešení FEDCBA:


Prac1 FFFFFFFFFFFFEEEEEEDDCCCCCCCCBBBBAAAAA

Prac2             FFFFFFFFFFFFFFFEEEEEEEEDDDDDDDCCCCCCCCCBBBAAAAA

      01234567890123456789012345678901234567890123456789012345678

      00000000000111111111222222222233333333334444444444555555555


Diskuse: Rozvrh je bez prostojů, na začátku je dlouho nevyužit o pracoviště 1, celkový konec práce je v 59. hodině.


Johnson


a) Vybereme úlohu s nejkratším výrobním časem. Jedná se o úlohu D s časem 2 hodiny.

b) Protože se jedná o čas na prvním pracovišti, rozvrhněme nejprve úlohu D. Vyloučíme D z dalších úvah.

c) Úloha B má nyní nejkratší čas. Protože se jedná o čas na druhém pracovišti, rozvrhněme ji nakonec a vyloučíme B z dalších úvah.


Nalezená posloupnost je nyní: D - - - - B


d) Zbývající úlohy a jejich časy jsou nyní:


Úloha     Prac1     Prac2

             (hod)       (hod)

------------------------------------

A            5           5

C            8           9

E            6           8

F           12         15


Všimněme si nyní nerozhodného stavu v nejkratších časech: úloha A má tentýž čas na pracovišti 1 i 2. Je jedno, zda A umístíme na volné místo od začátku nebo od konce posloupnosti. Rozhodněme náhodně, že nakonec.


e) Nyní máme: D - - - A B



Úloha     Prac1     Prac2

             (hod)       (hod)

------------------------------------

C            8           9

E            6           8

F           12         15


Nejkratší čas je na 6 pro úlohu E na pracovišti 1. Zařadíme ji od začátku.


Nyní máme: D E - - A B


Úloha     Prac1     Prac2

             (hod)       (hod)

------------------------------------

C            8           9

F           12         15


f) C má nejkratší čas ze zbývajících dvou úloh (8 hodin na pracovišti 1). Zařadíme ji od začátku a zbývající úlohu za ni na poslední volné místo.


Nyní máme konečnou posloupnost úloh: D E C F A B


g) Výsledek zobrazíme do časového diagramu:


Prac1 DDEEEEEECCCCCCCCFFFFFFFFFFFFAAAAABBBB

Prac2   DDDDDDDEEEEEEEECCCCCCCCC FFFFFFFFFFFFFFFAAAAABBB

      0123456789012345678901234567890123456789012345678901234567

      0000000000011111111122222222223333333333444444444455555555


Vidíme, že na pracovišti 2 je prostoj ve 26 a 27 hodině. Na pracovišti 2 proto můžeme začít práci na D o 2 hodiny později bez prostoje. Všechny úkoly budou splněny za 51 hodin, pracoviště 1 bude hotovo za 36 hodin.


Výsledek bez prostoje bude:


Prac1 DDEEEEEECCCCCCCCFFFFFFFFFFFFAAAAABBBB

Prac2     DDDDDDDEEEEEEEECCCCCCCCCFFFFFFFFFFFFFFFAAAAABBB

      0123456789012345678901234567890123456789012345678901234567

      0000000000011111111122222222223333333333444444444455555555


Řešení hrubou sílou


Za řešení silovou metodou se považuje prozkoumání všech možností.


V případě sériové linky se dvěma stroji a N úlohami je těchto možností N!. Jedná se o všechny možné permutace z daných úloh.


Výsledky silového řešení jsou v souboru:


Silové řešení rozvrhu


Je přiložen i zdrojový kód programu:


Kód silového řešení


Počet permutací astronomicky roste s počtem úloh (N faktoriál). V případě extrémního nárůstu lze silové řešení nahradit náhodným výběrem určité permutace úkolů. Provedeme tolik výběrů, na kolik máme k dispozici výpočetní čas. Z nich vybereme nejlepší řešení.


Jakou máme šanci, že jsme vybrali dobré řešení?


Jistotu nemáme nikdy.


Co když odhadneme naši šanci na nalezení úspěchu na jedno promile. Pak šance nebýt úspěšný je 999 promile. S každým následujícím pokusem se naše šance zlepšuje.

Obrázek 1. Šance na úspěch



Při tisíci pokusech je šance na chybné řešení ještě 36%, pro desetitisíci pokusech máme velkou naději na úspěch.