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
Použijte Johnsonovo pravidlo.
Návrh řešení
FIFOZkusí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ě. LIFOZkusí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ě. Johnsona) 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ílouZa ř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: Je přiložen i zdrojový kód programu: 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. |