Aplikácia fuzzy dispečerských prioritných pravidiel

09. Máj, 2011, Autor článku: Ladovský Tomáš, Informačné technológie
Ročník 4, číslo 5 Pridať príspevok

Článok sa venuje problému rozvrhovania úloh identickým paralelným strojom pomocou konštrukčnej heuristiky, známej pod názvom dispečérske prioritné pravidlá, pričom optimalizačným kritériom je zrovnomernenie pracovného zaťaženia strojov. Technika dispečerských prioritných pravidiel patrí medzi prvé techniky, ktoré boli použité na riešenie problému identických paralelných strojov.

Princíp dispečerských prioritných pravidiel spočíva v pridelení priority nerozvrhnutým úlohám a následnom vytváraní rozvrhu postupne od úlohy s najväčšou prioritou po úlohu s najmenšou prioritou. Prioritu prideľujeme úlohám vzhľadom na ich dobu spracovania, pričom časy spracovania jednotlivých úloh sú neisté a modelované pomocou fuzzy trojuholníkových čísel. Pre pridelenie priority potrebujeme vedieť porovnať medzi sebou jednotlivé časy spracovania, čo sa u fuzzy čísel nedá urobiť jednoznačne (kvôli neistote).

Výsledok rozvrhovacieho problému je preto ovplyvnený rozhodnutím voľby metódy porovnania. Najskôr teda preskúmame a porovnáme metódy porovnania fuzzy trojuholníkových čísel a následne ich použijeme v dispečérskych prioritných pravidlách, ktoré aplikujeme na problém rozvrhovania úloh identickým paralelným strojom.

1. Úvod

Problém umiestnenia/priradenia úloh identickým paralelným strojom môžeme formulovať nasledujúco: Máme priradiť $n$ úloh na $m$ identických strojov tak, aby sme neporušili obmedzenia a optimalizovali zadané optimalizačné kritéria. Platí, že $m<<n[/latex]. V našom prípade je optimalizačným kritériom miera nerovnomernosti. Čím je táto miera nerovnomernosti menšia, tým je záťaž strojov rovnomernejšia. <p align="justify">Podľa Graham a kol. [8] klasifikujeme takýto systém ako <img src='http://s0.wp.com/latex.php?latex&bg=ffffff&fg=000000&s=0' alt='' title='' class='latex' />P_m,||f$ , kde $P$ predstavuje identické paralelné stroje, $m$ je počet strojov a $f$ je miera nerovnomernosti. Je dokázané, že minimalizácia času skončenia poslednej úlohy $f = C_{max}$ , čo sa dá taktiež formulovať ako minimalizácia maximálneho zaťaženia [20], vedie k zrovnomerňovaniu pracovnej záťaže. Takýto systém môžeme klasifikovať ako $P_m||C_{max}$ a ide o jeden z najviac študovaných systémov v literatúre. V článku ale používame na určenie miery rovnomernosti rozvrhu inú funkciu.

Garey a Johnson 1979 [6] ukázali, že problém rozvrhovania úloh identickým paralelným strojom je pre $m\geq 2$ $NP$ -ťažký. Z tohoto dôvodu prehľadávanie hrubou silou, dynamické programovanie, celočíselné programovanie a metóda vetiev a hraníc sa používajú na získanie optimálneho riešenia len pre malé a stredne veľké inštancie problému. Pre veľké inštancie sú nepoužiteľné.

Doposiaľ sa nenašiel efektívny polynomiálny algoritmus s optimálnym riešením a to viedlo veľa výskumníkov k vytváraní heuristík. Aj keď heuristiky negarantujú nájdenie optimálneho riešenia, tak poskytujú približné (aproximačné) riešenia, ktoré sú skoro tak dobré ako optimálne riešenia. Tieto je možné rozdeliť zhruba na zlepšujúce heuristiky a konštruktívne heuristiky. Do prvej kategórie patria algoritmy založené na lokálnom prehľadávaní okolia prípustného riešenia. Aplikácie takýchto algoritmov na riešenie problému $P_m||C_{max}$ môžeme nájsť v ([2],[1],[5])

Väčšina algoritmov patriacich do druhej kategórie majú známe pomery najhoršieho riešenia, získaného heuristikou, k optimálnemu riešeniu (worst case performance ratio). Medzi ne patria aj dispečerské prioritné pravidlá. Dispečérske pravidlo LPT (longet processing time first) bolo prvý krát predstavené Grahamom [7] v roku 1969. Toto dispečérske pravidlo sa stalo kritériom pri navrhovaní efektívnych algoritmov. Je známe, že zrovnomerňuje jednotlivé výkony strojov. Zrovnomerňovanie spôsobuje ponechanie najmenších časov spracovania na koniec rozvrhovania.

Ľudský faktor, výrobné chyby alebo výskyt porúch zapríčiňujú, že časy spracovania sú neistého charakteru. Takéto neisté časy spracovania môžeme modelovať pomocou fuzzy čísel. Pre porovnanie fuzzy čísel neexistuje univerzálna metóda, pomocou ktorej by sme ich vedeli porovnať a zoradiť. Veľa dispečérskych pravidiel prideľuje prioritu úlohám na základe relácie usporiadania časov spracovania úloh. Prideľovanie priority vyžaduje reláciu lineárneho usporiadania, ktorá pre fuzzy čísla nie je lineárne usporiadaná.

