Modely rozvrhování produkce s využitím Matlabu
Semestrální práce pro 4EK425 (Modely produkčních systémů) Autor: Jaroslav Zahálka
Obsah Úvod _____________________________________________________________________ 3 Popis produkčního systému____________________________________________________ 3 Matlab a TORSCHE Scheduling Toolbox ________________________________________ 4 Modely s jedním procesorem __________________________________________________ 6 Modely s více procesory ______________________________________________________ 7 Závěr _____________________________________________________________________ 9
Úvod Modely s rozvržením produkce jsou jednou z nejdůležitějších odnoží oblasti optimalizace produkčních systémů. Tato práce má za cíl na úloze jednoduššího charakteru předvést řešení několika problémů z této problematiky a zároveň ilustrovat využití profesionálního softwarového prostředí Matlab a jeho doplňků k tomu určených. Matlab samotný nemá ve své základní instalaci žádné prostředky pro řešení problémů rozvrhování produkce, ale existuje plug-in TORSCHE Scheduling Toolbox, který má ambice tento nedostatek pokrýt. Následující práce tedy nejdříve nastíní řešený problém a pak postupně probere vhodné algoritmy implementované v tomto toolboxu a použitelné pro tuto úlohu.
Popis produkčního systému Produkční systém, pro kterou budeme řešit jednotlivé úlohy, bude automatická linka, na které jsou skládány jednotlivé díly osobních počítačů. Pro naše účely je problém zjednodušen na deset operací, které mohou probíhat nezávisle na sobě. Jedná se o instalace jednotlivých komponent počítače do základní desky a tzv.casu – krycí části základní jednotky počítače.Každá činnost je charakterizována svou dobou trvání ti, termínem nejdříve možného začátku realizace ri a termínem požadovaného dokončení di. Činnosti jsou následující:
1. instalace procesoru – označíme procesor 2. instalace pevného disku – označíme disk 3. instalace pamětového modulu – označíme paměť 4. instalace grafické karty – označíme grafika 5. instalace zvukové karty – označíme zvuk 6. intalace síťové karty – označíme disk 7. instalace chladícího větráku – označíme větrák 8. instalace CD mechaniky – označíme cdrom 9. instalace disketové mechaniky – označíme diskety 10. instalace zdroje – označíme zdroj
Tabulka shrnuje charakteristiky činností (časy jsou v sekundách): procesor 15 0 20
ti ri di
disk 20 15 35
paměť 8 18 52
grafika 10 25 52
zvuk 10 45 60
síť 12 70 80
větrák 20 65 100
cdrom 17 50 90
diskety 17 95 110
zdroj 25 110 120
Matlab a TORSCHE Scheduling Toolbox Matlab je pokročilý výpočetní software, který má vlastní programovací jazyk pro popis řešených problémů a díky kterému je možné vytvářet i tzv. plug-iny – přídavné moduly rozšiřující základní funkcionalitu výchozího programu. Jedním z nepřeberného množství těchto doplňků je právě TORSCHE Scheduling Toolbox zaměřený na úlohy rozvrhování produkce.
Toolbox byl vytvořen na elektrotechnické fakultě ČVUT Praha a přehledný informační web o jeho použití s možností stažení je na adrese http://rtime.felk.cvut.cz/scheduling-toolbox/ . Instalace Matlabu i samotného plug-inu je nenáročná a dobře popsaná, největší problém je s verzí Matlabu, která musí být vyšší než 6.5 (poslední verze jsou 7.3 a vyšší) a hardwarovou náročností programu. Na pomalejších počítačích není použití Matlabu kvůli jeho nárokům na velikost paměti a rychlost procesoru nejpříjemnější.
Po zdárném zavedení toolboxu do systému je umožněn přístup k novým objektům a funkcím, díky kterým je možné definovat a řešit úlohy plánování. Základní příkazy jsou task, taskset, problem, plot a pak jednotlivé algoritmy:
Objekt task představuje reprezentaci jedné činnosti systému, které lze přiřadit charakteristiky jako např. Processing time (doba trvání), Release time (nejdříve možný začátek realizace) a Deadline (požadovaný čas dokončení).
Taskset představuje soubor činností (tedy objektů Task), které tvoří systém a je s nimi nakládáno jako s celkem.
Problem je objekt zastřešující řešenou úlohu a je popsán Grahamovou notací, např. 1|ri|Cmax. Syntaxe je pak např. problem('1,rj,Cmax').
Algoritmy jsou implementovány jako funkce, jejichž parametrem je většinou objekt problem a taskset. Například pro úlohu 1|ri|Cmax se používá funkce alg1rjcmax(taskset,problem).
Příkaz plot se používá k vizualizaci vypočítaného řešení.
Ke všem příkazům lze vypsat nápovědu pokynem help. Vyčerpávající přehled možností systému lze najít na adrese http://rtime.felk.cvut.cz/scheduling-toolbox/manual/ .
Pro představu následuje přehled algoritmů a typů úloh, které lze díky toolboxu řešit: Název Algoritmus pro 1|rj|Cmax Bratleyho algoritmus Hodgsonův algoritmus Algoritmus pro P| |Cmax McNaughtonův algoritmus Algoritmus pro P|rj,prec,~dj | Cmax Huův algoritmus Bruckerův algoritmus Hornův algoritmus Plánování seznamu (List scheduling) Hoffmanův a Grahamův algoritmus Plánování s kladným a záporným časovým zpožděním Cyklické plánování SAT plánování (SAT scheduling)
Příkaz alg1rjcmax bratley1 alg1sumuj1 algpcmax mcnaughtonrule algprjdeadlinepreccmax hu brucker76 horn listsch algorithmcoffmangraham spntl
Problém 1| rj | Cmax | rj,~dj | Cmax | | ΣUj P| |Cmax P|pmtn|Cmax P|rj,prec,~dj|Cmax P|in-tree,pj=1|Cmax P|in-tree,pj=1|Lmax 1|pmtn,rj|Lmax P|prec|Cmax P2|prec,pj=1|Cmax SPNTL
cycsch satsch
CSCH P|prec|Cmax
Definice dané úlohy v Matlabu zjednodušeným zápisem by tedy vypadala následovně:
T=taskset([15 20 8 10 10 12 20 17 17 25]); T.Name={'procesor' 'disk' 'pamet' 'grafika' 'zvuk' 'sit' 'vetrak' 'cdrom' 'diskety' 'zdroj'}; T.ReleaseTime = ([0 15 18 25 45 70 65 50 95 110]); T.Deadline = ([20 35 52 52 60 80 100 90 110 120]);
Na takto zavedený systém můžeme dále aplikovat celou řadu algoritmů a vytvářet jednotlivé rozvrhy optimální podle daných kritérií. Příkazem plot(T) lze zobrazit výchozí rozvržení činností včetně svých časových charakteristik. Šipky ve směru vzhůru zobrazují nejdříve možný začátek činnosti a šipky dolů požadované ukončení realizace. Výsledek zobrazuje následující obrázek.
Modely s jedním procesorem Nejjednodušší úloha je výpočet kritéria Cmax v jednoprocesorovém systému. V našem případě hodnota vychází 154 sekund a daný rozvrh můžete vidět na následujícím obrázku. Úloha byla vyřešena díky funkci alg1rjcmax(T,p), kdy všechny hodnoty rj jsou rovny nule.
Další úlohou je 1|rj| Cmax která se řeší algoritmem řadícím dávky vzestupně podle doby nejdříve možného začátku rj. Řeší se stejnou funkcí jako předchozí úloha - alg1rjcmax(T,p). Cmax je opět 154 sekund.Výsledek zobrazuje následující obrázek.
Modely s více procesory Pokud se bude náš systém skládat z více procesorů, např. bude linka obsluhována více automaty skládajícími díly počítačů, můžeme se zabývat modely s více procesory.
První úlohou je rozdělení dávek v systému se třemi procesory, kde není možné činnosti přerušovat – v Grahamově notaci úloha 3||Cmax. Úloha je definována jako problem('P||Cmax') a řešení je dosaženo algoritmem algpcmax(T,p,3). Algoritmus pro hledání optimálního rozvržení používá metody celočíselného programování.Hodnota kritéria Cmax činí 52 sekund. Obrázek ukazuje optimální řešení:
Obdobným problémem je úloha se dvěma procesory bez přerušení dávek 2||Cmax. Zde vychází optimální Cmax =77 a rozvržení činností na procesory ukazuje opět vygenerovaný obrázek na následující straně.
Úlohu rozdělení dávek na víc procesorů lze upravit o požadavek možného přerušení činností. V případě naší úlohy to asi není nejrozumnější požadavek, ale pro ilustrační účely schopností Matlabu se můžeme tohoto nedopatření dopustit. Nejprve budeme tedy řešit úlohu označenou jako 3|pmtn|Cmax, na kterou byl vyvinut speciální algoritmus známý jako McNaughtonův. Ten je implementován v Matlabu jako funkce mcnaughtonrule() – v našem případě ji tedy použijeme se třemi parametry jako mcnaughtonrule(T,p,3). Kritérium Cmax vychází 51,3 sekund. Prohlédněte si znázornění příslušného optimálního rozvrhu:
Obdobnou úlohou je 2|pmtn|Cmax , která se řeší také Mcnaughtonovým algoritmem a kritérium Cmax pro ní vychází 77 sekund. Na další stránce se opět nachází grafická podoba optimálního rozvrhu.
Závěr V této práci byly popsány základní možnosti využití Matlabu pro řešení úloh rozvrhování produkce s několika ilustračními problémy řešenými algoritmy probíranými v předmětu 4EK425. Použitý plug-in TORSCHE Scheduling Toolbox dokáže řešit i spoustu dalších úloh, zároveň však v současné verzi postrádá schopnost počítat některé základní problémy a určovat hodnoty kritérií. Určitě by však nebyl problém alespoň některé z jednodušších
algoritmů
naimplementovat.
a
postupů
používaných
při
výuce
4EK425
dodatečně
