Problém rovnomerných rozvrhov a fuzzy inferenčné systémy

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

Zovšeobecnenú matematickú formuláciu problematiky tvorby rovnomerných rozvrhov pri neistote poznáme pod názvom “problém rovnomernosti riadkových súčtov stĺpcovo permutovanej matice”. Neistota je zahrnutá v prvkoch matice alebo spôsobe optimalizácie. Veľmi zaujímavá je dvojstĺpcová varianta problému, ktorá je často základom heuristík. Túto dvojstĺpcovú variantu vieme riešiť polynomiálne pomocou priraďovacej úlohy. Článok sa venuje problému návrhu nového spôsobu určenia koeficientov účelovej funkcie priraďovacej úlohy pomocou fuzzy inferenčného systému.

1. Úvod

V tomto článku rozumieme pod pojmom tvorba rozvrhu alebo rozvrhovanie proces rozhodovania, ktorý sa používa vo výrobnom priemysle, vo verejnej doprave a v iných odvetviach a službách. Pracuje s prideľovaním aktivít k zdrojom nad danými časovými periódami a snaží sa optimalizovať jednu alebo viac kriteriálnych funkcií tak, aby boli splnené všetky podmienky priradené k jednotlivým aktivitám a zdrojom. Z iného pohľadu je tvorba rozvrhov problémom časového plánovania a kombinatorickej optimalizácie. To sú problémy v ktorých vystupujú diskrétne premenné a v ktorých množina prípustných riešení je konečná. V každom z týchto problémov sa skrýva možnosť kombinatorickej explózie.

Rozvrh je súbor údajov, z ktorého je zrejmé, v ktorých časových intervaloch sa majú jednotlivé aktivity realizovať na ktorých zdrojoch. Zdrojmi môžu byť vodiči autobusov, stroje v dielni, viacnásobné/viacjadrové procesory, dopravné prostriedky, robotníci na pracovisku a veľa iného. Aktivitami môžu byť turnusy¹ v autobusovej doprave, úlohy (operácie) vo výrobnom procese, vykonávanie počítačových programov, etapy pri stavebnom projekte a iné.

Každá aktivita má naplánovanú dobu trvania. V reálnom živote sa stretávame so zrovnomerňovaním pracovných zaťažení/výkonov strojov/vodičov za dané časové (periodické) obdobie rozvrhovania. Aby sme vedeli optimalizovať rovnomernosť rozvrhov, potrebujeme poznať mieru nerovnomernosti, ktorá je jednou z optimalizovaných kriteriálnych funkcií a môže nadobúdať nasledujúce tvary

$f_{dev}(x_1, \dots, x_m)=\frac{1}{m}\sum_{i=1}^{m}\frac{|x_i-\bar{x}|}{\bar{x}}$

(1)

$f_{ssqr}(x_1, \dots, x_m)=\frac{1}{m}\sum_{i=1}^{m} (x_i - \bar{x})^2$

(2)

Za predpokladu, že vytvárame rozvrh v doprave, môže jednotlivé premenné x₁ až x_m predstavovať plánované pracovné zaťaženia m vodičov a $\bar{x}$ je ideálnym pracovným zaťažením vodičov, v tomto prípade priemernou hodnotou, ktorú spočítame ako

$\bar{x} = \frac{1}{m} \sum_{i=1}^{m} x_i$

Rozvrhy, ktoré vznikli optimalizáciou miery nerovnomernosti, nazývame rovnomernými rozvrhmi. Vzhľadom na známu Grahamovu [1] klasifikáciu ide o neštandardný typ rozvrhov. Pod pojmom rovnomerné rozvrhy pri neistote rozumieme v nasledujúcom texte také rovnomerné rozvrhy, ktorých veľkosť aktivít je neistá a/alebo podmienky priradené k jednotlivým aktivitám a zdrojom sú vyjadrené neisto.

2 Rovnomerné rozvrhy pri neistote

Rovnomerné rozvrhy môžeme zovšeobecniť a matematicky formulovať ako kombinatorický problém rovnomernosti riadkových súčtov stĺpcovo permutovanej matice, ktorý anglicky označujeme ako matrix permutation problem $\mathcal{MPP}$ [3]. Vhodným preusporiadaním stĺpcov matice môžeme docieliť väčšiu rovnomernosť riadkových súčtov matice/rozvrhu.