Pojem fuzzy množiny bol prvý krát predstavený americkým expertom na automatizáciu L. A. Zadehom [22] a pojem fuzzy čísla predstavili Jain [9] a Dubois a Prade [3]. Výskum porovnania fuzzy čísel je jednou z veľmi dôležitých tém teórie fuzzy množín a aplikuje sa na všetky oblasti rozhodovania. Napríklad poňatie optimality alebo najlepšieho výberu je kompletne založené na porovnaní (poradí). Fuzzy čísla nevieme ľahko usporiadať v poradí ich veľkosti, pretože predstavujú neisté a neurčité hodnoty, ktoré vyjadrujeme možnostnými rozdeleniami a môžu sa navzájom prekrývať. Ak sa dve fuzzy čísla prekrývajú, potom ich nemožno považovať za absolútne usporiadateľné [11]. To znamená, že jedenkrát môžeme považovať fuzzy číslo za väčšie ako ostatné, no pri inej metóde porovnania ho môžeme považovať za menšie ako ostatné. Dôsledkom je, že aj keď uvažujeme iba dve fuzzy čísla, potom výsledkom ich porovnanie sú dve postupnosti poradia v danom čase.

Ak usporiadame fuzzy čísla z obrázka 1a podľa ťažiska, Yager [21], tak získame výstupnú postupnosť $A_2, A_1,$ $A_3, A_4$ , kde $A_2$ je najmenšie a $A_4$ najväčšie fuzzy číslo. U fuzzy čísel $A_2$ a $A_4$ je ihneď jasné, že fuzzy číslo $A_4$ je absolútne väčšie ako $A_2$ . Ak sa ale fuzzy čísla navzájom prekrývajú, potom ich nemôžeme považovať za absolútne usporiadateľné. Napríklad, fuzzy čísla $A_1$ a $A_3$ sa navzájom prekrývajú a tak nemôžeme považovať fuzzy číslo $A_3$ za absolútne väčšie ako $A_1$ . Stále totiž existuje možnosť, že $A_1$ je väčšie ako $A_3$ .

Veľké množstvo prioritných pravidiel je založené na porovnaní čísel. Článok prezentuje problém prideľovania úloh paralelným strojom, ktorých časy spracovania sú modelované pomocou trojuholníkových fuzzy čísel, ktoré sú vytvorené na základe štatistického súboru (tréningových dát) a snažíme sa nimi popísať očakávané časy spracovania úloh.

Na porovnanie fuzzy hodnôt neexistuje univerzálna metóda, tak ako sme zvyknutí u reálnych čísel. V dnešnej dobe existuje veľké množstvo metód, pomocou ktorých sme schopní porovnať fuzzy čísla. Rozdielne prístupy porovnania fuzzy čísel môžeme podľa Nasseriho [14] a Ramliho [18] kategorizovať do štyroch hlavných tried: relácie preferencie, posibilitné¹ rozdelenia fuzzy priemeru a rozptylu, fuzzy bodovanie a lingvistické vyjadrovanie. My sa zameriame na centroidné metódy, ktoré patria do skupiny fuzzy bodovania. K týmto skupinám pridáme lexikografický a agregačný prístup porovnania fuzzy trojuholníkových čísel.

Cieľom článku je prezentovanie metód porovnania fuzzy čísel, dispečérskych prioritných pravidiel a ich aplikovania na riešenie problému prideľovania úloh paralélnym strojom. Taktiež nás zaujíma vplyv výberu metódy porovnania na optimalitu riešenia (rovnomernosť) a vplyv výberu dispečérskeho prioritného pravidla na rovnomernosť rozvrhu. Nasledujúca sekcia definuje pojem fuzzy čísla.

2. Fuzzy čísla

Nech $\mathfrak R$ je množina reálnych čísel. Fuzzy množinu $A$ definujeme na $\mathfrak R$ pomocou funkcie príslušnosti $\mu_A:\mathfrak R\rightarrow [0,1]$ , kde $\mu_A(x)$ predstavuje stupeň príslušnosti elementu $x$ vo fuzzy množine $A$ . Fuzzy podmnožina $A$ definovaná na $\mathfrak R$ je normálna, ak a iba ak

$H(A) = \sup_{x\in \mathfrak R}\{\mu_A(x)\} = 1$

kde $H(A)$ je výška fuzzy množiny $A$ . Fuzzy podmnožina $A$ množiny $\mathfrak R$ je konvexná, ak a iba ak

$\mu_A(\lambda x+(1-\lambda)y)\geq\min\{\mu_A(x),\mu_A(y)\}$

kde $x,y\in\mathfrak R$ a $\lambda\in [0,1]$ . Nosič množiny $A$ je definovaný ako

$S(A) = \{x\,|\, \mu_A(x) > 0\}.$

Fuzzy množinu $A$ sa nazýva fuzzy číslo, ak a iba ak $A$ je normálna, konvexná a nosič množiny $A$ je ohraničený na $\mathfrak R$ . Trojuholníkové fuzzy číslo $A$ je fuzzy číslom so spojitou lineárnou funkciou príslušnosti $\mu_A(x)$ definovanou ako:

