Návrh algoritmu pro optimalizaci diskrétních procesů


Věchet, Vladimír1, Olehla, Miroslav2

1 Prof. Ing., CSc., Technická univerzita v Liberci, Hálkova 6, 461 17 Liberec,

 vladimir.vechet@vslib.cz,  http://www.kky.vslib.cz/~vechet

2 Doc. Ing., CSc.,  miroslav.olehla@vslib.cz,  http://www.kky.vslib.cz/

1. Abstract

In the article the task of optimization of manufacturing processes is described and the algorithm for a solution of transformated problem is formulated, that enable to obtain relative quick useful results by means of computer aid.

2. Formulace problému

Komplexní technologickou úlohu lze rozložit na posloupnost dílčích procesů, jejichž isolovaná optimalizace samozřejmě vůbec nemusí korespondovat s optimálním řešením z hlediska celého technologického procesu. Jako kriterium optimalizace použijeme nejdříve nákladovostní kriterium, přičemž komplexní technologický proces rozdělíme do k skupin, z nichž každá obsahuje mi dílčích, navzájem nezávislých procesů. Pro zjednodušení zápisu a bez úkoru na obecnosti uvažujme pro každý dílčí proces dva optimalizované parametry p a q. To ostatně bývá velmi frekventovaný případ. Cílové kriterium pak zapíšeme ve tvaru

(1)

za předpokladu splnění všech technologických, výrobně-technických a technicko-organizačních omezení formulovaných pro daný dílčí proces, která generují tzv. oblast přípustných řešení Pij dílčího procesu

(2)

Z hlediska celého technologického procesu je však třeba při řešení zohlednit další omezující podmínku, vyjadřovanou ve tvaru časové restrikce :

(3)

Zatímco t představuje podíl spotřeby času dílčího procesu, vázaný na optimalizované parametry, tak jsou invarianty řešení a vyjadřují podíl času nezávislého na optimalizovaných parametrech.Ve speciálních případech lze výše uvedenou formulaci interpretovat následovně. Např. pro k=1 se operace skládá z m1 úseků a pak časová restrikce vyjadřuje požadavek na dodržení dané průběžné doby výrobní dávky, i když obecně uvedená časová restrikce vyjadřuje požadavek na dodržení taktu výroby.

3. Transformace úlohy

Vztahy

(4)

je dáno nějaké zobrazení Zij dílčího procesu, které každému bodu v Pij přiřazuje nějaký bod v transformované oblasti Rij v rovině času t a nákladovosti N. Budeme předpokládat, že toto zobrazení je v Pij regulární, což ostatně u reálných technologií bývá splněno. Formulujme nyní takovou funkci nákladovosti N v závislosti na čase t, že pro každé pevné

(5)

bude

(6)

za podmínky

(7)

Přitom

(8)

(9)

Pak bychom mohli danou úlohu vyjádřit ve tvaru

(10)

(11)

Z dosud analyzovaných případů lze usoudit, že Pij i Rij jsou souvislé oblasti a funkce Hij(tij ) spojité (tato spojitost však není podmínkou implementace dále uváděného algoritmu). Nicméně v praktických případech není grafická interpretace Hij( tij ) hladká křivka (nespojistost prvního druhu u první derivace). To však i ve zjednodušených případech brání ve využití analytických metod pro hledání vázaných extrémů (viz např. [2]), a proto byl pro řešení daného problému navržen dále uvedený algoritmus. Algoritmizaci transformace úlohy je nutné vždy řešit s ohledem na zvláštnosti jednotlivých technologií.

4. Návrh algoritmu

Proveďme nejprve korekci časových intervalů, které připadají v úvahu jako možná řešení. Nechť

(12)

(13)

(14)

Pak zřejmě pro a bude

(15)

kde

(16)

(17)

Označíme-li

(18)

tak

(19)

a uvážíme-li dále, že

(20)

tak stačí uvažovat

(21)

kde

 

(22)

(23)

Řešme pak nejprve úlohu ve tvaru

(24)

za podmínky

(25)

tedy pro nějaké pevné ti* . Označíme

(26)

kde

(27)

Dále pak

(28)

Přitom

(29)

a dále musí platit :

(30)

Tudíž vztah budeme řešit pro

(31)

Analogicky určíme

(32)

(33)

a tím na každém kroku řešení bude pro každé

(34)

dáno

(35)

kde je minimální. Potom také pro každé

(36)

budou hledané a pro dané ti* optimální hodnoty tir dány zpětným chodem :

(37)

(38)

(39)

Na každém kroku řešení se tedy daná úloha převádí na úlohu nalezení minima součtu 2 funkcí jednoho argumentu a tudíž aplikovat algoritmus numericky lze tak, že budeme uvažovat "dostatečně hustou" diskrétní změnu tij , nebo lépe aproximovat funkce H s dostatečnou přesností spojitými lineárními úseky (pak i funkce G bude téhož typu).

V rozšíření na původně definované zadání pak pro každé

(40)

bude

(41)

a tím úlohu redukujeme na iterační výpočet minima na intervalu .

Poznamenejme, že řešení úlohy existuje jen tehdy, když

(42)

Pokud bychom nákladovostní kriterium (1) nahradili kriteriem maximální produktivity ve tvaru

(43)

tak zřejmě

(44)

pochopitelně, že jen pokud platí

(45)

Výsledné optimum pak získáme řešením zjednodušených úloh ve tvaru :

(46)

za podmínky

(47)

pro

Optimální hodnoty originálních parametrů pak získáme pomocí inverzního zobrazení k zobrazení Zij.

5. Závěr

Popsaný algoritmus byl prověřen na případech optimalizace, kdy vztahy mezi technologickými proměnnými jsou vyjadřovány ve tvaru obecných mocninných závislostí a ukazuje se, že je dostatečně rychlý i pro případy aproximace pomocí spojitých lomených čar.

6. Literatura

VĚCHET, V. 1997. Optimalizace parametrů výrobních procesů. Liberec : Technická univerzita, 1997. 5 s.

JACOBS, H.-J., MASZAROS, I. : Zur Loesung von Optimalproblemen in der Fertigung spanender Prozesse mittels Lagrangeschen Multiplikators. Int. Manuskript der TU Dresden.