Definícia 1 (Matrix permutation problem [2])

Nech $\mathcal M=\{1,2,\dots,m\}$ a $\mathcal N=\{1,2,\dots,n\}$ sú konečné neprázdne množiny a nech $\mathbb A=(a_{ij})\in\mathfrak R^{m\times n}$ je reálna matica rozmeru $m\times n$ . Hľadá sa taká matica permutácií $\Psi = (\psi_j)_{j\in N}$ stĺpcov matice $\mathbb A$ pre ktorú platí:

$\min_{\psi\in\Pi(\mathcal M)}\Big\{ f(s^{\psi}_1,s^{\psi}_2,\dots,s^{\psi}_m) \:|\: s^{\psi}_i=\sum_{j\in\mathcal N} a_{\psi_{ij},j},\forall i\in\mathcal M$

$\psi_j = (\psi_{1j},\psi_{2j}\dots,\psi_{mj}),\forall j\in\mathcal N \Big\}$

kde f je nejaká miera nerovnomernosti vektora reálnych čísel, $s^{\psi}_i$ je i-ty riadkový súčet matice ${\mathrm A}^\psi$ a $\Pi(\mathcal M)$ je množina všetkých permutácií množiny $\mathcal M$ . Riešením takto formulovanej úlohy $\mathcal{MPP}$ je matica ${\mathbb A}^\psi = (a_{\psi_{ij},j})$

Veľmi zaujímavá varianta problému ${\mathcal MPP}$ vzniká pri dvojstĺpcovej matici, tzv. n=2, ktorú označujeme ${\mathcal MPP2c}$ . Túto variantu vieme riešiť exaktne v polynomiálnom čase pomocou \textit{priraďovacej úlohy} bivalentného lineárneho programovania, kde maticu priradení $X = (x_{ij})$ definujeme ako