$\mu_A(x) = \left\{ \begin{array}{ccc} \mathcal L_A(x) = (x-a)/(b-a) & \text{pre} & a\leq x\leq b \\ \mathcal R_A(x) = (c-x)/(c-b) & \text{pre} & b\leq x\leq c \\ 0 & \text{inak} & \end{array} \right.$

kde $\mathcal L_A:[a,b]\rightarrow [0,1]$ je striktne rastúca funkcia a $\mathcal R_A:[b,c]\rightarrow [0,1]$ je striktne klesajúca funkcia. V nasledujúcom texte používame namiesto pojmu trojuholníkové fuzzy číslo skrátený tvar fuzzy číslo. Fuzzy číslo môžeme taktiež značiť ako usporiadanú trojicu $A = (a,b,c)$ , kde $a\leq b\leq c$ a $a,b,c\in\mathfrak R$ . Hodnota $a$ je nazývaná infimom, $b$ je nazývaná modusom a $c$ je nazývaná suprémom.

Taktiež sa používajú označenia pre $a$ ako ľavá hodnota, spodná hodnota, pre $b$ sa používajú označenia ako centrálna hodnota, stredná hodnota a pre $c$ sa používajú označenia ako pravá hodnota, horná hodnota. V nasledujúcom texte sa obmedzíme na také trojuholníkové fuzzy čísla, ktorých hodnoty usporiadanej trojice sa nerovnajú. Definujme množinu všetkých fuzzy čísel s prirodzenými hodnotami $a,b,c$ ako

$\mathcal H(N) = \{(a,b,c)\,|\,a < b < c,\, a,b,c\in N_0\}[/latex]</td> <td style="width:20px; text-align:center;"></td> </tr> </table> <p align="justify">Inverzné funkcie <img src='http://s0.wp.com/latex.php?latex&bg=ffffff&fg=000000&s=0' alt='' title='' class='latex' />\mathcal L^{-1}_A:[0,1]\rightarrow [a,b]$ a $\mathcal R^{-1}_A:[0,1]\rightarrow [b,c]$ k funkciám $\mathcal L_A$ a $\mathcal R_A$ definujeme (viď. obrázok 1b) pre fuzzy číslo $A$ ako

$\mathcal L^{-1}_A(y) = a+(b-a)y\quad\text{a}\quad\mathcal R^{-1}_A(y) = c + (b - c)y$

kde $y\in[0,1]$ Označme reálny interval $A_\alpha$ ako $\alpha$ -rez fuzzy množiny $A$ a definujme ho ako

$A_\alpha = [a^L_\alpha,a^R_\alpha] = [\mathcal L^{-1}_A(\alpha), \mathcal R^{-1}_A(\alpha)] =[a+(b-a)\alpha,c+(b-c)\alpha]$

Nech $m(A_\alpha)$ je centrálna hodnota elementov $\alpha$ -rezu, ktorú pre fuzzy číslo $A = (a,b,c)$ spočítame ako

$m(A_\alpha) = m[a^L_\alpha,a^R_\alpha] = ((2b-a-c)\alpha + (a+c))/2$

kde $\alpha\in[0,1]$ . Nech $A$ je ľubovoľné fuzzy číslo $A = (a,b,c)$ , potom obsah plochy $a(A)$ pod grafom $m(A_\alpha)$ (viď. obrázok 2a) spočítame pre $\alpha\in[0,1]$ ako

$a(A) = \int_0^1 m[a^L_\alpha,a^R_\alpha]\,d\alpha = (a+2b+c)/4$

Fig.1 Na ľavom obrázku (a) sú zobrazené štyri fuzzy čísla, na ktorých demonštrujeme problém ich porovnania. Fuzzy čísla $A_2$ a $A_3$ sa s fuzzy číslom $A_4$ neprekrývajú, preto vieme ľahko povedať, že $A_2$ a $A_3$ sú menšie ako $A_4$ . Ako je to ale s fuzzy číslami $A_1$ a $A_3$ . Tieto dve fuzzy čísla sa prekrývajú. Pre $\alpha$ -rezy oboch fuzzy čísel platí, že ${A_3}_\alpha$ je podmnožinou ${A_1}_\alpha$ , pre $\alpha\in[0,0.23)$ . To znamená, že pri pesimistickej optimalizácií, kde preferujeme väčšiu šírku intervalu ${A_1}_\alpha$ pred menšou ${A_3}_\alpha$ , zvolíme za väčšie fuzzy číslo $A_1$ a to pre hladiny $\alpha\in[0,0.23)$ . Pre hladiny $\alpha\in[0.23, 0.6)$ nastáva nejasná situácia, ktorý $\alpha$ -rez je väčší a ktorý menší, aj keď pravá hodnota intervalu ${A_3}_\alpha$ je väčší ako pravá hodnota intervalu ${A_1}_\alpha$ . Nakoniec pre hladiny $\alpha\in[0.6, 1]$ sa intervaly ${A_1}_\alpha$ a ${A_3}_\alpha$ neprekrývajú. Alfa rez ${A_3}_\alpha$ je väčší ako ${A_1}_\alpha$ , a to z toho dôvodu, že ľavá hodnota ${A_3}_\alpha$ je väčšia ako pravá hodnota ${A_1}_\alpha$ . Na pravom obrázku (b) je zobrazená inverzná funkcia členstva fuzzy trojuholníkového fuzzy čísla

Strednú hodnotu fuzzy čísla $A$ spočítame ako

$m(A) = (a+b+c)/3$

a smerodajnú odchýlku fuzzy čísla $A$ spočítame ako

$s(A) = \sqrt{a^2+b^2+c^2-ab-bc-ac}/(3\sqrt{2})$

Ukážku strednej hodnoty a smerodajnej odchýlky fuzzy čísla $A$ môžeme vidieť na obrázku 2b.

Na ľavom obrázku (a) môžeme vidieť obsah oblasti ohraničenej funkciou $m(A_\alpha)$ a $x$ -ovou osou. Pravý obrázok (b) zobrazuje strednú hodnotu a smerodajnú odchýlku fuzzy čúsla $A$

Nasledujúca sekcia definuje niekoľko metód porovnania fuzzy trojuholníkových čísel.

3. Metódy porovnania fuzzy čísel

Nech $\mathcal H(N)$ je množina všetkých fuzzy čísel definovaných na množine reálnych čísel $\mathfrak R$ a $A,B\in\mathcal H(N)$ . Nasledujúci text porovnáva fuzzy čísla pomocou funkcie $F: \mathcal H(N)\rightarrow\mathfrak R$ , ktorú nazývame porovnávacia funkcia alebo index porovnania (angl. ranking function, ranking index). Ak platí $F(A)\leq F(B)$ , potom $A\leq B$ a znamená to, že fuzzy číslo $A$ je menšie alebo rovné ako $B$ vzhľadom na zvolenú funkciu porovnania. Výsledky optimalizačného problému sú závislé na správnej voľbe funkcie porovnania a to vzhľadom na preferenciu riešiteľa, ktoré môžu byť známe pred začatím procesu optimalizácie (apriórne techniky), v priebehu procesu optimalizácie (interaktívne techniky) alebo až po skončení optimalizácie (aposteriórne techniky). Medzi apriórne techniky patrí lexikografický a agregačný prístup.

Yager v roku 1980 [21] navrhol, že väčšie z dvoch fuzzy čísel je to, ktoré má väčšiu hodnotu

$F^{(1)}(A) = m(A)$

Na Yagerov index sa ešte pozrieme detailnejšie neskôr a to z toho dôvodu, že sa tento index stal základom novej vetvy metód porovnania fuzzy čísel (centroidné metódy). Väčšie fuzzy číslo má väčšiu hodnotu $F^{(1)}(A)$ . Bector a Chandra použili na porovnanie dvoch fuzzy čísel funkciu porovnania

$F^{(2)}(A) = a(A)$

Väčšie fuzzy číslo má väčšiu hodnotu $F^{(2)}(A)$ . Ak porovnávame fuzzy čísla iba na základe jednej hodnoty (porovnávacia funkcia, index), tak potom dochádza k určitej strate informácie alebo index porovnania považuje veľkú množinu rôznych fuzzy čísel za rovnaké. Preto sa používajú viackriteriálne optimalizačné techniky ako lexikografický prístup a agregačný prístup. V lexikografickom prístupe sa rozhoduje podľa viacerých kritérií. McCahon a Lee [12] stanovili dve kritéria

$F^{(3)}_1(A) = m(A),\quad\text{a}\quad F^{(3)}_2(A) = s(A).$

Väčšie z dvoch fuzzy čísiel je to, ktoré má väčšiu strednú hodnotu $F^{(3)}_1$ , v prípade zhody stredných hodnôt je väčšie to s väčšou smerodajnou odchýlkou $F^{(3)}_2$ . Sakawa a Kubota [19] použili pre porovnanie fuzzy čísiel $A = (a,b,c)$ tri kritéria.

$F^{(4)}_1(A) = a(A),\quad\text{a}\quad F^{(4)}_2(A) = b,\quad\text{a}\quad F^{(4)}_3(A) = c - a.$

Väčšie z dvoch fuzzy čísiel je to, ktoré má väčšiu hodnotu $F^{(4)}_1$ , v prípade zhody hodnôt $F^{(4)}_1$ je väčšie to s väčšou modálnou hodnotou $F^{(4)}_2$ a v prípade zhody hodnôt $F^{(4)}_2$ je väčšie to s väčším nosičom $F^{(4)}_3$ . Podľa Dvořáka [4] môžeme zoradiť fuzzy čísla jednoducho podľa troch jeho charakteristických hodnôt

$F^{(5)}_1(A) = c,\quad\text{a}\quad F^{(5)}_2(A) = b,\quad\text{a}\quad F^{(5)}_3(A) = a$

O zoradení fuzzy čísel rozhoduje prvé kritérium, v prípade ich rovnosti druhé a v prípade aj ich rovnosti rozhoduje o zoradení fuzzy čísiel tretie kritérium. Nedostatkom lexikografického prístupu je dominancia prvého kritéria. Napríklad, $A$ a $B$ sú fuzzy čísla a platí $m(B) = m(A)+\epsilon$ , kde $\epsilon$ je malé kladné číslo a $s(B)<<s(A)[/latex], potom fuzzy číslo [latex]A[/latex] je podľa McCahonho kritéria vyhodnotené ako menšie než [latex]B[/latex]. Tento nedostatok môžeme odstrániť spojením dielčich kritérií do jedného celkového kritéria. Agregačným prístupom skladáme z viacerých dielčich kritérií celkové kritérium a to na základe sčítania dielčich kritérií s použitím nezáporných váhových koeficientov [latex]w\geq 0[/latex]. Na základe McCahonho kritéria môžeme napríklad navrhnúť kritérium kombinujúce strednú hodnotu a smerodajnú odchýlku ako <table style="width:100%;"> <tr> <td style="text-align:center;"><img src='http://s0.wp.com/latex.php?latex&bg=ffffff&fg=000000&s=0' alt='' title='' class='latex' />F^{(6)}(A) = w_1m(A) + w_2s(A)$

kde $w_1,w_2\geq 0$ .

Iný spôsob porovnania fuzzy čísel je založený na vypočítaní súradníc ťažiska $T = (\hat{x},\hat{y})$ a porovnaní fuzzy čísel vzhľadom na hodnoty $\hat{x}, \hat{y}$ alebo vzdialenosti ťažísk $T$ od počiatku súradnicovej sústavy $(0,0)$ . Taktiež existujú rôzne modifikácie tejto metódy, ktorá sa označuje ako metóda porovnania indexov ťažiska alebo jednoducho ako centroidné metódy porovnania fuzzy čísel (angl. centroid index ranking methods).

Ako prvý prispel do metód porovnania fuzzy čísel s pojmom index ťažiska Yager v roku 1980 [21]. Vypočítal horizontálnu pozíciu ťažiska $\hat{x}_A$ fuzzy čísla $A$ a túto hodnotu použil ako index porovnania. Túto hodnotu spočítame ako

$\hat{x}_A = \frac{\int_{x}w(x)\mu_A(x)\,dx}{\int_{x}\mu_A(x)\,dx}$

kde $w(x)$ predstavuje funkciu váh významu hodnoty $x$ . Pre $w(x)=x$ sa horizontálna súradnica ťažiska $T(A) = (\hat{x}_A,0)$ stáva ťažiskom (COG). Čím je index $\hat{x}_A$ väčší, tým je fuzzy číslo $A$ hodnotené ako väčšie. Pre $w(x)=x$ definujeme Yagerov index ako

$F^{(1)}(A) = \hat{x}_A = m(A)$

Murakami a kol. v roku 1983 prezentovali horizontálne a vertikálne súradnice bodu ťažiska. Horizontálna súradnica $\hat{x}_A$ je rovnaká ako pri Yagerovi. Čím je index $\hat{x}_A$ a/alebo $\hat{y}_A$ väčší, tým je fuzzy číslo $A$ väčšie. Podľa Bortolan a Degani (1985) je logická iba voľba horizontálnej súradnice, pretože vertikálna hodnota je rovnaká pre všetky normálne trojuholníkové fuzzy čísla $(\hat{y}=1/3)$ . Teda podľa Murakamiovho indexu sa na súradnicu $\hat{x}$ pozeráme ako na hlavný index a na súradnicu $\hat{y}$ pozeráme ako na pomocný index. Cheng v roku 1998 navrhol index vzdialenosti, ktorý je založený na oboch súradniciach ťažiska a môžeme ho definovať ako

$F^{(7)}(A) = \sqrt{{\hat{x}_A}^2 + {\hat{y}_A}^2}$

Horizontálna súradnica $\hat{x}_A$ je totožná s Yagerom a Murakamiom a pre fuzzy číslo $A = (a,b,c)$ je vertikálna súradnica $\hat{y}_A$ rovná

$\hat{y}_A = \frac{(a+4b+c)}{3(a+2b+c)}$

Pôvodná Chengova metóda je špecializovaná pre porovnanie lichobežníkových fuzzy čísel, ale môže byť taktiež aplikovaná na všeobecné fuzzy čísla, pokiaľ je ľavá a pravá funkcia príslušnosti invertabilná. Nevýhodou metódy je, že nevie porovnávať negatívne fuzzy čísla. Chu a Tsao navrhol v roku 2002 ako index porovnania plochu medzi bodom ťažiska $T_A = (\hat{x}_A,\hat{y}_A)$ a stredom súradnicovej sústavy $(0,0)$ , ktorú definoval ako

$F^{(8)}(A) = \hat{x}_A\hat{y}_A$

kde $\hat{x}_A$ a $\hat{y}_A$ je totožné s Chengom. Väčšia plocha reprezentuje väčšie fuzzy číslo. Chen a Chen v roku 2003 zistili, že Chengová (1998), Murakamiová a kol. (1983) a Yagerová (1980) metóda nevie v určitých situáciách porovnať rozdielne fuzzy čísla a taktiež nevedia spočítať poradie pre ostré hodnoty. Z tohoto dôvodu Chen a Chen odvodili novú metódu, založenú na súradniciach ťažiska $T=(\hat{x},\hat{y})$ a smerodajnej odchýlke $s(A)$ . Chen a Chenov index porovnania pre fuzzy čísla $A=(a,b,c)$ je definované ako

$F^{(9)}(A) = \hat{x}_A + (1-\hat{y}_A)^{s(A)}$

kde horizontálna súradnica je rovná hodnote

$\hat{x}_A=(2b\hat{y}_A+(c+a)(1-\hat{y}_A))/2$

a vertikálna súradnica je buď rovná hodnote
$\hat{y}_A = 1/3$ ak $a\neq c$ alebo $\hat{y}_A = 1/2$ ak $a = c$ . Čím je hodnota $F^{(9)}(A)$ väčšia, tým je fuzzy číslo väčšie. Pôvodná Chen a Chenová metóda je špecializovaná pre porovnanie zovšeobecnených lichobežníkových fuzzy čísel. Liang a kol. predstavili v roku 2006 dva indexy a to index vzdialenosti, ktorý je podobný k Chengovmu indexu vzdialenosti a RV index. Horizontálna súradnica je rovnaká ako u Chenga a vertikálna súradnica je rovná hodnote $\hat{y}_A = 1/3$ . RV index definujeme ako

$F^{(10)}_1(A) = \sqrt{{\hat{x}_A}^2 + {\hat{y}_A}^2}\quad\text{a}\quad F^{(10)}_2(A) = \frac{\sigma(A)_R}{R}$

kde $R$ je index vzdialenosti a pre fuzzy číslo $A = (a,b,c)$ platí

$\sigma(A)_R=\sqrt{\sigma_x(A)^2 + \sigma_y(A)^2}$

kde

$\sigma_x(A) = s(A)\quad\text{a}\quad\sigma_y(A) = \frac{\sqrt{2(c-a)^2}}{6(c-a)}$

Pre index vzdialenosti platí, že čím je väčší, tým je fuzzy číslo väčšie a pre RV index platí, že čím je menší, tým je fuzzy číslo väčšie. Navyše Liang a kol. ukázali ako voliť hlavný a pomocný index. Pre fuzzy čísla, ktoré sú obe normálne je potreba voliť RV index ako hlavný index a index vzdialenosti ako pomocný index. Túto metódu môžeme zaradiť ako medzi centroidné metódy, tak aj medzi lexikografické metódy. asledujúca sekcia formuluje dispečerské prioritné pravidlá a popisuje algoritmické kroky dispečérskych prioritných pravidiel RPT, SPT a LPT.

4. Dispečerské prioritné pravidlá

Technika dispečerských prioritných pravidiel² bola jedna z prvých techník, ktorá sa použila na riešenie problému identických paralelných strojov. Jej výhody spočívajú v ľahkej implementácií a v polynomiálnom čase riešenia úlohy. Princíp metódy spočíva v tom, že v každom kroku pridelíme nerozvrhnutým operáciám prioritu a operácia s najväčšou prioritou sa pridá do rozvrhu. O dispečerských prioritných pravidlách pojednávajú napr. Pinedo [17], Palúch [15] a Mičunek [13]. Najznámejšími prioritnými dispečerskými pravidlami, ktoré sa používajú na prideľovanie úloh k identickým paralélnym strojom, sú:

Pravidlo	Popis dispečerského pravidla
RPT	(random processing time first) priorita je úlohám pridelená náhodne;
LPT	(longest processing time first) úloha s väčším časom spracovania má väčšiu prioritou;
WLPT	(weighted longest processing time first) úloha s váženým väčším časom spracovania má väčšiu prioritou;
LRPT	(largest remaining processing time first) úloha so zostávajúcim väčším časom spracovania má väčšiu prioritu;
SPT	(shortest processing time first) úloha s menším časom spracovania má väčšiu prioritou;
WSPT	(weighted shortest processing time first) úloha s váženým menším časom spracovania má väčšiu prioritou;
SRPT	(shortest remaining processing time first) úloha so zostávajúcim menším časom spracovania má väčšiu prioritu;
FCFS	(first come first serve) úloha ktorá príde prvá, bude spracovaná prvá.

Nasledujúci algoritmus popisuje algoritmické kroky dispečerského prioritného pravidla RPT (random processing time first).

Algoritmus: Dispečerské prioritné pravidlo RPT

1. Krok Inicializácia

Poradie úloh vytvoríme náhodne

2. Krok Prideľovanie úloh

V tomto poradí priraďujme úlohy strojom $\mathcal M$ , ktoré sa najskôr uvoľnia.

Nech $\pi$ je permutácia množiny $\mathcal N = \{1,2,\dots,n\}$ . Nasledujúci algoritmus popisuje algoritmické kroky dispečerského prioritného pravidla LPT (longest processing time first).

Algoritmus: Dispečerské prioritné pravidlo LPT

1. Krok Inicializácia

Vytvoríme poradie úloh

$p_{\pi(1)}\geq p_{\pi(2)}\geq\dots\geq p_{\pi(n)}$

(1)

2. Krok Prideľovanie úloh

V tomto poradí priraďujme úlohy strojom $\mathcal M$ , ktoré sa najskôr uvoľnia.

Dôležitou vlastnosťou dispečerského prioritného pravidla LPT je, že zrovnomerňuje pracovné výkony strojov. Nasledujúci algoritmus popisuje algoritmické kroky dispečerského prioritného pravidla SPT (shortest processing time first).

Algoritmus: Dispečerské prioritné pravidlo SPT

1. Krok Inicializácia

Vytvoríme poradie úloh

$p_{\pi(1)}\leq p_{\pi(2)}\leq\dots\leq p_{\pi(n)}$

(1)

2. Krok Prideľovanie úloh

V tomto poradí priraďujme úlohy strojom $\mathcal M$ , ktoré sa najskôr uvoľnia.

Priraďovanie priorít (1) a (2) úlohám robíme na základe porovnania časov spracovania všetkých úloh a to za pomoci metód porovnania fuzzy čísel. Nasledujúca sekcia aplikuje získané poznatky predošlých sekcií na probléme rozvrhovania identických paralelných strojov.

5. Identické paralelné stroje

Rozvrhovanie je optimálna alokácia/priradenie strojov množine úloh v čase. Nech $\mathcal M = \{M_1,M_2,\dots,M_m\}$ je množina identických paralelných strojov a nech $\mathcal J=\{J_1,J_2,\dots,J_n\}$ je množina úloh, kde $m, n$ sú kladné celé čísla. Podľa Graham a kol. [8] môžeme takýto systém klasifikovať ako $P_m,||f$ , kde $f$ je miera nerovnomernosti. Rozvrhovanie je obmedzované viacerými predpismi a pravidlami pomocou nasledujúcich ťažkých podmienok:

(h1) Každý stroj v jednom časovom okamžiku môže vykonávať nanajvýš jednu úlohu
(h2) Každú úlohu v jednom časovom okamžiku môže spracovať nanajvýš jeden stroj
(h3) Každú úlohu nie je možné pri jej spracovávaní prerušiť.
(h4) Každá úloha je k dispozícii pre spracovanie už v čase 0.
(h5) Nezáleží na poradí spracovania úloh, t.j. neexistuje precedenčná relácia medzi úlohami.

Nazývajú sa ťažkými podmienkami, pretože sa pri vytváraní rozvrhu nesmú porušiť. Ďalej je dobrý rozvrh charakterizovaný ľahkými podmienkami. V našom prípade ide o jednu ľahkú podmienku, a to zrovnomerňovanie celkových kumulovaných pracovných časov strojov, čo môžeme taktiež formulovať ako minimalizáciu miery nerovnomernosti $f$ . V ľahkých podmienkach sú zahrnuté ciele rozvrhovania a tie optimalizujeme.

Fuzzy čas spracovania úlohy $J_k$ budeme značiť ako $p_k = (p^a_k, p^b_k, p^c_k)\in\mathcal H(N)$ , pre všetky $k\in\mathcal J$ . Doba spracovania $p_k$ úlohy $J_k$ je na všetkých strojoch rovnaká.

6. Experimentálne porovnanie

Najskôr vygenerujeme množinu fuzzy čísel, ktorých pravá hodnota je menšia alebo rovný hodnote $h$ . Tieto fuzzy čísla chceme použiť na modelovanie fuzzy časov spracovania úloh. Definujeme ju ako

$\mathcal H(N,h) = \{(a,b,c)\,|\,a < b < c \leq h,\, a,b,c,h \in N_0\}[/latex]</td> <td style="width:20px; text-align:center;"></td> </tr> </table> <p align="justify">Pseudokód generátora trojuholníkových fuzzy čísel <img src='http://s0.wp.com/latex.php?latex&bg=ffffff&fg=000000&s=0' alt='' title='' class='latex' />(a,b,c)\in\mathcal H(N,h)$ , kde hodnota $c$ nepresiahne parameter $h$ , môžeme vidieť na obrázku 3. Z tejto množiny fuzzy trojuholníkových čísel vyberieme rovnomerne $n$ fuzzy čísel a vytvoríme tak množinu časov spracovania $n$ -úloh. Indexy porovnania fuzzy čísel značíme ako $F^{(1)}$ až $F^{(10)}$ .

Fig. 3 Pseudokód generovania fuzzy čísel

Dispečérskym prioritným pravidlom pri nasledujúcom experimente je LPT pravidlo. O tomto pravidle je všeobecne známe, že zrovnomerňuje pracovné zaťaženia strojov. Preferenčnú permutáciu priraďovania úloh (1) sme vytvárali postupne pre metódy porovnania čísel $F^{(1)}$ až $F^{(10)}$ . Mierou nerovnomernosti, pomocou ktorej určujeme kvalitu výberu metódy porovnania a kvalitu výberu dispečérskeho prioritného pravidla, je nasledujúca upravená miera nerovnomernosti, ktorá bola prezentovaná v článkoch [16], [10]:

$f_{ssqr}(x) = \frac{1}{3}\left(\frac{1}{m}\sum_{M_i\in\mathcal M}(x^a_i - \bar{x}^a)^2 + \frac{1}{m}\sum_{M_i\in\mathcal M}(x^b_i - \bar{x}^b)^2 + \right.$

$\left . \frac{1}{m}\sum_{M_i\in\mathcal M} (x^c_i - \bar{x}^c)^2\right)$

(2)

kde

$\bar{x}^a = \frac{1}{n}\sum_{J_k\in\mathcal J} p^a_k,\quad\bar{x}^b = \frac{1}{n}\sum_{J_k\in\mathcal J} p^b_k\quad\text{ a }\quad\bar{x}^c = \frac{1}{n}\sum_{J_k\in\mathcal J} p^c_k$

Vektor $x = (x_1,x_2,\dots,x_m)$ predstavuje $m$ pracovných zaťažení strojov. Miera nerovnomernosti (3) je tvorená sumou trojice hodnôt, pričom prvá suma vyjadruje mieru nerovnomernosti pre ľavé hodnoty fuzzy trojuholníkových pracovných zaťažení strojov, druha suma hodnôt vyjadruje mieru nerovnomernosti pre modálne hodnoty fuzzy trojuholníkových pracovných zaťažení strojov a tretia suma hodnôt vyjadruje mieru nerovnomernosti pre pravé hodnoty fuzzy trojuholníkových pracovných zaťažení strojov.

Agregačná metóda ( $F^{(6)}$ ) má váhy nastavené na hodnoty $w_1 = 0.5$ a $w_2 = 0.5$ . Nasledujúca tabuľka obsahuje priemerné hodnoty mier nerovnomerností pre 1000 vstupných inštancií: $n = 1000$ , $m = 50$ , $h = 40$ , kde $n$ je počet úloh, $m$ je počet strojov a $h$ je maximálna hodnota, ktorá ohraničuje fuzzy trojuholníkové čísla sprava.

LPT	$f_{ssqr}$
$F^{(1)}$	397.39
$F^{(2)}$	418.21
$F^{(3)}$	400.38
$F^{(4)}$	417.25
$F^{(5)}$	778.18
$F^{(6)}$	463.66
$F^{(7)}$	400.24
$F^{(8)}$	418.60
$F^{(9)}$	390.85
$F^{(10)}$	398.11

Menšia miera nerovnomernosti vyjadruje viac zrovnomernený rozvrh. Najlepší prípad by nastal, keby miera nerovnomernosti (3) bola nulová. Vykonanie 1000 experimentov trvalo 4 hodiny a 38 minút. Najlepšie sa umiestnila Chen-Chenová metóda porovnania fuzzy čísel a najhoršie sa umiestnila Dvořáková metóda. Nasledujúca tabuľka obsahuje výsledky pre ďalších 1000 experimentov, v ktorých sme použili dispečérske prioritné pravidlo SPT. Parametre inštancie sú rovnaké ako v predchádzajúcom experimente. Priemerné výsledky experimentov sú v nasledujúcej tabuľke.

SPT	$f_{ssqr}$
$F^{(1)}$	498.49
$F^{(2)}$	520.72
$F^{(3)}$	495.45
$F^{(4)}$	522.45
$F^{(5)}$	819.55
$F^{(6)}$	569.90
$F^{(7)}$	498.72
$F^{(8)}$	524.34
$F^{(9)}$	491.58
$F^{(10)}$	497.83

Vykonanie 1000 experimentov trvalo 6 hodín a 31 minút. Aj v tomto prípade sa najlepšie umiestnila Chen-Chenová metóda porovnania fuzzy čísel a najhoršie Dvořáková metóda. Výsledky ďalších 1000 experimentov, v ktorých použijeme dispečérske prioritné pravidlo RPT, sú zapísané v nasledujúce tabuľke.

RPT	$f_{ssqr}$
$F^{(1)}$	736.40
$F^{(2)}$	778.53
$F^{(3)}$	725.49
$F^{(4)}$	782.50
$F^{(5)}$	838.58
$F^{(6)}$	663.37
$F^{(7)}$	732.01
$F^{(8)}$	776.31
$F^{(9)}$	736.00
$F^{(10)}$	729.18

Vykonanie 1000 experimentov trvalo 1 hodinu a 27 minút. V tomto prípade sa najlepšie umiestnil agregačný prístup porovnania fuzzy čísel a najhoršie sa umiestnila Dvořáková metóda. Ak porovnáme obdržané miery nerovnomernosti, ktoré sú vypočítané po použití dispečérskeho prioritného pravidla LPT s mierami nerovnomernosti po použití dispečérskeho prioritného pravidla SPT a RPT, tak dôjdeme k záveru, že dispečérske prioritné pravidlo LPT viac zrovnomerňuje rozvrh.

7. Záver

Článok prezentoval problém prideľovania úloh strojom pomocou prioritných dispečérskych prioritných pravidiel. Každá úloha je reprezentovaná časom spracovania, ktorý je neistý. Túto neistotu modelujeme pomocou fuzzy trojuholníkových čísel. Veľké množstvo dispečérskych prioritných pravidiel pracuje na princípe porovnania časov spracovania jednotlivých úloh. Keďže ale časy spracovania obsahujú neistotu je potreba zvoliť (navrhnúť) metódu porovnania, ktorá je schopná porovnať takéto dve neisté čísla, v našom prípade ide o porovnanie trojuholníkových fuzzy čísel.

V článku sme prezentovali 10 metód porovnania fuzzy trojuholníkových čísel. Zaujímalo nás, ako jednotlivé metódy porovnania fuzzy čísel ovplyvňujú rovnomernosť rozvrhu. Dospeli sme k názoru, že z uvedených desiatich metód porovnania fuzzy čísel sa najlepšie umiestnila Chen-Chenová metóda. Pri vyhodnocovaní výsledkov porovnávaní metód sme zanedbali optimalizačné vlastnosti, klady a zápory jednotlivých metód a taktiež sme zanedbali neúspešnosť s akou jednotlivé metódy porovnávajú fuzzy čísla. Pod pojmom neúspešnosť si môžeme predstaviť počet rôznych fuzzy čísel, ktoré daná metóda považuje za totožné.

Taktiež nás zaujímalo, ktoré z dispečérskych prioritných pravidiel dokáže lepšie zrovnomerniť rozvrh. Experimentálne sme dokázali, že dispečérske prioritné pravidlo LPT lepšie zrovnomerňuje plánovaný rozvrh. Toto zrovnomerňovanie spôsobuje ponechanie najmenších časov spracovania na koniec rozvrhovania.

Poďakovanie

Táto práca vznikla s podporou grantovej agentúry VEGA vrámci riešenia projektu 1/0374/11 Modelovanie a optimalizácia mobility a infraštruktúry v logistických sieťach.

Literatúra

R. Agarwal, Ö. Ergun, J.B. Orlin, and C.N. Potts. Solving parallel machine scheduling problems with variable depth local search. Working Paper, Operations Research, 2004.
D.E. Akyol. Identical parallel machines scheduling with dynamical networks using time-varying penalty parameters. Multiprocessor Scheduling: Theory and Application, page 436, 2007.
D. Dubois and H. Prade. Operations on fuzzy numbers. The International Journal of Systems Sciences, 9:613–626, 1978.
J. Dvořák. Criteria for fuzzy scheduling. Proceedings of the 7th International Conference on Soft Computing MENDEL ’2001, pages 319–328, 2001.
A. Frangioni, M.G. Scutella, and E. Necciari. Multi- exchange algorithms for the minimum makespan machine. Technical report, Universita degli Studi di Bologna, Dipar- timento di informatica, Università di Pisa, 1999. Technical Report: TR-99-22.
M.R. Garey and D.S. Johnson. Computers and Intractability: a Guide to the Theory of NP-Completeness. W. H. Freeman
and Co. New York, NY, USA, 1979.
R.L. Graham. Bounds on multiprocessing timing anomalies.
SIAM J. Appl. Math. 17., pages 163–269, 1969.
R.L. Graham, E.L. Lawler, J.K. Lenstra, and A.H.G. Rinnooy Kan. Optimization and approximation in deterministic sequencing and scheduling: A survey. odborný časopis neznámy, 1979.
R. Jain. Decisionmaking in the presence of fuzzy variables. IEEE Transactions on Systems, Man and Cybernetics, 6, pages 698–703, 1976.
T. Ladovský. Problém rovnomernosti sĺpcovo permutovanej trojuholníkovej fuzzy matice. Master’s thesis, Fakulta riadenia a informatiky, Univerzita v Žiline, 2008. Diploma work 78/2007.
J.H. Lee and H. Lee-Kwang. A method for ranking fuzzily fuzzy numbers. The Nineth IEEE International Conference on Fuzzy Systems, 1:71–76, 2000.
C.S. McCahon and E.S. Lee. Fuzzy job sequencing for a flow shop. European Journal of Operational Research, 1992.
P. Mičunek. Metastratégie pri riešení problému job-shop. Písomná práca na dizertačnú skúšku, Fakulta riadenia a informatiky, Katedra matematických metód, Žilinská univerzita v Žiline, Žilina, 2002.
S.H. Nasseri and M. Sohrabi. Hadi‘s method and it‘s advantage in ranking fuzzy numbers. Australian Jornal of Basic and Applied Sciences, 4(10), pages 4630–4637, 2010.
S. Palúch. Teoria rozvrhov. učebné texty.
Š. Peško. The matrix permutation problem in interval arithmetic. Journal of Information, Control and Management Systems, 1(1), 2006.
M.L. Pinedo. Scheduling: Theory, Algorithms, and Systems. Spinger, 3rd edition, 2008.
N. Ramli and D. Mohamad. A comparative analysis of centroid methods in ranking fuzzy numbers. European Journal of Scientific Research, 28(3):492–501, 2009.
R. Sakawa, M. Kubota. Fuzzy programming for multiobjective job shop scheduling with fuzzy processing time and fuzzy duedate through genetic algorithms. European Journal of Operations Research, 120:393–407, 2000.
M. Tegze and M. Vlach. On the matrix permutation problem. Technical Report 84-54, Institute fur mathematic, Universitaet Graz, 1986.
R.R. Yager. On a general class of fuzy connectives. Fuzzy Sets and Systems, 4(6), pages 235–242, 1980.
L.A. Zadeh. Fuzzy sets. Information and Control 8 (3), page 338–353, 1965.

O časopise

Meta

RSS

Aplikácia fuzzy dispečerských prioritných pravidiel

Napísať príspevok

Rubriky

Burza práce

Štúdijné materiály

Archív