$x_{ij} = \left\{ \begin{array}{ccc} 1 & \text{potom} & \psi_{i1} = i, \psi_{i2} = j \\ 0 & \text{nic nerob} & \end{array} \right. (i,j)\in\mathcal M\times\mathcal M$

(3)

Definícia2 (Klasická priraďovacia úloha KPU)

Medzi najznámejšie inštancie rozvrhovacích úloh patrí klasická priraďovacia úloha. Nech $M,|M|=m$ je konečná množina, $\mathbb C$ typu $m\times m$ je daná matica reálnych čísel a $\mathbb X$ typu $m\times m$ je hľadaná matica priradení. Potom priraďovaciu úlohu možno formulovať ako nasledujúcu úlohu bivalentného lineárneho programovania.

$\begin{array}{c} \min Z = \sum_{i\in M} \sum_{j\in M}{c_{ij}x_{ij}} \\ s.t. \\ \sum_{i\in M}x_{ij} = 1, \quad pre \quad \forall j\in M, \\ \sum_{j\in M}x_{ij} = 1, \quad pre \quad \forall i\in M, \\ x_{ij}\in\{0,1\}, \quad pre \quad \forall (i,j)\in M^2 \end{array}$

(4)

Aby sme vyriešili ${\mathcal MPP2c}$ pomocou ${\mathcal KPU}$ , potrebujeme správne navrhnúť účelovú funkciu, t.j. prvky matice $\mathbb C$ . Pre štandardný postup [2] nám poslúži miera nerovnomernosti (2). Po jednoduchej úprave získavame nasledujúci tvar

$f_{ssqr}(s_1,s_2,\dots,s_m) = \frac{1}{m}\sum_{i=1}^{m}s_i^2 - \bar{s}^2$

(4)

Za predpokladu že permutácia prvého stĺpca je identická, je $s_i = a_{i1} + a_{\psi_{i2} 2}$ . Hodnoty $\frac{1}{m}$ a $\bar{s}^2$ sú konštantné a neovplyvňujú výsledok optimalizácie, preto ich z účelovej funkcie môžeme vypustiť. Za predpokladu $\psi_{i2} = j$ , môžeme písať prvok matice $\mathbb C$ ako $c_{ij} = (a_{i1} + a_{j2})^2$ pre všetky $(i,j)\in\mathcal M\times\mathcal M$

Čo ale ak potrebujeme nahradiť niektoré alebo všetky prvky matice $\mathbb A$ neistými hodnotami (fuzzy číslami, fuzzy intervalmi)? V takomto prípade potrebujeme definovať novú mieru nerovnomernosti, ktorá vie pracovať s neistými číslami. Takýto postup ale nie je cieľom článku. My chceme použiť trošku neštandardný postup a ukázať nové možnosti použitia fuzzy inferenčných systémov, to je ale cieľom predposlednej sekcie 3.

Pre úplnosť si ukážme ešte možnosti riešenia všeobecného problému ${\mathcal MPP}$ . Tento problém rovnomernosti riadkových súčtov stĺpcovo permutovanej matice môžeme riešiť dvoma známymi heuristikami:

Stochastickou dekompozičnou metódou ${\mathcal SDM}$
Metódou deň-po-dni (stĺpec-po-stĺpci) ${\mathcal DBD}$

Metóda deň-po-dni najskôr pridelí turnusy vodičom pre prvý deň rozpisovania služieb, potom pre druhý deň a takto pokračuje až nepridelí turnusy vodičom pre každý deň rozpisovacieho obdobia. Toto prideľovanie sa deje s ohľadom na optimalizačné kritérium, ktoré je v tom tomto článku mierou nerovnomernosti. Nech $\mathcal M=\{1,2,\dots,m\}$ je množina indexov riadkov a $\mathcal N=\{1,2,\dots,n\}$ je množina indexov stĺpcov reálnej matice $\mathbb A=(a_{ij})\in\mathfrak R^{m\times n}$ rozmeru $m\times n$ . Nech $\psi=(\psi_1, \psi_2,\dots, \psi_n)$ je usporiadaná n-tica permutácií množiny $\mathcal M$ .

Algoritmus: Zovšeobecnená metóda deň-za-dňom [4]

1. Krok Inicializácia

Nech k je aktuálny index stĺpca, potom nastav k:=1
Nech $\mathbb A$ je vstupná matica rozmeru $m\times n$
Nech $\psi:=(\psi_1,\psi_2,\dots,\psi_n)$ je inicializačná usporiadaná n-tica permutácií množiny $atex \mathcal M$, pre ktorú platí, že $\psi_j:= (1,2,\dots,m)$ pre $\forall j\in N$ .

2. Krok Hľadanie permutácie $\psi_k$

Pre dané aktuálne k nastav $b_{kk}:=1$
Nájdi takú permutáciu $\psi_k$ , pre ktorú platí, že $(\mathbb A^\psi\times\mathbb B)$ je optimálnou stĺpcovo permutovanou maticou s ohľadom na optimalizačné kritérium. Operácia $\times$ je operáciou násobenia matíc.

3. Krok Kontrola

Ak k=n, potom KONIEC; inak k:=k+1 a GOTO krok 2.

Stochastická dekompozičná metóda pracuje na princípe rozkladu problému na niekoľko podproblémov (častí), riešením týchto podproblémov a ich následnou kompozíciou. Nech $\mathcal M=\{1,2,\dots,m\}$ je množina indexov riadkov a $\mathcal N=\{1,2,\dots,n\}$ je množina indexov stĺpcov reálnej matice $\mathbb A=(a_{ij})\in\mathfrak R^{m\times n}$ rozmeru $m\times n$ . Nech $\psi=(\psi_1, \psi_2,\dots, \psi_n)$ je usporiadaná n-tica permutácií množiny $\mathcal M$ .

Algoritmus: Stochastická-dekompozičná metóda [2]

1. Krok Kontrola

Začíname s $m\times n$ reálnou maticou $\mathbb A$ a ľubovoľnou n-ticou $\psi=(\psi_1,\dots,\psi_n)$ permutácií.

2. Krok Stochastická dekompozícia

Náhodne vyberieme $2\leq r < n[/latex] neprázdnych podmnožín [latex]\mathcal J_k\neq\emptyset[/latex] množiny indexov stĺpcov, t.j. [latex]\mathcal J_k\subset\mathcal N[/latex], [latex]k=1,2,\dots,r[/latex] pre ktoré platí [latex]\bigcap_{k=1}^{r} J_k = \emptyset[/latex] a zároveň [latex]\bigcup_{k=1}^{r} J_k = N[/latex]</li> </ul> <p align="justify">3. Krok Riešenie podproblému <ul> <li>Nájdime takú usporiadanú r-ticu permutácií <img src='https://s0.wp.com/latex.php?latex&bg=ffffff&fg=000000&s=0' alt='' title='' class='latex' />\pi = (\pi_1,\dots,\pi_r)$ , pre ktoré platí, že matica $B^\pi = (b^\pi_{ij})$ rozmeru $m\times r$ , ktorú definujeme ako

$b^\pi_{ik} = \sum_{j\in\mathcal J_k} a_{\psi_{ij},j},\quad\text{pre}\quad k=1,2,\dots,r,$

kde $i\in\mathcal M$ , je optimálnou stĺpcovo permutovanou maticou s ohľadom na optimalizačné kritérium.

4.Krok Skladanie

Aplikujme permutáciu $\pi_1$ na všetky permutácie $\psi_j$ pre $j\in\mathcal J_1$ , to isté s $\pi_2$ na všetky permutácie $\psi_j$ pre $j\in\mathcal J_2$ , atď. – a tak aktualizujeme n-tuple $\psi$ ako

$\psi_j = \left\{ \begin{array}{c} \pi_1\circ\psi_j \text{ ak } j\in\mathcal J_1,\\ \pi_2\circ\psi_j \text{ ak } j\in\mathcal J_2,\\ \vdots \\ \pi_r\circ\psi_j \text{ ak } j\in\mathcal J_r. \end{array} \right.$

5. Krok Kontrola

Ak je splnené nejaké zastavovacie kritérium potom STOP inak GOTO krok 2.

Tretí krok metódy môžeme riešiť viacerými prístupmi. Napríklad pre r=2 vzniká dvojstĺpcová matica $\mathbb B$ , ktorú môžeme vzhľadom na optimalizačné kritérium riešiť pomocou priraďovacej úlohy (viď. definícia 2.2), kde hodnota premennej $x_{ij}\in\{0,1\}$ rozhoduje o tom, či i-ty prvok v ľavom stĺpci priradíme k j-temu prvku v pravom stĺpci. Ďalej pre r=3 sa ponúka použitie trojindexovej priraďovacej úlohy. Taktiež sa na úlohy pre $3 \leq r < n[/latex] môžeme pozerať ako na zjednodušenú úlohu, ktorej čas výpočtu [latex]O((m!)^r)[/latex] je omnoho kratší s porovnaním času výpočtu [latex]O((m!)^n)[/latex] pôvodnej nedekomponovanej matice. <p align="justify">Podobne môžeme vytvoriť algoritmus, ktorý dekomponuje maticu riadkovo, t.j. z m-riadkovej matice vytvorí napríklad dvojriadkovú maticu, ktorú môžeme optimalizovať klasickou úlohou o batohu. <p align="justify">Poznámka 1. (Dvojstĺpcový <img src='https://s0.wp.com/latex.php?latex&bg=ffffff&fg=000000&s=0' alt='' title='' class='latex' />{\mathcal MPP2c}$ problém)

Hlavný výpočet heuristík pozostáva z problematiky ${\mathcal MPP2c}$ . Pri ${\mathcal SDM}$ a pre r=2 je to konkrétne jej tretí krok a pre ${\mathcal SDM}$ je to konkrétne druhý krok heuristiky. Táto vlasnosť nám dovoľuje použiť vyššie spomínaný postup riešenia ${\mathcal MPP2c}$ problému pomocou priraďovacej úlohy ${\mathcal KPU}$ .

Cieľom článku nieje prezentovať výhody a nevýhody jednotlivých heuristických metód, ale ukázať fuzzy inferenčné systémy ako vhodný a jednoduchý nástroj pri riešení problémov spojených s tvorbou rovnomerných rozvrhov, v tomto prípade pri návrhu prvkov matice $\mathbb C$ .

3. Návrh koeficientov účelovej funkcie

Aby sme mohli vyriešiť ${\mathcal MPP2c}$ problém pomocou ${\mathcal KPU}$ , potrebujeme správne navrhnúť účelovú funkciu, t.j. prvky matice $\mathbb C$ . Už vieme, že môžeme použiť modifikovanú mieru nerovnomernosti (5). Teraz na nasledujúcom príklade je ukázaný ďalší spôsob, pomocou ktorého demonštrujeme jednoduchosť/výhody použitia fuzzy inferenčných systémov.

Príklad 1 (Ilustračný príklad riešenia ${\mathcal MPP2c}$ pomocou ${\mathcal FIS}$ )

Majme už existujúci s-dňový rozvrh pre piatich vodičov $(m = 5)$ a pre $(s+1)$ -vý deň chceme nájsť také priradenie i-teho vodiča k j-temu turnusu, aby index preferencie $c_{ij}$ spojený s týmto priradením bol maximálny, pričom musíme každému vodičovi priradiť práve jeden turnus (h1) a každému turnusu priradiť práve jedného vodiča (h2). Nech prvý stĺpec dvojstĺpcovej matice $\mathbb A$ odpovedá kumulovaným výkonom [min] piatich vodičov po s-tý deň a druhý stĺpec matice odpovedá pracovným časom [min] piatich turnusov, o ktorých ešte len máme rozhodnúť, ktorému vodičovi budú priradené.

Zadanie chceme riešiť pomocou priraďovacej úlohy (3), pre ktorú sú obe podmienky (h1,h2) splnené. Ostáva nám iba správne navrhnúť účelovú funkciu, t.j. prvky matice $\mathbb C = (c_{ij})$ , ktoré spočítame pomocou fuzzy inferenčného systému, pre každé $i\in\mathcal M=\{1,2,3,4,5\}$ a pre každé $j\in\mathcal M$ samostatne, tzn., že vykonáme 25 fuzzy inferencií.

Výhodou použitia fuzzy inferenčného systému je, že vyjadrí hodnoty matice $\mathbb C$ aj pre fuzzy vstupy, tzv. pre fuzzy maticu $\mathbb A$ . Teda nemusíme navrhovať žiadnu novú mieru nerovnomernosti pracujúcu s fuzzy číslami. Pre jednoduchosť riešme túto úlohu pre reálnu maticu, ktorej prvky sú fuzzy singletony

$\mathbb A=\left( \begin{array}{cc} 7200 & 420 \\ 7680 & 660 \\ 7080 & 480 \\ 7320 & 540 \\ 7500 & 360 \end{array} \right)$

Nami navrhovaný fuzzy inferenčný systém má dve reálne vstupné hodnoty $x_1$ a $x_2$ , ktoré sa zobrazujú do príslušných fuzzy množín (hodnôt fuzzy lingvistických premenných) a jednu reálnu výstupnú hodnotu y.

Báza dát pozostáva z dvoch fuzzy lingvistických premenných $A, B$ , ktoré sú potrebné pri fuzzyfikácií, t.j. pri určovaní stupňa, ktorým jednotlivé vstupy prislúchajú fuzzy lingvistickým hodnotám, ktoré definujeme pomocou funkcií príslušnosti. Nech $A$ je fuzzy lingvistická premenná vyjadrujúca denný kumulovaný pracovný čas vodiča nadobúdajúca nasledujúce hodnoty (obr. 1):

VS – Very short working cumulated time
S – Short working cumulated time
A – Average working cumulated time
L – Long working cumulated time
VL – Very long working cumulated time

Obr. 1: Fuzzy lingvistická premenná A vyjadrujúca kumulovaný denný pracovný čas vodiča s danými funkciami členstva fuzzy množín VS, S, A, L, VL

Nech $B$ je fuzzy lingvistická premenná vyjadrujúca denný pracovný čas turnusu, ktorá nadobúda nasledujúce hodnoty (obr. 1(b)):

VS – Very short working time
S – Short working time
A – Average working time
L – Long working time
VL – Very long working time

Obr. 2: Fuzzy lingvistická premenná B vyjadrujúca denný pracovný čas turnusu a jej funkcie členstva fuzzy množín VS, S, A, L, VL

Ďalej báza dát pozostáva z fuzzy lingvistickej premennej $C$ , ktorá je potrebná v procese inferencie na získanie výslednej hodnoty (plochy) uvažovaného lingvistického pravidla (AK – POTOM). Nech $C$ je fuzzy lingvistická premenná vyjadrujúca index preferencie a nadobúda nasledujúce hodnoty (obr. 3).

VLP – Very low preference
LP – Low preference
MP – Medium preference
HP – High preference
VHP – Very high preference

Obr. 3: Fuzzy lingvistická premenná C vyjadrujúca index preferencie a jej funkcie členstva fuzzy množín VLP, LP, MP, HP, VHP

Báza lingvistických pravidiel pozostáva z nasledujúcich piatich pravidiel:

$R_1: \text{ AK } (x_1 \text{ je VS } \wedge x_2 \text{ je VL }) \vee (x_1 \text{ je VL } \wedge x_2 \text{ je VS }),$

$\text{POTOM } y \text{ je VHP}$

$R_2: \text{ AK } ((x_1 \text{ je VS } \wedge x_2 \text{ je L }) \vee (x_1 \text{ je S } \wedge x_2 \text{ je VL })) \vee$

$\vee ((x_1 \text{ je L } \wedge x_2 \text{ je VS }) \vee (x_1 \text{ je VL } \wedge x_2 \text{ je VS } )), \text{ POTOM } y \text{ je HP }$

$R_3: \text{ AK } ((x_1 \text{ je VS } \wedge x_2 \text{ je A } ) \vee (x_1 \text{ je S } \wedge x_2 \text{ je L } ) \vee$

$\vee (x_1 \text{ je A } \wedge x_2 \text{ je VL } )) \vee ((x_1 \text{ je A } \wedge x_2 \text{ je VS } ) \vee$

$\vee (x_1 \text{ je L } \wedge x_2 \text{ je S } ) \vee (x_1 \text{ je VL } \wedge x_2 \text{ je A } )), \text{ POTOM } y \text{ je MP }$

$R_4: \text{ AK } ((x_1 \text{ je VS } \wedge x_2 \text{ je S } ) \vee (x_1 \text{ je S } \wedge x_2 \text { je A } ) \vee$

$\vee (x_1 \text{ je A } \wedge x_2 \text{ je L } ) \vee (x_1 \text { je L } \wedge x_2 \text { je VL } )) \vee$

$\vee ((x_1 \text { je S } \wedge x_2 \text{ je VS } ) \vee (x_1 \text { je A } \wedge x_2 \text{ je S } ) \vee$

$\vee (x_1 \text{ je L } \wedge x_2 \text{ je A } ) \vee (x_1 \text{ je VL } \wedge x_2 \text{ je L } )), \text{ POTOM } y \text{ je LP}$

$R_5: \text { AK } (x_1 \text{ je VS } \wedge x_2 \text{ je VS } ) \vee (x_1 \text{ je S } \wedge x_2 \text{ je S } ) \vee$

$\vee (x_1 \text{ je A } \wedge x_2 \text{ je A } ) \vee (x_1 \text{ je L } \wedge x_2 \text{ je L } ) \vee$

$\vee (x_1 \text{ je VL } \wedge x_2 \text{ je VL } ), \text { POTOM } y \text { je VLP }$

Vidíme, že takto zapísaná báza lingvistických pravidiel je dosť nečitateľná a preto ju zjednodušíme a zapíšeme pomocou nasledujúcej tabuľky:

Báza pravidiel

y		x₂
		VS	S	A	L	VL
x₁	VS	VLP	LP	MP	HP	VHP
	S	LP	VLP	LP	MP	HP
	A	MP	LP	VLP	LP	MP
	L	HP	MP	LP	VLP	LP
	VL	VHP	HP	MP	LP	VLP

Zadefinujme si teraz dve vstupné a jednu výstupnú hodnotu fuzzy inferenčného systému:

Prvou vstupnou hodnotou je $x_1 = a_{i1}$ ,
druhou vstupnou hodnotou je $x_2 = a_{j2}$ a
výstupnou hodnotou je $c_{ij} = y$ .

Tieto vstupy a výstupy definujeme pre každé $(i,j)\in\mathcal M\times\mathcal M$ . Teraz môžeme použiť nástroj [7] (aplikáciu), ktorým vyriešime takto navrhnutý fuzzy inferenčný systém aplikovaním Mamdamiho inferenčnej metódy. Postup inferencie pre dané vstupy $x_1 = 7200$ a $x_2 = 420$ s výslednou hodnotou $y = 22.5$ môžeme vidieť na obrázku 3. Výsledok inferencie y patriaci do intervalu [0,100] pre všetky vstupné hodnoty $x_1\in [7000, 8000]$ a $x_2\in [300, 700]$ sme spočítali pomocou balíčka pyFuzzy [6] v programovacom prostredí Python [5] a môžeme ho vidieť na obrázku 4. A matica $\mathbb C = (c_{ij})$ je rovná hodnotám

$\mathbb C=\left( \begin{array}{cccccc} 22.90 & 64.47 & 32.13 & 43.89 & 20.73 \\ 40.25 & 30.88 & 31.07 & 24.30 & 51.83 \\ 30.52 & 71.25 & 39.65 & 51.17 & 24.30 \\ 18.25 & 54.46 & 26.17 & 34.36 & 28.03 \\ 27.34 & 41.61 & 16.40 & 20.73 & 38.39 \end{array} \right)$

Po vyriešení priraďovacej úlohy získame maticu priradení $\mathbb X = (x_{ij})_{m\times m}$

$\mathbb X=\left( \begin{array}{cccccc} 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \end{array} \right)$

pre ktorú podľa predpisu (3) spočítame usporiadanú dvojicu (maticu permutácií 2.1) $\Psi = (\psi_1, \psi_2)$ optimálnych permutácií

$\Psi=\left( \begin{array}{cc} 1 & 2 \\ 2 & 5 \\ 3 & 4 \\ 4 & 3 \\ 5 & 1 \end{array} \right)$

pre ktoré obdržíme nasledujúci rozvrh

$\mathbb A^{\Psi}=\left( \begin{array}{cc} 7200 & 660 \\ 7680 & 360 \\ 7080 & 540 \\ 7320 & 480 \\ 7500 & 420 \end{array} \right)$

s kumulovanými pracovnými časmi vodičov $s^{\Psi} = (7860, 8040, 7620, 7800, 7920)$ .

Obr. 4: Výsledný graf fuzzy inferencie pre všetky vstupy.

4 Záver

Článok sa venoval problematike rovnomernosti riadkových súčtov stĺpcovo permutovanej matice, ktorú vieme riešiť pomocou dvoch známych heuristických metód. Obe heuristiky sú založené na zjednodušenej variante problému a exaktnom výpočte dvojstĺpcovej matice. Na exaktný výpočet sme použili priraďovaciu úlohu, pre ktorú sme navrhli koeficienty účelovej funkcie pomocou neštandardného postupu, t.j. pomocou fuzzy inferenčného systému.

Výhody použitia ${\mathcal FIS}$ na riešenie ${\mathcal MPP2c}$ sú:

Matica $\mathbb A$ môže obsahovať ako fuzzy singletony (reálne hodnoty), tak aj fuzzy čísla, tzv. fuzzy inferenčný systém ponúka možnosť definovania všeobecnej miery nerovnomernosti, ktorá pracuje ako s ostrými hodnotami, tak aj s fuzzy číslami.
Pre väčší počet hodnôt lingvistických premenných A,B a C obdržíme rovnomernejší rozvrh.
Znalostná báza pozostáva z jasne zrozumiteľných požiadaviek/pravidiel.

Literatúra

Graham, R.L., Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Optimization and Appro- ximation in Deterministic Sequencing and Scheduling: A Survey, 1979
Peško, Š., Optimalizácia NP-ťažkých dopravných rozvrhov, ŽU Žilina, Habilitačná práca, 2002
Peško, Š., The Matrix Permutation Problem in Interval Arithmetic, Journal of Information, Control and Management Systems, vol. 1, num. 1, 2006
Teodorovič, D., Luči ́c, P., A fuzzy set theory approach to the aircrew rostering problem, Fuzzy Sets and Systems, vol. 95, num. 3, pp. 261-277, 1998
Python, Python Programming Language, Programming Language,
www.python.org
pyFuzzy, Python fuzzy package,
pyfuzzy.sourceforge.net

Katedra matematických metód, Fakulta riadenia a informatiky, Žilinská Univerzita, Univerzitná 8215/1, 010 26 Žilina
¹Turnus je denný pracovný cyklus, ktorý má byť odjazdený vodičom v danom dni a pozostáva z postup- nosti trás. Trasa je súbor jázd a jazda pozostáva z príslušného času (miesta) odchodu a príchodu autobusu.

O časopise

Meta

RSS

Problém rovnomerných rozvrhov a fuzzy inferenčné systémy

Napísať príspevok

Rubriky

Burza práce

Štúdijné materiály

Archív