ˇ ´ vysoke ´ uc ˇen´ı technicke ´ v Praze Cesk e ´ Fakulta elektrotechnicka
´ pra ´ce Diplomova Modelace a optimalizace logistick´ych proces˚ u v Pivovarech Staropramen, a. s.
Praha, 2009
Michal Dvoˇr´ak
ii
Prohl´ aˇ sen´ı Prohlaˇsuji, ˇze jsem svou diplomovou pr´aci vypracoval samostatnˇe a pouˇzil jsem pouze podklady uveden´e v pˇriloˇzen´em seznamu.
V Praze dne podpis
iii
iv
Podˇ ekov´ an´ı Dovoluji si t´ımto podˇekovat Ing. Jiˇr´ımu Roubalovi, Ph.D. za zaj´ımav´e zad´an´ı, odborn´e veden´ı a cenn´e rady.
v
vi
Anotace ˇ e rePivovary Staropramen, a. s., jsou kolosem dod´avaj´ıc´ım sv´e produkty do cel´e Cesk´ publiky i mimo ni. Dennˇe jsou na mnoha v´ yrobn´ıch link´ach stoˇceny tis´ıce hektolitr˚ u piva a stovky r˚ uzn´ ych produkt˚ u putuj´ı mezi des´ıtkami distribuˇcn´ıch center. Efektivita t´eto logistiky je jedn´ım ze z´akladn´ıch pˇredpoklad˚ u ekonomick´e u ´spˇeˇsnosti firmy a pˇritom nen´ı dodnes jej´ı ˇr´ızen´ı podpoˇreno ˇz´adn´ ym komplexnˇejˇs´ım n´astrojem zaloˇzen´ ym na matematick´em popisu probl´emu. C´ılem t´eto pr´ace je doplnit pˇr´ıpadn´e mezery v modelu logistiky Pivovar˚ u Staropramen, a. s., prezentovan´em v pˇredchoz´ı pr´aci [1] a pˇredevˇs´ım nab´ıdnout studii moˇznost´ı a pˇr´ınosu realizace centralizovan´eho optimalizaˇcn´ıho n´astroje a to spoleˇcnˇe s n´avrhem ˇreˇsen´ı pomoc´ı matematick´eho programov´an´ı.
Annotation The giant corporation Pivovary Staropramen holds significant market share as a beer producer in the Czech Republic. Its production logistics consists of many bottling and keg lines as well as tens of distribution centers. Rich portfolio of about two hundred kinds of products is beeing delivered every day to customers from all over the republic and significat portion of production come to export. Efficiency of such extensive logistics structure is the main prerequisite for economical prosperity of the company. No sofisticated planning tool based on mathematical description of the problem is used, though. The goal of this thesis is to complete a model of logistics presented in [1] and above all offer a study of potential and benefits of logistics optimization tool as well as a concept of the actual realization using mathematical programming.
vii
viii
Českévysoké učenítechnickév Praze Fakulta elektrotechnická Katedra řídicí techniky
ZADÁNí plpl-oMovÉ PRÁcE Student: Bc. Michal Dvořák Studijní program: Elektrotechnika a informatika (ma-gisterský), strukturovaný oibor: Kybernetika a měření, blok KM1 - Řioicitechnika
Název tématu: Model logistických procesů v Pivovarech Staropramen
Pokyny pro Vypracování: '1 .
Vytvořte model logistických procesů zásobování výrobních linek v Pivovarech
Staropramen (konkrání specifikaci problému dodá Staropramen). modelování skladováni (rozvoz ze skladů, svoz z celé republiky) zásobování výrobních linek (obaly apod') obsluha rnýrobních linek (odvoz hotov'ých výrobků do skladŮ, k zákazníkům) 2. ověřte správnost modelu s reálnými daý z Pivovarů Staropramen. Proveďe srovnání s daty z minulosti i přítomnosti. 3. Navrhněte optimalizátor logistiky pro zásobování výrobních linek a zaváŽení skladŮ' Seznam odborné literatury: Petr Horáěek, Systémy a modely, Praha 2000 Web SAR!, http://dce.felk. cvut. czlsari/ Jan John, Systémy ařízeni, Praha 1999 Franklin, Powel, Emami-Naeini, Feedback Control of Dynamic Systems, Prentice Hall, 2006
Vedoucí: lng. JiříRoubal, Ph.D'
I
t
i1 I
I
L
Platnost zadání: do konce letního semestru 2008/09
1ůfu- ffi% -4
prof' lng. Michael Šebek, DrSc. vedoucí katedry
ffi
VPraze dne27.2.2009
x
Obsah
Seznam obr´ azk˚ u
xv
Seznam tabulek
xvii
´ 1 Uvod
1
1.1
Struktura podniku a v´ yrobn´ıho procesu . . . . . . . . . . . . . . . . . . .
2
1.1.1
V´ yrobn´ı linka . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
1.1.2
Sklad
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
1.1.3
Transport . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
Postup ˇreˇsen´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
1.2
2 O modelov´ an´ı, ˇ r´ızen´ı a optimalizaci 2.1
2.2
7
O modelov´an´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
2.1.1
Vstupn´ı a v´ ystupn´ı veliˇciny . . . . . . . . . . . . . . . . . . . . .
9
2.1.2
Stavov´e veliˇciny . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
2.1.3
Parametry syst´emu . . . . . . . . . . . . . . . . . . . . . . . . . .
10
O optimalizaci
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3 Model logistiky
10 11
3.1
Z´akladn´ı ustanoven´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
3.2
St´aˇcec´ı linka
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
Vstupn´ı a v´ ystupn´ı veliˇciny modelu linky . . . . . . . . . . . . . .
13
3.2.1
xi
3.3
3.4
3.5
3.6
3.2.2
Parametry modelu linky . . . . . . . . . . . . . . . . . . . . . . .
15
3.2.3
Z´akladn´ı vztahy . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
3.2.4
Rozˇs´ıˇren´ı modelu . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
Distribuˇcn´ı centrum a sklad . . . . . . . . . . . . . . . . . . . . . . . . .
29
3.3.1
Vstupn´ı a v´ ystupn´ı veliˇciny modelu skladu . . . . . . . . . . . . .
29
3.3.2
Parametry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31
3.3.3
Dalˇs´ı vztahy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
32
Transport . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
32
3.4.1
Vstupn´ı a v´ ystupn´ı veliˇciny modelu transportu . . . . . . . . . . .
32
3.4.2
Parametry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
34
3.4.3
Shrnut´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
34
Celkov´ y model
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
35
3.5.1
Veliˇciny celkov´eho modelu . . . . . . . . . . . . . . . . . . . . . .
35
3.5.2
Shrnut´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
37
Verifikace modelu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
38
3.6.1
Verifikace modelu st´aˇcec´ı linky
. . . . . . . . . . . . . . . . . . .
38
3.6.2
Vyhodnocen´ı verifikace . . . . . . . . . . . . . . . . . . . . . . . .
40
4 Optimaliz´ ator 4.1
4.2
4.3
C´ıl optimalizace
43 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
43
4.1.1
Proces pl´anov´an´ı . . . . . . . . . . . . . . . . . . . . . . . . . . .
44
4.1.2
Krit´erium optimality ˇr´ızen´ı . . . . . . . . . . . . . . . . . . . . .
46
4.1.3
Pˇr´ınosy optimaliz´atoru . . . . . . . . . . . . . . . . . . . . . . . .
48
Metody optim´aln´ıho ˇr´ızen´ı . . . . . . . . . . . . . . . . . . . . . . . . . .
49
4.2.1
Pˇresn´e metody . . . . . . . . . . . . . . . . . . . . . . . . . . . .
49
4.2.2
Heuristick´e metody . . . . . . . . . . . . . . . . . . . . . . . . . .
51
4.2.3
Vyhodnocen´ı algoritm˚ u. . . . . . . . . . . . . . . . . . . . . . . .
53
Diskretizace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
54
xii
4.4
4.5
4.6
4.3.1
Diskr´etn´ı model linky . . . . . . . . . . . . . . . . . . . . . . . . .
54
4.3.2
Diskr´etn´ı model skladov´an´ı . . . . . . . . . . . . . . . . . . . . . .
55
4.3.3
Diskr´etn´ı model transportu . . . . . . . . . . . . . . . . . . . . .
55
4.3.4
Celkov´ y diskr´etn´ı model . . . . . . . . . . . . . . . . . . . . . . .
56
Softwarov´e vybaven´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
58
4.4.1
Nekomerˇcn´ı solvery . . . . . . . . . . . . . . . . . . . . . . . . . .
59
4.4.2
Placen´e solvery . . . . . . . . . . . . . . . . . . . . . . . . . . . .
59
Popis probl´emu matematick´ ym programov´an´ım . . . . . . . . . . . . . .
60
4.5.1
Definice promˇenn´ ych . . . . . . . . . . . . . . . . . . . . . . . . .
60
4.5.2
Omezuj´ıc´ı podm´ınky . . . . . . . . . . . . . . . . . . . . . . . . .
61
4.5.3
´ celov´a funkce . . . . . . . . . . . . . . . . . . . . . . . . . . . . Uˇ
63
Vyhodnocen´ı optimalizace . . . . . . . . . . . . . . . . . . . . . . . . . .
66
4.6.1
Testovac´ı sc´en´aˇr . . . . . . . . . . . . . . . . . . . . . . . . . . . .
66
4.6.2
Validita v´ ystupu . . . . . . . . . . . . . . . . . . . . . . . . . . .
73
4.6.3
Rychlost optimalizace
. . . . . . . . . . . . . . . . . . . . . . . .
82
4.6.4
M´ıra zjednoduˇsen´ı oproti re´aln´emu probl´emu . . . . . . . . . . . .
84
5 Z´ avˇ ereˇ cn´ e vyhodnocen´ı
87
Literatura
92
A Nomenklatura
I
B Obsah pˇ riloˇ zen´ eho CD
V
xiii
xiv
Seznam obr´ azk˚ u 2.1
Blokov´e sch´ema stavov´eho popisu syst´emu . . . . . . . . . . . . . . . . .
8
3.1
Blokov´e sch´ema modelu st´aˇcec´ı linky . . . . . . . . . . . . . . . . . . . .
13
3.2
Uk´azkov´e pr˚ ubˇehy vstupn´ıch a v´ ystupn´ıch veliˇcin modelu linky . . . . . .
19
3.3
Transformace obd´eln´ıkov´eho sign´alu na sign´al lichobˇeˇzn´ıkov´ y . . . . . . .
20
3.4
Alternativn´ı zp˚ usob modelace postupn´eho n´ajezdu a odstaven´ı linky . . .
23
3.5
Pˇr´ıˇcina vzniku pˇrekryvu . . . . . . . . . . . . . . . . . . . . . . . . . . .
24
3.6
Ilustrace transformace vstupn´ıho sign´alu l(t) pro odstranˇen´ı pˇrekryvu . .
25
3.7
Srovn´an´ı ide´aln´ıho pr˚ ubˇehu v´ yroby pˇri pˇrekryvu s modelem. . . . . . . .
28
3.8
Sch´ema integr´atoru . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
29
3.9
Gantt˚ uv diagram st´aˇcen´ı pro verifikaci modelu . . . . . . . . . . . . . . .
39
3.10 Histogram odchylky modelu od reality pro jednotliv´e v´ yrobky . . . . . .
40
4.1
Sch´ema pl´anov´an´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
44
4.2
Gantt˚ uv diagram produkce pˇri nomin´aln´ım nastaven´ı . . . . . . . . . . .
69
4.3
Stavy produkt˚ u v DC Most pˇri nomin´aln´ım nastaven´ı optimalizace
71
4.4
Odchylky od poˇzadovan´ ych z´asob produkt˚ u v DC Most pˇri nom. nastaven´ı 71
4.5
Stavy produkt˚ u a obal˚ u v DC Sm´ıchov pˇri nom. nastaven´ı optimalizace .
72
4.6
Gantt˚ uv diagram produkce testu ˇc. 2 . . . . . . . . . . . . . . . . . . . .
75
4.7
Stavy produkt˚ u v DC Most a jejich odchylky od reference pˇri testu ˇc. 2 .
76
4.8
Gantt˚ uv diagram produkce testu ˇc. 3 . . . . . . . . . . . . . . . . . . . .
77
4.9
Pondˇeln´ı stavy produkt˚ u a obal˚ u ve sm´ıchovsk´em skladu pˇri testu ˇc. 3
78
xv
. . .
.
4.10 Pondˇeln´ı stavy produkt˚ u a obal˚ u ve sm´ıchovsk´em skladu pˇri testu ˇc. 4
.
78
4.11 Gantt˚ uv diagram produkce testu ˇc. 5 . . . . . . . . . . . . . . . . . . . .
79
4.12 Gantt˚ uv diagram produkce testu ˇc. 6 . . . . . . . . . . . . . . . . . . . .
79
4.13 Gantt˚ uv diagram produkce testu ˇc. 6 pˇri cpch = 0 . . . . . . . . . . . . .
80
4.14 Gantt˚ uv diagram produkce testu ˇc. 7 . . . . . . . . . . . . . . . . . . . .
80
4.15 Pondˇeln´ı stavy produkt˚ u pˇri testu ˇc. 8 . . . . . . . . . . . . . . . . . . .
81
4.16 Srovn´an´ı u ´tern´ıch stav˚ u obal˚ u v DC Most pro test ˇc. 9 a nom. nastaven´ı
81
xvi
Seznam tabulek 3.1
Rozdˇelen´ı transformace na intervaly . . . . . . . . . . . . . . . . . . . . .
21
3.2
Historie provozu linky . . . . . . . . . . . . . . . . . . . . . . . . . . . .
41
4.1
Kapacity sklad˚ u testovac´ıho sc´en´aˇre . . . . . . . . . . . . . . . . . . . . .
67
4.2
Poˇc´ateˇcn´ı mnoˇzstv´ı produkt˚ u a obal˚ u na skladech . . . . . . . . . . . . .
68
4.3
Odbˇer produkt˚ u a obal˚ u z distribuˇcn´ıch center . . . . . . . . . . . . . . .
68
4.4
Poˇzadovan´e hladiny z´asob v jednotliv´ ych skladech . . . . . . . . . . . . .
68
4.5
Koeficienty cenov´e funkce nomin´aln´ıho nastaven´ı optimaliz´atoru . . . . .
69
4.6
Souhrn informac´ı o nomin´aln´ım nastaven´ı optimaliz´atoru . . . . . . . . .
70
4.7
Transport ze sm´ıchovsk´eho skladu do DC Most v pondˇel´ı – nom. nastaven´ı 73
4.8
Hodnoty krit´eria nomin´aln´ıho nastaven´ı optimaliz´atoru . . . . . . . . . .
73
4.9
Hodnoty krit´eria pro test ˇc. 1 . . . . . . . . . . . . . . . . . . . . . . . .
74
4.10 Transport ze sm´ıchovsk´eho skladu do DC Most v pondˇel´ı pro test ˇc. 3 . .
82
4.11 Z´avislost ˇcasov´e n´aroˇcnosti v´ ypoˇctu na tvaru u ´ˇcelov´e funkce . . . . . . .
83
4.12 Z´avislost ˇcasov´e n´aroˇcnosti v´ ypoˇctu na pouˇzit´em solveru . . . . . . . . .
84
4.13 Z´avislost ˇcasov´e n´aroˇcnosti v´ ypoˇctu na zp˚ usobu popisu transportu . . . .
85
xvii
xviii
Kapitola 1 ´ Uvod ˇ e republiky, kter´emu by znaˇcka Pravdˇepodobnˇe neexistuje jedin´ y dospˇel´ y obyvatel Cesk´ Staropramen nic neˇr´ıkala. Vˇetˇsina si urˇcitˇe ihned pˇredstav´ı orosenou sklenici zlatav´eho n´apoje. A i ti, kteˇr´ı pivu pˇr´ıliˇs neholduj´ı, si jistˇe vybav´ı hory zelen´ ych beden naplnˇen´ ych lahv´aˇci“ zab´ıraj´ıc´ı znaˇcnou ˇc´ast pˇr´ısluˇsn´eho oddˇelen´ı supermarketu. ” ˇ um, ale belgick´emu To, ˇze Pivovary Staropramen, a. s., jiˇz p˚ ul desetilet´ı nepatˇr´ı n´am Cech˚ kolosu Inbev, jiˇz tolik zn´amo nen´ı. Za povˇsimnut´ı tak´e stoj´ı mnoˇzn´e ˇc´ıslo v n´azvu spoleˇcnosti. M´alokdo totiˇz v´ı (a m´alokoho to asi tak´e zaj´ım´a), ˇze kdyˇz si vychutn´av´a pivo znaˇcek jako je Bran´ık, Velvet, Kelt, Mˇeˇst’an, Ostravar nebo dokonce Stella Artois, tak se jedn´a o pivo stoˇcen´e na stejn´e lince jako Staropramen. Pˇrirozenˇe receptura se do urˇcit´e m´ıry u kaˇzd´e ze znaˇcek liˇs´ı, ale pivo vaˇr´ı stejn´ı lid´e. Dalo by se ˇr´ıci, ˇze tato spoleˇcnost produkuje jedin´ y v´ yrobek - pivo. Avˇsak od kaˇzd´e znaˇcky existuje mnoho variant. Vyr´abˇej´ı si piva s r˚ uznou koncentrac´ı mladiny1 , r˚ uzn´e tmavosti a v neposledn´ı ˇradˇe se st´aˇcej´ı do r˚ uzn´ ych obal˚ u (lahv´ı a sud˚ u r˚ uzn´ ych velikost´ı). Pˇri zahrnut´ı kombinac´ı vˇsech znaˇcek a variant jsou druh˚ u v´ yrobk˚ u stovky. Nˇekter´e jsou pˇrirozenˇe produkov´any ve v´ yraznˇe vˇetˇs´ıch objemech neˇz jin´e. ˇ e republice nejen do Pivovary Staropramen, a. s., prod´avaj´ı sv´e v´ yrobky po cel´e Cesk´ restaurac´ı, pivnic´ı a hospod, ale tak´e do hypermarket˚ u i menˇs´ıch obchod˚ u. D´ale jde v´ yznamn´a ˇc´ast produkce na export. Pro u ´ˇcely distribuce spoleˇcnost vlastn´ı, nebo si pronaj´ım´a, des´ıtky distribuˇcn´ıch center. Vyvst´av´a ot´azka, jak je tento kolos, dod´avaj´ıc´ı stovky produkt˚ u pˇres des´ıtky distribuˇcn´ıch ˇ e republiky a i mimo ni, ˇr´ızen? Pl´anov´an´ı je v tuto chv´ıli center do vˇsech kout˚ u Cesk´ 1
v´ yˇcepn´ı pivo 8-10% neboli stupˇ n˚ u, leˇz´ak 11-12,5%, speci´aln´ı v´ıce neˇz 12,5%
1
´ KAPITOLA 1. UVOD
2
znaˇcnˇe decentralizovan´e z hlediska zamˇeˇren´ı na r˚ uzn´e oblasti v´ yroby a logistiky a nen´ı takˇrka v˚ ubec automatizovan´e. C´ılem t´eto pr´ace je nab´ıdnout studii moˇznost´ı realizace centralizovan´eho optimalizaˇcn´ıho n´astroje logistiky Pivovar˚ u Staropramen, a. s., spoleˇcnˇe s n´avrhem ˇreˇsen´ı.
1.1
Struktura podniku a v´ yrobn´ıho procesu
Pˇrestoˇze v dneˇsn´ı dobˇe je trendem co nejv´ıce u ´kon˚ u nechat prov´adˇet stroje (to je u ´ˇcelem i t´eto pr´ace), v pivovaru je lidsk´ y prvek v urˇcit´e m´ıˇre nezbytn´ y - pˇredevˇs´ım ve spoˇ ım vˇetˇs´ı pod´ıl lidsk´e pr´ace na jen´ı s transportem (ˇridiˇci) a skladov´an´ım (jeˇstˇerk´aˇri). C´ v´ yrobn´ım procesu, t´ım sp´ıˇs nelze tento proces pˇresnˇe popsat. To je tak´e jeden z d˚ uvod˚ u, proˇc pro u ´ˇcely modelace a optimalizace pivovaru nen´ı tˇreba ve studiu jednotliv´ ych ˇc´ast´ı provozu zkoumat jejich podstatu pˇr´ıliˇs do hloubky, ale postaˇc´ı vystihnout chov´an´ı co nejvˇetˇs´ıch autonomn´ıch struktur2 . Tˇemito z´akladn´ımi ˇc´astmi v´ yrobn´ıho a distribuˇcn´ıho procesu jsou • v´ yrobn´ı linka, • sklad (distribuˇcn´ı centrum), • transport.
1.1.1
V´ yrobn´ı linka
Srdcem kaˇzd´eho pivovaru je pˇrirozenˇe varna piva. Pˇresto z hlediska logistiky je zbyteˇcn´e ji modelovat samostatnˇe. Staˇc´ı ji uvaˇzovat jako souˇc´ast v´ yrobn´ı linky. V´ yrobn´ı linka vˇsak nen´ı zcela korektn´ı term´ın. Pivo jako takov´e se nevyr´ab´ı na lince, ale vaˇr´ı ve varnˇe. Na lince se naopak st´aˇc´ı. Pˇresto pod pojmem v´ yrobn´ı linka bude v t´eto pr´aci myˇslena pr´avˇe varna, st´aˇcec´ı linka, pasterizaˇcn´ı a filtraˇcn´ı kolony a ostatn´ı ˇc´asti v´ yrobn´ıho provozu. K v´ yrobˇe samotn´eho piva je tˇreba r˚ uzn´ ych surovin - pˇredevˇs´ım jsou to voda, chmel, slad a kvasnice. Touto ˇc´ast´ı v´ yroby se vˇsak ani model, ani optimaliz´ator v r´amci t´eto pr´ace zab´ yvat nebude. D˚ uvodem je odliˇsn´ y ˇcasov´ y horizont pl´anov´an´ı z´avozu potravin´aˇrsk´ ymi 2
Tedy rozdˇelit logistiku na co nejvˇetˇs´ı celky, kter´e vˇsak jeˇstˇe funguj´ı nez´avisle.
´ ´IHO PROCESU 1.1. STRUKTURA PODNIKU A VYROBN
3
surovinami a snaha o rozdˇelen´ı probl´emu na menˇs´ı podprobl´emy, kter´e by bylo moˇzn´e ˇreˇsit samostatnˇe. Tato pr´ace si d´av´a za c´ıl ˇreˇsit pouze ˇc´asti provozu u ´zce souvisej´ıc´ı s logistikou.
Filtrace piva Samotn´a st´aˇcec´ı linka potˇrebuje k provozu pochopitelnˇe pivo ke st´aˇcen´ı a obaly k plnˇen´ı (sudy, lahve). Tato pr´ace bude pˇredpokl´adat, ˇze pivo ke stoˇcen´ı bude vˇzdy k dispozici. Takov´e zjednoduˇsen´ı je moˇzn´e prov´est pouze za pˇredpokladu, ˇze bude model obsahovat pouze jedinou st´aˇcec´ı linku (v tomto pˇr´ıpadˇe jedinou sudovou linku na praˇzsk´em Sm´ıchovˇe). Pokud by bylo zakomponov´ano linek v´ıce, pak by bylo nutn´e probl´em filtrace piva uvaˇzovat. N´apoj se pˇred stoˇcen´ım mus´ı profiltrovat (odstraˇ nuj´ı se pevn´e ˇc´astice a kvasnice). Pˇrefiltrovan´e pivo se uskladn´ı v k´ad´ıch a ˇcek´a na stoˇcen´ı. Kapacita tˇechto k´ad´ı je vˇsak omezen´a a proto je tˇreba koordinovat st´aˇcen´ı na r˚ uzn´ ych link´ach tak, aby se v ide´aln´ım pˇr´ıpadˇe na vˇsech st´aˇcelo stejn´e pivo (tˇrebaˇze do r˚ uzn´ ych obal˚ u).
1.1.2
Sklad
Skladov´an´ı je proces mnohem jednoduˇsˇs´ı neˇz v´ yroba. Z hlediska logistiky vˇsak pravdˇepodobnˇe nejv´ıce problematick´ y. Sklady maj´ı omezenou kapacitu a to pˇredevˇs´ım ten sm´ıchovsk´ y u st´aˇcec´ıch linek. Jedn´ım z d˚ uleˇzit´ ych faktor˚ u je cena skladov´an´ı ve smyslu blokace kapit´alu. Zdroje takto uloˇzen´e“ ve skladech nemohou b´ yt pouˇzity na dalˇs´ı pro” dukci, n´akup surovin apod. Ide´aln´ım stavem by tedy bylo, kdyby sklady mohly b´ yt neust´ale pr´azdn´e. Toho nelze doc´ılit, avˇsak snahou je co nejvˇetˇs´ı pˇribl´ıˇzen´ı. Skladov´an´ı lze rozdˇelit na prim´arn´ı a sekund´arn´ı - prim´arn´ı a sekund´arn´ı distribuˇcn´ı ˇ asteˇcnˇe mimo toto dˇelen´ı stoj´ı mal´e sklady u v´ centra. C´ yrobn´ıch linek, kter´e funguj´ı sp´ıˇse jako pˇrekladiˇstˇe. Prim´arn´ı distribuˇcn´ı centra slouˇz´ı pro uskladnˇen´ı z´asob (rezerv) a obal˚ u staˇzen´ ych z trhu. D´ale tak´e pro export. Sekund´arn´ı distribuˇcn´ı centra pak pro pˇr´ım´e z´asobov´an´ı z´akazn´ık˚ u. C´ılem je zav´aˇzet sekund´arn´ı distribuˇcn´ı centra (DC) pˇr´ımo od linky, avˇsak ne vˇzdy se to povede. V takov´em pˇr´ıpadˇe jsou produkty nejdˇr´ıvˇe dovezeny do prim´arn´ıho DC a teprve potom dopraveny do c´ılov´eho DC. T´ım vˇsak vznikaj´ı v´ıcen´aklady za dopravu.
´ KAPITOLA 1. UVOD
4
1.1.3
Transport
Pivovary Staropramen, a. s., t´emˇeˇr v´ yhradnˇe vyuˇz´ıvaj´ı sluˇzeb extern´ıch autodopravc˚ u. Na kaˇzdou cestu je tak tˇreba objednat n´akladn´ı v˚ uz s urˇcit´ ym pˇredstihem. Pˇritom nehraje roli, zda se jedn´a o cestu jednosmˇernou a nebo obousmˇernou, kdy se rovnou naloˇz´ı v´ yrobky nebo obaly na cestu zpˇet. Autodopravce si vyuˇzit´ı kamionu v pˇr´ıpadˇe jednosmˇern´e cesty zajist´ı s´am. Kaˇzd´ y druh n´akladn´ıho vozu m´a urˇcit´ y poˇcet paletov´ ych m´ıst, pˇriˇcemˇz z´aleˇz´ı na konkr´etn´ı pˇrev´aˇzen´e komoditˇe, jak´e jej´ı mnoˇzstv´ı jedno paletov´e m´ısto pojme. R˚ uzn´e druhy obal˚ ua produkt˚ u maj´ı r˚ uzn´e moˇznosti vrˇsen´ı palet na sebe z d˚ uvod˚ u pevnosti obal˚ u. Maxim´aln´ı naloˇzen´ı se m˚ uˇze liˇsit i u jednotliv´ ych tras - napˇr´ıklad kolem Sm´ıchova je povoleno jezdit jen automobil˚ um do urˇcit´e v´ahy. Zde je tedy moˇzn´e naloˇzit na v˚ uz mnohem v´ıce palet pr´azdn´ ych obal˚ u neˇz hotov´ ych produkt˚ u t´ehoˇz typu.
1.2
Postup ˇ reˇ sen´ı
Tato sekce shrnuje proces tvorby optimaliz´atoru do jednotliv´ ych etap, podle kter´ ych budou koncipov´any n´asleduj´ıc´ı kapitoly a struˇcnˇe je popisuje. D´ale zmiˇ nuje pˇr´ıpravn´e pr´ace tomuto procesu pˇredch´azej´ıc´ı. Myˇslenka tvorby optimaliz´atoru logistick´ ych proces˚ u v Pivovarech Staropramen, a. s., se zrodila jiˇz pˇred nˇekolika lety, kdy Ing. Jiˇr´ı Roubal Ph.D. ve spolupr´aci s Ing. Jaroslavem Hlavatou z Pivovar˚ u Staropramen, a. s., vypsal bakal´aˇrsk´e t´ema t´ ykaj´ıc´ı se prozat´ım pouze modelace. Tehdy vznikla pr´ace postihuj´ıc´ı z´akladn´ı problematiku [2], kterou jsem se o rok poˇzdeji pokusil rozˇs´ıˇrit a doplnit [1]. Pˇred rokem, kdy byly kontakty s Pivovary Staropramen, a. s., opˇet obnoveny za uˇcelem v´ yvoje optimaliz´atoru, bylo z d˚ uvodu zmˇen v podniku rozhonuto model do urˇcit´e m´ıry pˇrepracovat. Zmˇeny postihly i management podniku, ale naˇstˇest´ı nikoliv z hlediska vstˇr´ıcnosti kontaktn´ıch osob. V´ yvoj lze rodˇelit do 4 f´az´ı: 1. Z´ısk´an´ı informac´ı o distribuˇcn´ım procesu nutn´ ych pro tvorbu modelu. 2. Z´ısk´an´ı informac´ı o pl´anovac´ım procesu potˇrebn´ ych pro tvorbu optimaliz´atoru. 3. Tvorba a verifikace modelu - kap. 3.
ˇ SEN ˇ ´I 1.2. POSTUP RE
5
4. Tvorba optimaliz´atoru - kap. 4. Informace o distribuˇcn´ım procesu byly z vˇetˇs´ı ˇc´asti pˇrevzaty z p˚ uvodn´ı pr´ace [1]. Byly doplnˇeny o nov´e poznatky a podle potˇreby upraveny pro st´avaj´ıc´ı podobu struktury Pivovar˚ u Staropramen, a. s. Sloˇzitˇejˇs´ı u ´lohou se uk´azalo z´ısk´an´ı dat potˇrebn´ ych pro verifikaci modelu. Protoˇze je spoleˇcnost souˇc´ast´ı mezin´arodn´ı korporace, pouˇz´ıv´a softwarov´e prostˇredky spoleˇcn´e vˇsem ˇclen˚ um skupiny Inbev. Tyto aplikace jsou na m´ıru pˇrizp˚ usoben´e intern´ım potˇreb´am, avˇsak jejich flexibilita je v podstatˇe nulov´a. Podnˇet na u ´pravu klientsk´e aplikace pro ˇcten´ı z podnikov´e datab´aze byl vstˇr´ıcnˇe vyslyˇsen, ale protoˇze spr´avy tˇechto technologi´ı s´ıdl´ı po cel´e Evropˇe, bylo z ˇcasov´ ych d˚ uvod˚ u v´ yhodnˇejˇs´ı potˇrebn´a data ruˇcnˇe opsat. V t´eto pr´aci je poprv´e pˇredstaven n´avrh optimalizaˇcn´ıho n´astroje a proto hlavn´ım c´ılem druh´e f´aze bylo co nejlepˇs´ı pochopen´ı souˇcasn´eho pl´anovac´ıho procesu. Za t´ımto u ´ˇcelem bylo sjedn´ano mnoho sch˚ uzek s r˚ uzn´ ymi osobami zodpovˇedn´ ymi za tvorbu pl´anu. Data pouˇz´ıvan´a pˇri ruˇcn´ım pl´anov´an´ı jsou v lepˇs´ım pˇr´ıpadˇe pˇr´ıstupn´a ve formˇe excelovsk´ ych tabulek v horˇs´ım pomoc´ı klienta podnikov´eho informaˇcn´ıho syst´emu (SAPu). Bylo proto potˇreba vytvoˇrit znaˇcn´e mnoˇzstv´ı skript˚ u, jejichˇz jedin´ ym u ´kolem bylo naˇc´ıtat data do vhodnˇejˇs´ıho form´atu. Pro efektivn´ı vyuˇzit´ı optimalizaˇcn´ıho n´astroje bude pˇrirozenˇe potˇreba pˇr´ım´e napojen´ı na datab´azi. Data a informace vyuˇz´ıvan´e pro tvorbu pl´an˚ u logistiky budou pops´any v kap. 4. Posledn´ı dvˇe f´aze v´ yvoje zpracov´avaj´ı z´ıskan´e informace. V kap. 3 je nejprve pops´ana dekompozice struktury logistiky a jednotliv´e ˇc´asti modelov´any zvl´aˇst’, pot´e je vytvoˇren celkov´ y model a ten verifikov´an. Obsahem kap. 4 pak je tak´e popis r˚ uzn´ ych metod optimalizace a v´ ybˇer t´e nejvhodnˇejˇs´ı, d´ale integrace modelu do optimaliz´atoru a vyhodnocen´ı optimalizace pomoc´ı r˚ uzn´ ych logistikc´ ych sc´en´aˇr˚ u. Obsah kap. 2 slouˇz´ı jako kr´atk´ yu ´vod do problematiky modelov´an´ı, ˇr´ızen´ı a optimalizace.
6
´ KAPITOLA 1. UVOD
Kapitola 2 O modelov´ an´ı, ˇ r´ızen´ı a optimalizaci Protoˇze z´akladn´ım pˇredpokladem pro u ´spˇeˇsnou komunikaci se zadavatelem bylo vz´ajemn´e pochopen´ı ve smyslu spr´avn´e interpretace r˚ uzn´ ych pojm˚ u, jako napˇr. model, optimaliz´ator, vstup, v´ ystup apod., bude dalˇs´ı sekce vˇenov´ana struˇcn´emu vysvˇetlen´ı z´akladn´ıch pojm˚ u t´ ykaj´ıc´ıch se modelov´an´ı.
2.1
O modelov´ an´ı
Pojem model v elektroinˇzen´ yrsk´e terminologii pˇredstavuje matematick´ y popis obvykle tvoˇren´ y mnoˇzinou diferenci´aln´ıch ˇci diferenˇcn´ıch rovnic popisuj´ıc´ıch dynamick´e chov´an´ı procesu [3]. Model lze z´ıskat pomoc´ı vyj´adˇren´ı fyzik´aln´ı podstaty procesu, pˇr´ıpadnˇe zkoum´an´ım odezvy modelovan´eho syst´emu na vhodn´e vstupn´ı pr˚ ubˇehy. V pˇr´ıpadˇe logistiky pivovaru pˇripad´a v u ´vahu sp´ıˇse fyzik´aln´ı odvozen´ı modelu1 . Modelov´an´ım vytv´aˇr´ıme matematick´e struktury, jejichˇz c´ılem je co nejvˇernˇeji simulovat chov´an´ı nˇejak´eho re´aln´eho procesu. Speci´aln´ı podmnoˇzinou matematick´ ych model˚ u jsou modely line´arn´ı, tedy takov´e jejichˇz stavebn´ımi prvky jsou pouze: • vstupn´ı veliˇciny, • v´ ystupn´ı veliˇciny, 1
Ve spojen´ı s logistikou m˚ uˇze slovo fyzik´ aln´ı“ zn´ıt nepatˇriˇcnˇe, ale vzhledem k tomu, ˇze fyzika je v pod” statˇe aplikovan´a matematika s u ´ˇcelem popisovat rozliˇcn´e jevy naˇseho svˇeta, nen´ı d˚ uvod toto oznaˇcen´ı povaˇzovat za nevalidn´ı.
7
´ ´I, R ˇ ´IZEN´I A OPTIMALIZACI KAPITOLA 2. O MODELOVAN
8 • stavov´e veliˇciny,
• line´ arn´ı diferenci´aln´ı rovnice prvn´ıho ˇr´adu, • v´ ystupn´ı line´arn´ı algebraick´a rovnice.
Je moˇzn´e uv´est, ˇze line´arn´ı modely popisuj´ı line´arn´ı procesy v naˇsem svˇetˇe. Toto tvrzen´ı vˇsak nar´aˇz´ı na fakt, ˇze v naˇsem vesm´ıru pravdˇepodobnˇe neexistuje ˇz´adn´ y re´aln´ y line´arn´ı syst´em (snad jen syst´em trivi´aln´ı). Ve skuteˇcnosti line´arn´ı modely popisuj´ı syst´emy, jejichˇz chov´an´ı se k line´arn´ımu bl´ıˇz´ı, pˇr´ıpadnˇe se linearita pˇr´ıliˇs neprojevuje v ˇz´adan´e pracovn´ı oblasti. D˚ uleˇzitou vlastnost´ı line´arn´ıch model˚ u je snazˇs´ı aplikace ˇr´ıd´ıc´ıch syst´em˚ u. Typick´ y tvar matematick´eho popisu spojit´eho2 line´arn´ıho ˇcasovˇe invariantn´ıho3 syst´emu je ˙ x(t) = Ax(t) + Bu(t),
(2.1)
y(t) = Cx(t) + Du(t),
(2.2)
kde vektory x, u a y jsou stavov´e, vstupn´ı a v´ ystupn´ı veliˇciny respektive a matice A, B, C a D jsou matice syst´emu, ˇr´ızen´ı a dvˇe v´ ystupn´ı matice respektive. V´ yznam veliˇcin stavov´eho popisu syst´emu je inlustrov´an na obr. 2.1.
D u(t)
B
∫
x(t)
C
y(t)
A Obr´azek 2.1: Blokov´e sch´ema stavov´eho popisu syst´emu
2 3
V tomto u ´vodu k modelov´ an´ı se pro jednoduchost budeme zab´ yvat pouze spojit´ ymi syst´emy. Matice syst´emu jsou konstantn´ı, tj. parametry syst´emu se ˇcasem nemˇen´ı.
´ ´I 2.1. O MODELOVAN
2.1.1
9
Vstupn´ı a v´ ystupn´ı veliˇ ciny
Model syst´emu je urˇcen pro pozorov´an´ı dynamick´eho chov´an´ı syst´emu, tedy sledov´an´ı v´ ystupn´ıch veliˇcin za urˇcit´ ych hodnot vstupn´ıch veliˇcin (jin´ ymi slovy odezvy syst´emu na urˇcit´e vstupy). Vstupn´ı veliˇcinou je funkce akˇcn´ıho z´asahu (vnˇejˇs´ı z´asah do syst´emu). V´ ystupn´ı veliˇcinou m˚ uˇze b´ yt opˇet konstanta nebo funkce, jej´ı pr˚ ubˇeh je z´avisl´ y na vstupn´ıch veliˇcin´ach a stavech syst´emu. Fyzicky je v´ ystupn´ı veliˇcinou takov´a, kterou je moˇzn´e mˇeˇrit. Pˇr´ıkladem v´ ystupn´ı veliˇciny m˚ uˇze b´ yt ujet´a vzd´alenost automobilem, pˇriˇcemˇz vstupem je seˇsl´apnut´ı plynu.
2.1.2
Stavov´ e veliˇ ciny
Stavov´e veliˇciny lze vysvˇetlit pokraˇcov´an´ım pˇr´ıkladu automobilu. Na ten p˚ usob´ı ve zjednoduˇsen´ı dvˇe s´ıly • v´ ykon motoru pˇrenesen´ y pˇres pˇrevodov´e u ´stroj´ı a n´apravu na kola, • odporov´a s´ıla vzduchu u ´mˇern´a rychlosti vozidla4 . Seˇsl´apnut´ım ped´alu plynu zv´ yˇs´ıme zrychlen´ı automobilu, avˇsak jak bude nar˚ ustat rychlost, zrychlen´ı bude klesat v d˚ usledku odporu vzduchu podle [3] ma(t) = −bv(t) + u(t).
(2.3)
Pˇritom a je zrychlen´ı automobilu, m je hmotnost automobilu, b je koeficient aerodynamick´eho odporu vozidla, v je jeho rychlost a u je s´ıla p˚ usob´ıc´ı na automobil (´ umˇern´a seˇsl´apnut´ı plynu). Vztah (2.3) plyne z druh´eho Newtonova z´akonu - z´akonu s´ıly F = ma.
(2.4)
Rychlost automobilu bude vnitˇrn´ım stavem syst´emu a jeho integrac´ı podle ˇcasu z´ısk´ame ujetou vzd´alenost x(t) , tedy v´ ystup syst´emu, kter´ y lze snadno mˇeˇrit. Stavov´ y popis (2.2) takto zjedoduˇsen´eho modelu m´a tvar v(t) ˙ = − mb v(t) +
1 m
u(t),
x(t) ˙ = v(t), y(t) = x(t), 4
Ve skuteˇcnosti je odpor vzduchu u ´mˇern´ y kvadr´ atu rychlosti.
(2.5)
´ ´I, R ˇ ´IZEN´I A OPTIMALIZACI KAPITOLA 2. O MODELOVAN
10
kde u(t) je vstupn´ı veliˇcina vyjadˇruj´ıc´ı m´ıru seˇsl´apnut´ı plynov´eho ped´alu a y(t) je v´ ystupn´ı veliˇcina, kter´a se rovn´a vozem uraˇzen´e vzd´alenosti.
2.1.3
Parametry syst´ emu
Pˇr´ıkladem parametru je v´aha vozu a jeho koeficient aerodynamick´eho odporu v (2.2). Hodnoty parametr˚ u modelu do urˇcit´e m´ıry ovlivˇ nuj´ı jeho chov´an´ı, avˇsak nemaj´ı vliv na vlastn´ı strukturu modelu. Jedn´a se obvykle o koeficienty rovnic syst´emu.
2.2
O optimalizaci
V kap. 2.1 byl uveden pˇr´ıklad line´arn´ıho modelu (2.5) pohybuj´ıc´ıho se automobilu. Na tomto dynamick´em syst´emu bude v t´eto sekci osvˇetlena souvislost pojm˚ u model, ˇr´ıdic´ı syst´em a optimaliz´ator. Pokud se automobil pohybuje rychlost´ı v1 a ˇridiˇc potˇrebuje zrychlit na rychlost v2 provede to za pomoc´ı plynov´eho ped´alu a sv´e zkuˇsenosti s ovl´ad´an´ım vozu. Avˇsak v l´epe vybaven´ ych vozech m´a moˇznost pouˇz´ıt tempomat - ˇridic´ı syst´em (regul´ator), kter´ y zmˇenu rychlosti provede za nˇej. Avˇsak je obvykl´e, ˇze na pr˚ ubˇeh zmˇeny rychlosti jsou kladeny urˇcit´e poˇzadavky, napˇr´ıklad: • okamˇzit´a spotˇreba vozu mus´ı b´ yt co nejniˇzˇs´ı, • zrychlen´ı mus´ı probˇehnout za co nejkratˇs´ı dobu, • zrychlen´ı nesm´ı pˇrekroˇcit m´ıru komfortu, • zrychlen´ı mus´ı probˇehnout co nejplynuleji. Kaˇzd´ y z tˇechto poˇzadavk˚ u lze ohodnotit urˇcitou cenou a sjednotit do celkov´e krit´eri´aln´ı ˇ ıdic´ı syst´em, kter´ funkce. Je zˇrejm´e, ˇze jednotliv´e poˇzadavky jsou ˇcasto protich˚ udn´e. R´ y pˇri regulaci zohledˇ nuje hodnotu krit´eria (maximalizuje, minimalizuje), m˚ uˇzeme naz´ yvat optimaliz´atorem.
Kapitola 3 Model logistiky Jak uˇz bylo uvedeno v u ´vodn´ı kapitole, probl´em logistiky Pivovar˚ u Staropramen, a. s., lze dekomponovat do tˇr´ı podprobl´em˚ u - v´ yroby, skladov´an´ı a transportu. Kaˇzd´a z tˇechto ˇc´ast´ı lze popsat samostatnˇe a model cel´e logistiky lze pot´e zkonstruovat uˇzit´ım tˇechto podmodel˚ u.
3.1
Z´ akladn´ı ustanoven´ı
Model zahrnuje mp v´ yrobk˚ u a mc obal˚ u. Vˇetˇsina veliˇcin modelu bude tedy vektorov´a ve tvaru
x (t) =
p1 (t)
pmp (t) , c1 (t) c2 (t) .. . cmc (t) p2 (t) .. .
(3.1)
kde pi a ci znaˇc´ı veliˇcinu (mnoˇzstv´ı, tok apod.) pˇr´ısluˇsej´ıc´ı i-t´emu v´ yrobku a obalu respektive. Sjednocen´ı produkt˚ u a obal˚ u do jednoho vektoru o d´elce m = mp + mc je v´ yhodn´e z hlediska mnoˇzstv´ı promˇenn´ ych a pˇrehlednosti modelu. U tansportu a skladov´an´ı totiˇz neexistuje takov´ y rozd´ıl v zach´azen´ı mezi obaly a produkty, jako u linky, kde by rozdˇelen´ı 11
12
KAPITOLA 3. MODEL LOGISTIKY
smysl mˇelo, ale nen´ı nutn´e. Dalˇs´ı ot´azkou jsou jednotky mnoˇzstv´ı produkt˚ u a obal˚ u, se kter´ ymi bude model pracovat. Nab´ız´ı se tyto moˇznosti: • kus - ks, • paleta - PAL, • hektolitr - hl. Kaˇzd´a z tˇechto jednotek m´a sv´e v´ yhody v urˇcit´ ych oblastech modelu. Poˇc´ıt´an´ı po kusech je vhodn´e zejm´ena pro v´ yrobu - pracovn´ı rychlost linky je ud´av´ana v obalech za hodinu a produkty i obaly na lince fyzicky vystupuj´ı po jednotliv´ ych kusech. Nev´ yhodou naopak jsou velk´e rozd´ıly faktick´eho mnoˇzstv´ı n´apoje mezi jednotliv´ ymi v´ yrobky (napˇr. pades´atilitrov´ y sud je ekvivalentem sta lahv´ı). Tato jednotka tak´e nic neˇr´ık´a o velikosti m´ısta zabran´eho ve skladˇe. Paleta je oproti kusu v´ yhodnˇejˇs´ı z hlediska skladov´an´ı a transportu. Tyto dvˇe oblasti logistiky poˇc´ıtaj´ı s paletov´ ymi m´ısty. Probl´emem ovˇsem je, ˇze na jedno paletov´e m´ısto lze r˚ uzn´e v´ yrobky vrˇsit r˚ uznˇe (je d´an maxim´aln´ı poˇcet pater). Paleta jako jednotka tedy d´av´a r´amcov´ y pˇrehled, kolik m´ısta na skladˇe dan´a jednotka zabere, ovˇsem st´ale ne pˇresnˇe. Pouˇzit´ım hektolitru jako jednotky nez´ısk´ame informaci ani o potˇrebn´em skladovac´ım prostoru, ani o rychlosti v´ yroby. V´ yhodou poˇc´ıt´an´ı s hektolitry je pˇresn´e definovan´ı mnoˇzstv´ı v´ yrobk˚ u. Z tohoto d˚ uvodu se tak´e jedn´a o jednotku, se kterou pracuj´ı v Pivovarech Staropramen, a. s. Pˇrirozenˇe je moˇzn´e tak´e tyto jednotky kombinovat a v pˇr´ıpadˇe potˇreby pˇrepoˇc´ıt´avat. Ve skuteˇcnosti to bude nutn´e, nebot’ zadavatel poˇzaduje informace o mnoˇzstv´ıch v hektolitrech. Protoˇze z hlediska modelov´an´ı se nejv´ yhodnˇejˇs´ı jev´ı poˇc´ıt´an´ı po kusech, bude tˇreba na vstupu a na v´ ystupu modelu pˇrepoˇc´ıt´avat.
3.2
St´ aˇ cec´ı linka
St´aˇcec´ı linky pouˇz´ıvan´e v pivovarech se liˇs´ı nejen sv´ ymi parametry, jako jsou kapacita, dopravn´ı zpoˇzden´ı, pˇr´ıpadnˇe doba n´abˇehu, ale tak´e sv´ ym u ´ˇcelem. Existuj´ı dva hlavn´ı typy
´ CEC ˇ ´I LINKA 3.2. STA
13
linek a to jsou linky sudov´e (kegov´e) a linky lahvov´e. Tento model se bude nejprve zab´ yvat pouze sudov´ ymi linkami, avˇsak z pohledu logistiky mezi tˇemito typy nen´ı principi´aln´ı rozd´ıl, liˇs´ı se sp´ıˇse v parametrech. V n´asleduj´ıc´ım textu tedy bude pod slovem linka vˇzdy m´ınˇena kegov´a, avˇsak vˇetˇsinu poznatk˚ u lze aplikovat na lahvovou linku tak´e. Linka je z´asobov´ana ze dvou zdroj˚ u - pivem z tank˚ u a obaly ze skladu. Tento model pˇredpokl´ad´a, ˇze pivo ke stoˇcen´ı je vˇzdy k dispozici. Staˇc´ı proto, kdyˇz model postihne pouze toky produkt˚ u a obal˚ u mezi linkou a skladem. Linka produkuj´ıc´ı urˇcit´ y v´ yrobek odeb´ır´a z pˇrilehl´eho skladu pˇr´ısluˇsn´e obaly a suroviny.
pa
ra m
et
ry
Model podle obr. 3.1 m´a jednu vstupn´ı veliˇcinu, dvˇe v´ ystupn´ı a nˇekolik parametr˚ u.
p(t) l(t) c(t) Linka Obr´azek 3.1: Blokov´e sch´ema modelu st´aˇcec´ı linky
3.2.1
Vstupn´ı a v´ ystupn´ı veliˇ ciny modelu linky
V´ yrobn´ı linka m´a jednu vstupn´ı veliˇcinu, kter´a urˇcuje zda je linka v dan´ y ˇcasov´ y okamˇzik pro urˇcit´ y v´ yrobek zapnuta. V´ ystupn´ı veliˇcinou je tok produkt˚ u z linky a tok obal˚ u na linku (podle (3.1) v jednom vektoru). V n´asleduj´ıc´ıch odstavc´ıch budou vstupn´ı a v´ ystupn´ı veliˇciny rozebr´any.
14
KAPITOLA 3. MODEL LOGISTIKY
V´ yrobn´ı vektor Aktu´aln´ı v´ yrobn´ı vektor l(t) je podle (3.1) tvaru l1 (t) l2 (t) .. . l (t) = lmp (t) 0 .. . 0
,
(3.2)
kde mp je poˇcet produkt˚ u, kter´e model postihuje. Vektor m´a m prvk˚ u, z toho mc nul, nebot’ obaly nelze na lince produkovat. Hodnota li (t) ud´av´a, zda linka st´aˇc´ı v´ yrobek s indexem i, pˇriˇcemˇz li (t) = {0; 1} (hodnota 1 znaˇc´ı produkci pˇr´ısluˇsn´eho v´ yrobku, hodnota 0 opak) a plat´ı podm´ınka, ˇze se sm´ı vyr´abˇet pouze jeden produkt v dan´ y okamˇzik, tedy mp X
li (t) ≤ 1.
(3.3)
i=1
Tok v´ yrobk˚ u a obal˚ u Tato v´ ystupn´ı veliˇcina lze rozdˇelit do dvou ˇc´ast´ı - vektor toku v´ yrobk˚ u z linky p(t) o rozmˇeru mp a vektor toku obal˚ u c(t) na linku o rozmˇeru mc : p (t) c (t) 1 1 p2 (t) c2 (t) p (t) = c (t) = , . .. .. . pmp (t) cmc (t) Tok v´ yrobk˚ u a obal˚ u sl (t) o rozmˇeru m pak m´a tvar sl1 (t) " # sl (t) p (t) 2 sl (t) = . = .. c (t) . slm (t)
.
(3.4)
Vektor sl (t) vyjadˇruje okamˇzitou spotˇrebu obal˚ u a okamˇzitou produkci v´ yrobk˚ u v
ks h
.
Hodnoty vektoru p(t) jsou proto nez´aporn´e, naopak hodnoty vektoru c(t) jsou nekladn´e. Opˇet plat´ı podm´ınka, ˇze sm´ı b´ yt produkov´an pouze jeden v´ yrobek v dan´ y okamˇzik.
´ CEC ˇ ´I LINKA 3.2. STA
3.2.2
15
Parametry modelu linky
Paramtery modelu linky lze rozdˇelit na extern´ı a intern´ı. Ty extern´ı plynou z re´aln´ ych parametr˚ u syst´emu a jsou to • matice receptury, • nomin´aln´ı kapacita linky, • efektivita linky, • dopravn´ı zpoˇzdˇen´ı linky, • doba n´abˇehu a odstaven´ı linky, • produkˇcn´ı ztr´aty. Intern´ım parametrem je doba pˇrekryvu v´ yroby a plyne z vnitˇrn´ı struktury modelu, tedy zp˚ usobu popisu syst´emu.
Matice receptury Je tˇreba definovat, jak´e obaly se spotˇrebov´avaj´ı pˇri produkci urˇcit´eho v´ yrobku. Toto ud´av´a matice receprury RE o rozmˇeru m × m definovan´a
rE11
rE12 · · ·
rE 21 rE22 RE = . .. rEm1
rE1m
... rEmm
.
(3.5)
Kaˇzd´ y ˇr´adek i matice RE ud´av´a v jednotliv´ ych sloupc´ıch kolik kus˚ u j-t´eho obalu je na jeden kus i-t´eho v´ yrobku tˇreba. Plat´ı podm´ınky o nekladnosti prvk˚ u matice a o nulovosti prvk˚ u pˇr´ısluˇsej´ıc´ıch spotˇrebˇe produkt˚ u, tedy: r Eij ≤ 0, r Eik = 0 , k = {0, 1, . . . , mp } .
16
KAPITOLA 3. MODEL LOGISTIKY
Nomin´ aln´ı kapacita Kaˇzd´a linka m´a urˇcitou maxim´aln´ı kapacitu, tedy mnoˇzstv´ı obal˚ u za hodinu, kter´e je za ide´aln´ıch podm´ınek schopna naplnit. Protoˇze pro kaˇzd´ y v´ yrobek m˚ uˇze b´ yt kapacita linky r˚ uzn´a, je definov´ana matice nomin´aln´ıch kapacit o rozmˇeru m × m cnom1 0 ··· 0 0 c nom 2 C nom = . , ... .. 0 cnomm
(3.6)
coˇz je diagon´aln´ı matice a hodnota prvku cnomi pˇr´ısluˇs´ı nomin´aln´ı kapacitˇe linky pˇri
produkci i-t´eho v´ yrobku a obalu. Kapacity pˇr´ısluˇsej´ıc´ı obal˚ um jsou ovˇsem nulov´e, plat´ı tedy cnomk = 0, k = {mp , mp + 1, mp + 2, . . . , mp + mc } . Potˇreba diagonality pramen´ı z nutnosti n´asobitelnosti v´ yrobn´ım vektorem.
Efektivita Maxim´aln´ı kapacity nelze dos´ahnout, proto se definuje kapacita efektivn´ı. Ta v pomˇern´ ych hodnot´ach ud´av´a, na kolik se kapacita linky bl´ıˇz´ı nomin´aln´ı hodnotˇe. Veliˇcina zahrnuje pravdˇepodobnost nepl´anovan´ ych odst´avek z d˚ uvodu technick´e poruchy, zaseknut´eho obalu, lidsk´e chyby apod. Definuje se podobnˇe jako nomin´aln´ı kapacita ve formˇe diagon´aln´ı matice (opˇet z d˚ uvod˚ u n´asobitelnosti) o rozmˇeru m × m c 0 ··· 0 ef1 0 cef 2 C ef = . . . . . . . 0 cefm
(3.7)
Hodnota prvku cefi pˇr´ısluˇs´ı efektivn´ı kapacitˇe linky pˇri produkci i-t´eho v´ yrobku. Kapacity
pˇr´ısluˇsej´ıc´ı obal˚ um by mˇely b´ yt nulov´e1 , plat´ı tedy cefk = 0, k = {mp , mp + 1, mp + 2, . . . , mp + mc } . 1
Nen´ı to vˇsak nutn´e, pokud jsou nulov´e pˇr´ısluˇsn´e nomin´ aln´ı kapacity.
´ CEC ˇ ´I LINKA 3.2. STA
17
Dopravn´ı zpoˇ zdˇ en´ı Jedn´a se o ˇcasov´ y interval ud´avan´ y v hodin´ach od naloˇzen´ı obalu na p´as linky po odebr´an´ı hotov´eho v´ yrobku. D´a se pˇredpokl´ad´at, ˇze velikost zpoˇzdˇen´ı je stejn´a pro vˇsechny produkty. Plat´ı Td > 0.
Doba n´ abˇ ehu a odstaven´ı Vlastnost´ı sudov´e linky je pozvoln´ y n´abˇeh zp˚ usoben´ y postupn´ ym naj´ıˇzdˇen´ım jednotliv´ ych plnic´ıch ramen. Obdobnˇe prob´ıh´a odstaven´ı linky. Plnic´ı ramena nab´ıhaj´ı stejn´ ym zp˚ usobem bez ohledu na plnˇen´ y obal, lze tedy opˇet tento parametr prohl´asit za skal´ar znaˇcen´ y Tn s vlastnost´ı Tn > 0.
Produkˇ cn´ı ztr´ aty Pˇri v´ yrobˇe doch´az´ı k opotˇreben´ı obal˚ u, palet apod. V matematick´em popisu jsou tyto zr´aty vyj´adˇreny pomoc´ı matice ztr´at W , kter´a m´a tvar w 0 ··· 0 1 0 w2 W = . ... .. 0 wm
.
(3.8)
Hodnota prvku wi je pomˇern´a hodnota ztr´at pˇri v´ yrobˇe i-t´eho v´ yrobku. Plat´ı tedy 0 ≤ wi < 1.
Matice ztr´at popisuje frekvenci jevu, kdy pˇri spotˇrebov´an´ı obalu nedojde k produkci. Doba pˇ rekryvu v´ yroby Obal str´av´ı na lince ˇr´adovˇe p˚ ul hodiny. Je proto moˇzn´e pˇri zmˇenˇe v´ yroby z produktu p1 na produkt p2 zaˇc´ıt zav´aˇzet linku obaly potˇrebn´ ymi pro st´aˇcen´ı produktu p2 jeˇstˇe
18
KAPITOLA 3. MODEL LOGISTIKY
pˇred opuˇstˇen´ım linky posledn´ım kusem v´ yrobku p1 . Doba pˇrekryvu To urˇcuje, jak dlouho budou na lince dva druhy obal˚ u (at’ uˇz naplnˇen´e, ˇci pr´azdn´e).
3.2.3
Z´ akladn´ı vztahy
Nejjednoduˇsˇs´ım zp˚ usobem lze linku popsat jako n´asobiˇcku. Vstupn´ı sign´al je vˇzdy bin´arn´ı, tedy vektor obd´eln´ıkov´ ych pr˚ ubˇeh˚ u, pˇriˇcemˇz prvky vektoru nab´ yvaj´ı hodnot 0 nebo 1. Uk´azka vstupn´ıho pr˚ ubˇehu l(t) pro tˇri v´ yrobky je na obr. 3.2(a). V´ ystupn´ı sign´al sl (t) z´ısk´ame podle vztahu p (t) = C nom C ef (I − W ) l (t − Td )
(3.9)
c(t) = −RE T C nom C ef l(t)
(3.10)
pro vektor produkt˚ ua
pro vektor obal˚ u. Spojen´ım tˇechto dvou v´ yraz˚ u z´ısk´ame " # l (t − Td ) sl (t) = L , l (t) kde matice L je definov´ana " L=
C nom C ef (I − W )
0
0
RE T C nom C ef
(3.11)
#
,
(3.12)
kde I je jednotkov´a matice a 0 je nulov´a matice pˇr´ısluˇsn´ ych dimenz´ı. V´ ystupn´ı tok produkt˚ u a obal˚ u p(t) m´a opˇet obd´eln´ıkov´ y charakter a liˇs´ı se od l(t) amplitudou a zpoˇzdˇen´ım, coˇz je uk´az´ano na obr. 3.2(b). Tyto vztahy popisuj´ı z´akladn´ı model v´ yrobn´ı linky. Pokud bychom chtˇeli zahrnout i sloˇzitˇejˇs´ı aspekty chov´an´ı linky, jako n´abˇeˇzn´e a sestupn´e hrany pˇri rozjezdu a odstaven´ı linky, nebo sn´ıˇzen´ı efektivity pˇri zmˇen´ach v´ yroby (zmˇena obalu nebo v´ yrobku), museli bychom model v´ yraznˇe rozˇs´ıˇrit. Moˇznosti takov´eho rozˇs´ıˇren´ı budou uvedeny v n´asleduj´ıc´ı sekci.
3.2.4
Rozˇ s´ıˇ ren´ı modelu
N´abˇeh linky neprobˇehne okamˇzitˇe, ale efektivita se zvyˇsuje postupnˇe. Pozvolnou n´abˇeˇznou a sestupnou hranu lze simulovat transformac´ı obd´eln´ıkov´eho sign´alu na lichobˇeˇzn´ıkov´ y, nebo syst´emem druh´eho ˇr´adu.
´ CEC ˇ ´I LINKA 3.2. STA
19
4
x 10 9 10° 50L KEG 12° 50L KEG 10° 30L KEG
1
10° 50L KEG 12° 50L KEG 10° 30L KEG
8 7
tok produktu [ks/h]
0.6
0.4
6 5 4 3 2
0.2
1 0 0
1
2
3
4
5
6
7
0 0
8
1
2
3
4
5
6
cas [h]
cas [h]
(a) Vstupn´ı sign´ al l(t)
(b) Tok produkt˚ u p(t)
4
0
x 10
50L KEG 30L KEG
−1 −2
tok obalu [ks/h]
stav linky [−]
0.8
−3 −4 −5 −6 −7 −8 −9 0
1
2
3
4
5
6
7
8
cas [h]
(c) Tok obal˚ u c(t)
Obr´azek 3.2: Uk´azkov´e pr˚ ubˇehy vstupn´ıch a v´ ystupn´ıch veliˇcin modelu linky
7
8
20
KAPITOLA 3. MODEL LOGISTIKY
Aproximace lichobˇ eˇ zn´ıkem Vztahy (3.9) a (3.10) je tˇreba upravit tak, aby n´abˇeˇzn´e a sestupn´e hrany obd´eln´ıkov´eho pr˚ ubˇehu byly pozvoln´e. C´ılem je sign´al r(t) transformovat do sign´alu z(t) pˇribliˇznˇe lichobˇeˇzn´ıkov´eho, coˇz je zn´azornˇeno na obr. 3.3.
1
stav linky [−]
0.8
0.6
0.4
0.2
0 T0
T0 + Tn
cas [−]
T1
T1 + Tn
Obr´azek 3.3: Transformace obd´eln´ıkov´eho sign´alu na sign´al lichobˇeˇzn´ıkov´ y
N´abˇeˇznou hranu lichobˇeˇzn´ıku z(t) lze z´ıskat integrac´ı obd´eln´ıkov´eho sign´alu r(t), ˇc´ımˇz bychom ovˇsem z´ıskali neklesaj´ıc´ı funkci. Je tˇreba, aby platilo lim r(t) = lim z(t)
t→∞
t→∞
(3.13)
a Z
∞
Z
∞
z (t)dt.
(3.14)
z˙ (t) = r (t) − r (t − Tn ) .
(3.15)
r (t)dt =
0
0
Tˇemto podm´ınk´am vyhovuje transformace
Pokud bychom splnˇen´ı podm´ınek (3.13) a (3.14) chtˇeli dok´azat, je moˇzn´e to snadno prov´est rozdˇelen´ım z(t) a r(t) na intervaly, viz tab. 3.1. Z posledn´ıho ˇr´adku tab. 3.1 vypl´ yv´a platnost (3.13). Druhou podm´ınku (3.14) ovˇeˇr´ıme
´ CEC ˇ ´I LINKA 3.2. STA
21
Tabulka 3.1: Rozdˇelen´ı transformace na intervaly
interval
vztahy r (t) = 0
t = h0, T0 i
z˙ (t) =
1 Tn
r (t) −
1 Tn
r (t − Tn )
z (t) = z0 = 0 r (t) = 1 t = (T0 , T0 + Tn i
z˙ (t) = z (t) =
1 Tn 1 Tn
r (t) = 1 t = (T0 + Tn , T1 i
z˙ (t) =
1 Tn
R
d (t − T0 ) + z (T0 ) =
−
1 Tn
t−T0 Tn
=0
z (t) = z (T0 + Tn ) =
T0 +Tn −T0 Tn
=1
r (t) = 0 t = (T1 , T1 + Tn i
z˙ (t) = − T1n z (t) = − T1n r (t) = 0
t = (T1 + Tn , ∞)
R
d (t − T1 ) + z (T1 ) = 1 −
z˙ (t) = 0 z (t) = z (T1 + Tn ) = 1 +
T1 +Tn −T1 Tn
=0
t−T1 Tn
22
KAPITOLA 3. MODEL LOGISTIKY
integrov´an´ım z(t) a r(t) pˇres jednotliv´e intervaly r (t) dt =
0
TZ 0 +Tn
Z∞
z (t) dt =
TZ 0 +Tn
Z∞
0
dt +
T0
ZT1
dt = T1 − T0
T0 +Tn
ZT1
t − T0 dt + Tn
T0
dt +
T0 +Tn
TZ 1 +Tn
t − T1 dt = T1 − T0 Tn
T1
Tuto transformaci lze aplikovat na vstupn´ı veliˇcinu modelu l(t) tak, ˇze plat´ı lz (t) = z (t) , 1 (l (t) − l (t − Tn )) , z˙ (t) = Tn
(3.16) z 0 = 0,
(3.17)
pˇriˇcemˇz Tn je doba n´abˇehu. Pak lze vztahy (3.9) a (3.10) zapsat n´asleduj´ıc´ım zp˚ usobem: # " lz (t − Td ) sl (t) = L . lz (t) Nev´ yhodou takto definovan´e transformace ovˇsem je pˇrid´an´ı dalˇs´ıho dopravn´ıho zpoˇzdˇen´ı do modelu. Aproximace pˇ renosovou funkc´ı druh´ eho ˇ r´ adu Dalˇs´ı moˇznost´ı je pouˇz´ıt pro transformaci vhodn´ y syst´em druh´eho ˇr´adu s pˇrenosem F (s) =
ωn2 , s2 + 2ξωn s + ωn2
kde ωn je pˇrirozen´a frekvence a ξ je pomˇern´e tlumen´ı nab´ yvaj´ıc´ı hodnoty mezi 0 a 1. Empirick´ y vzorec pro dobu n´abˇehu tr syst´emu druh´eho ˇr´adu je 1,8 . tr ∼ = ωn Pro n´abˇeh linky za p˚ ul hodiny lze tedy zvolit ωn = 3,6. Vzhledem k poˇzadavku na nulov´ y pˇrekmit mus´ı m´ıt pomˇern´e tlumen´ı ξ hodnotu 1 a pˇrenosov´a funkce F (s) m´a po dosazen´ı tvar F (s) =
12,96 . (s + 3,6)2
´ CEC ˇ ´I LINKA 3.2. STA
23
Stavov´ y popis takov´eho syst´emu m˚ uˇze b´ yt x˙ 1 (t) = −3,6x1 (t) + x2 (t) ,
(3.18)
x˙ 2 (t) = −3,6x2 (t) + 4r (t) ,
(3.19)
z (t) = 3,24x1 (t) .
(3.20)
T´ımto zp˚ usobem transformovan´ y sign´al je na obr. 3.4. Je zˇrejm´e, ˇze tvar n´abˇehu a sestupu z (t) odpov´ıd´a skuteˇcnosti m´enˇe, neˇz v pˇr´ıpadˇe transformace lichobˇeˇzn´ıkem (3.16). Dalˇs´ım probl´emem je, ˇze vhodnou volbou koeficient˚ u (3.18) sice lze simulovat urˇcitou dobu n´abˇehu, ovˇsem sign´al z (t) v koneˇcn´em ˇcase nedos´ahne c´ılov´e hodnoty 1 pˇri n´abˇehu, ani 0 pˇri sestupu. K tˇemto hodnot´am se pouze asymptoticky pˇribl´ıˇz´ı v nekoneˇcnu. To by mˇelo za n´asledek sn´ıˇzen´ı efektivity linky. To by pˇrirozenˇe ˇslo korigovat mal´ ym nav´ yˇsen´ım parametru efektivity linky. Velikost t´eto korekce by vˇsak musela b´ yt zjiˇstˇena empiricky. 1
stav linky [−]
0.8
0.6
0.4
0.2
0 T0
T0 + Tn
cas [−]
T1
T1 + Tn
Obr´azek 3.4: Alternativn´ı zp˚ usob modelace postupn´eho n´ajezdu a odstaven´ı linky
Zamezen´ı souˇ casn´ e v´ yroby dvou produkt˚ u Transformace popsan´e v pˇrechoz´ıch odstavc´ıch mohou zapˇr´ıˇcinit nenulov´e hodnoty v´ıce prvk˚ u v´ ystupn´ıho vektoru modelu linky souˇcasnˇe i pˇri dodrˇzen´ı podm´ınky zamezuj´ıc´ı souˇcasnou v´ yrobu v´ıce produkt˚ u (3.3). To nastane v pˇr´ıpadˇe, ˇze n´ajezdov´a hrana pr˚ ubˇehu jednoho v´ yrobku zaˇcne v okamˇziku, kdy dojezdov´a hrana jin´eho v´ yrobku jeˇstˇe neskonˇcila. Pˇr´ıklad takov´e situace je na obr. 3.5.
24
KAPITOLA 3. MODEL LOGISTIKY 4
x 10 9 10° 50L KEG 12° 50L KEG 10° 30L KEG
1
10° 50L KEG 12° 50L KEG 10° 30L KEG
8 7
tok produktu [ks/h]
stav linky [−]
0.8
0.6
0.4
6 5 4 3 2
0.2
1 0 0
1
2
3
4
5
6
7
0 0
8
1
2
3
4
5
6
7
8
cas [h]
cas [h]
(a) Vstupn´ı sign´ al
(b) Tok produkt˚ u 4
0
x 10
50L KEG 30L KEG
−1
tok obalu [ks/h]
−2 −3 −4 −5 −6 −7 −8 −9 0
1
2
3
4
5
6
7
8
cas [h]
(c) Tok obal˚ u
Obr´azek 3.5: Pˇr´ıˇcina vzniku pˇrekryvu
Pˇrekryv v´ yroby m˚ uˇze b´ yt probl´emem, ale za urˇcit´ ych podm´ınek jej lze i vyuˇz´ıt pro simulaci vˇerohodn´eho chov´an´ı linky, viz dalˇs´ı sekce. Zamezen´ı pˇrekryvu lze doc´ılit dalˇs´ı transformac´ı vstupn´ıho sign´alu, kter´a zajist´ı, ˇze n´abˇeh v´ yroby dalˇs´ıho produktu nastane nejdˇr´ıve po u ´pln´em zastaven´ı produkce pˇredch´azej´ıc´ı2 . V re´aln´e situaci by tato transformace odpov´ıdala situaci, kdy obsluha linky pozdrˇz´ı dalˇs´ı zak´azku, dokud nen´ı dopravn´ı p´as zcela vypr´azdnˇen. Pˇritom se dodrˇz´ı pl´anovan´ y konec st´aˇcen´ı t´eto zak´azky, aby nebyly zdrˇzov´any dalˇs´ı. Dojde tedy ke zkr´acen´ı inkriminovan´eho bloku v´ yroby, pokud je to nutn´e. 2
Ve skuteˇcnosti nen´ı tˇreba zcela zastavit linku, aby bylo moˇzn´e zaˇc´ıt produkovat jin´ y v´ yrobek. O tomto
jevu bude pojedn´ ano d´ale.
´ CEC ˇ ´I LINKA 3.2. STA
25
Ilustraci t´eto situace lze vidˇet na obr. 3.5(a). Podle vstupn´ıho sign´alu mˇelo b´ yt zapoˇcato st´aˇcen´ı dvan´actistupˇ nov´eho piva v 1 hodinu a 5 minut, zat´ımco odstavov´an´ı p˚ uvodn´ı v´ yroby mˇelo zaˇc´ıt pˇresnˇe v 1 hodinu. To znamen´a, ˇze pokud odstavov´an´ı linky trv´a 30 minut, pak by 25 minut linka produkovala dva v´ yrobky souˇcasnˇe a pokud je dopravn´ı cesta dlouh´a 45 minut, pak by 40 minut byly na lince souˇcasnˇe v´ yrobky a obaly obou zak´azek. C´ılem t´eto transformace vstupn´ıho sign´alu l(t) je zamezit tomu, aby po v´ yrobˇe jednoho produktu zapoˇcala v´ yroba druh´eho pˇr´ıliˇs brzy. Jedin´a moˇznost, jak toto prov´est, aniˇz by hrozila v´ yrazn´a zmˇena cel´eho pl´anu, je zkr´atit pl´anovanou dobu n´asleduj´ıc´ı v´ yroby, viz obr. 3.6. stav linky [−]
1 0.8 0.6 0.4 0.2 0 0
1
2
3
4
5
6
4
5
6
cas [−]
stav linky [−]
1 0.8 0.6 0.4 0.2 0 0
1
2
3
cas [−]
Obr´azek 3.6: Ilustrace transformace vstupn´ıho sign´alu l(t) pro odstranˇen´ı pˇrekryvu
Slovnˇe lze poˇzadavek na transformaci vyj´adˇrit: 1. Pokud v ˇcase t nen´ı produkov´an ˇz´adn´ y v´ yrobek, z˚ ust´av´a pr˚ ubˇeh l(t) bez z´asahu. 2. Pokud v ˇcase t − Td nebyl produkov´an ˇz´adn´ y v´ yrobek, z˚ ust´av´a pr˚ ubˇeh l(t) bez z´asahu. 3. Pokud je v ˇcase t i v ˇcase t − Td produkov´an v´ yrobek tent´ yˇz, pak z˚ ust´av´a pr˚ ubˇeh l(t) bez z´asahu. 4. V ˇcase t je produkov´an v´ yrobek pi , v ˇcase t − Td pak v´ yrobek pj , i 6= j. V takov´em pˇr´ıpadˇe dojde k pozdrˇzen´ı“ produkce v´ yrobku pj . ”
26
KAPITOLA 3. MODEL LOGISTIKY
Pozdrˇzen´ı v´ yroby zm´ınˇen´e ve 4. bodˇe probˇehne nastaven´ım sign´alu l(t) na nulov´ y vektor, dokud neuplyne doba Td od ukonˇcen´ı posledn´ı zak´azky. Ve vˇsech ostatn´ıch pˇr´ıpadech z˚ ustane vektor l(t) beze zmˇen. T´eto u ´pravy lze doc´ılit pomoc´ı n´asleduj´ıc´ı bin´arn´ı operace α (t) ∨ β (t − Td ) ↔ γ (t) ,
(3.21)
kde α (t) znaˇc´ı, ˇze v ˇcase t je na lince stejn´ y v´ yrobek jako v ˇcase t − Td a β (t − Td ) m´a hodnotu 1, pokud v ˇcase t − Td byl na lince alespoˇ n nˇejak´ y v´ yrobek. Hodnoty α (t) a β (t − Td ) lze urˇcit n´asleduj´ıc´ım zp˚ usobem: α (t) = lT (t) l (t − Td ) , β (t) = eT f l (t) . Vektor ef m´a d´elku m a vˇsechny jeho prvky maj´ı hodnotu 1. Slouˇz´ı k seˇcten´ı prvk˚ u vektoru l(t). Transformovan´ y sign´al lt (t) lze odtud vyj´adˇrit lt (t) = γ (t) l (t) = lT (t) l (t − Td ) + 1 − eT l (t) . f l (t − Td )
(3.22)
Takov´ y zp˚ usob u ´pravy vstupn´ıho sing´alu s sebou pˇrin´aˇs´ı do syst´emu znaˇcnou nelinearitu. Pokud vˇsak konzistence vstupn´ıho sign´alu bude zajiˇstˇena jin´ ym zp˚ usobem, nebude tˇreba tuto transformaci prov´adˇet. V pˇr´ıpadˇe pozorov´an´ı chov´an´ı syst´emu je nezbytn´e, abychom zajistili vˇerohodn´e chov´an´ı modelu. Na druhou stranu optimaliz´ator bude na z´akladˇe poˇzadovan´ ych v´ ystupn´ıch hodnot urˇcovat optim´aln´ı vstupn´ı sekvenci a bude pˇritom moˇzn´e pomoc´ı vhodnˇe definovan´eho krit´eria optimality zajistit, aby nekonzistentn´ı vstupn´ı sign´al nebyl optim´aln´ı. Pˇr´ıpadnˇe bude moˇzn´e pomoc´ı vhodnˇe definovan´ ych omezen´ı nekonzistentn´ı vstup zcela vylouˇcit. Pˇ rekryv v´ yroby V minul´ ych odstavc´ıch byl rozveden zp˚ usob, jak upravit vstupn´ı sign´al, aby se zamezilo v´ yrobˇe dvou produkt˚ u souˇcasnˇe. Pˇrestoˇze nen´ı fyzicky moˇzn´e, aby z linky vystupovalo v´ıce v´ yrobk˚ u v tent´ yˇz okamˇzik, je bˇeˇzn´e, ˇze jsou na lince z´aroveˇ n dvˇe sady obal˚ u urˇcen´e k v´ yrobˇe dvou r˚ uzn´ ych v´ yrobk˚ u. Zat´ımco totiˇz dob´ıh´a v´ yroba zak´azky prvn´ı, linka se uˇz zav´aˇz´ı obaly urˇcen´ ymi pro zak´azku n´asleduj´ıc´ı. T´ımto zp˚ usobem je d´ıky dlouh´ ym dopravn´ım cest´am moˇzn´e ve v´ yrobˇe pˇrech´azet mezi r˚ uzn´ ymi v´ yrobky, aniˇz by byla mezit´ım st´aˇcec´ı aparatura zcela odstavena a t´ım zv´ yˇsit efektivitu linky.
´ CEC ˇ ´I LINKA 3.2. STA
27
Doba, po kterou je moˇzn´e, aby na dopravn´ıc´ıch linky byly dvˇe sady obal˚ u je parametrem znaˇcen´ ym To . Jeho hodnota je pˇrirozenˇe shora omezena dopravn´ım zpoˇzdˇen´ım linky, tedy To < Td .
(3.23)
Parametr To lze do modelu zav´est m´ırnou modifikac´ı transformace (3.22), jej´ıˇz c´ılem je pr´avˇe moˇznost pˇrekryvu eliminovat. α (t) ∨ β (t − Td + To ) ↔ γ (t) .
(3.24)
Vztah (3.24) pˇresnˇe urˇcuje, o kolik poklesne moment´aln´ı efektivita linky (rychlost v´ yroby) pˇri pˇrechodu mezi dvˇema v´ yrobn´ımi zak´azkami. V ide´aln´ım pˇr´ıpadˇe si lze v´ yrobu s pˇrekryvem podle vstupn´ıho sign´alu na obr. 3.7(a) pˇredstavit jako pr˚ ubˇeh na obr. 3.7(b). Jeho aproximace modelem je na obr. 3.7(c). Zaj´ımaj´ı n´as pˇredevˇs´ım integr´aly tˇechto pr˚ ubˇeh˚ u a jejich srovn´an´ı. Plocha pod pr˚ ubˇehy generovan´ ymi modelem na obr. 3.7(c) je TZ 4 +Tn
lzm =
0
TZ 4 +Tn
lzm1 +
0
TZ 4 +Tn
lzm2 = T4 − T1 − Td + To ,
0
nebot’ podle (3.22) T3 = T2 + Td − To , pˇriˇcemˇz pˇredpokl´adejme, ˇze T3 − T2 < Td . Hodnotu Td − To lze povaˇzovat za pokles u ´hrnu v´ yroby v obdob´ı T1 aˇz T4 v d˚ usledku zmˇeny produkovan´eho v´ yrobku3 . Integr´al pr˚ ubˇeh˚ u na obr. 3.7(b) je TZ 4 +Tn
lzi =
0
TZ 4 +Tn
TZ 4 +Tn
lzi1 +
lzi2
(Td − To )2 . = T4 − T1 − Tn
0
0
Pokles u ´hrnu v´ yroby se liˇs´ı od aproximace. Je moˇzn´e vˇsak upravit hodnotu parametru modelu To tak, aby hodnota poklesu u ´hrnu v´ yroby odpov´ıdala poklesu podle ide´aln´ıho ′
pr˚ ubˇehu na obr. 3.7(b) s pˇrekryvem To : (Td − To )2 To = Td − . Tn ′
Z´aroveˇ n se liˇs´ı hodnoty integr´al˚ u pr˚ ubˇeh˚ u lzi1 a lzm1 stejnˇe jako lzi2 a lzm2 . Nejedn´a se vˇsak o chyby z´avisej´ıc´ı na d´elce bloku produkce, ale o chyby pauˇs´aln´ıho charakteru. V pˇr´ıpadˇe v´ıce blok˚ u v´ yroby v ˇradˇe se chyby navz´ajem t´emˇeˇr vyruˇs´ı. 3
za pˇredpokladu, ˇze uvaˇzujeme u obou v´ yrobk˚ u jednotkovou maxim´aln´ı efektivn´ı kapacitu linky
28
KAPITOLA 3. MODEL LOGISTIKY
l1(t)
1
lzi (t)
1
l (t)
1
l (t)
2
zi
2
0.8
stav linky [−]
stav linky [−]
0.8
0.6
0.4
0.2
0.6
0.4
0.2
0 T
1
T +T 1
n
T T 2
3
0
cas [−]
T
T +T
4
4
T
n
T +T
1
(a) Vstupn´ı sign´ al pˇred tvarovac´ı transformac´ı
1
T T
n
2
3
cas [−]
T
4
T +T
l
zm
(t)
1
lzm (t) 2
stav linky [−]
0.8
0.6
0.4
0.2
0 1
T +T 1
n
n
(b) Ide´ aln´ı pr˚ ubˇeh v´ yroby s pˇrekryvem
1
T
4
T T 2
3
cas [−]
T
4
T +T 4
n
(c) Aproximace pr˚ ubˇehu v´ yrobys pˇrekryvem
Obr´azek 3.7: Srovn´an´ı ide´aln´ıho pr˚ ubˇehu v´ yroby pˇri pˇrekryvu s modelem.
ˇ ´I CENTRUM A SKLAD 3.3. DISTRIBUCN
3.3
29
Distribuˇ cn´ı centrum a sklad
Ve spojen´ı se skladov´an´ım pouˇz´ıv´ame dva pojmy - distribuˇcn´ı centrum (DC) a sklad. Rozd´ıl je v u ´ˇcelu zaˇr´ızen´ı a jeho velikosti, pro obˇe ale postaˇc´ı tent´ yˇz model, rozd´ıl je pouze v hodnot´ach parametr˚ u. Z hlediska modelov´an´ı je struktura syst´emu skladu velice jednoduch´a, jedn´a se o integr´ator, jehoˇz funkce je zn´azornˇena na obr. 3.8. V´ ystupn´ı veliˇcina je integr´alem vstupn´ı, tedy plat´ı y(t) =
Z∞
x(t)dt ⇒ y(t) ˙ = x(t), x(0) = x0 .
0
u(t)
∫
y(t)
Obr´azek 3.8: Sch´ema integr´atoru
3.3.1
Vstupn´ı a v´ ystupn´ı veliˇ ciny modelu skladu
Na vstupu skladu jsou n´asleduj´ıc´ı veliˇciny: • tok produkt˚ u a obal˚ u z v´ yrobn´ıch linek v
ks h
(jen u sklad˚ u pˇridruˇzen´ ych k lince,
u ostatn´ıch nulov´ y), • tok produkt˚ u a obal˚ u z transportu
ks h
.
Na v´ ystupu pak: • uskladnˇen´e mnoˇzstv´ı v kusech po jednotliv´ ych produktech a obalech, • uskladnˇen´e mnoˇzstv´ı v paletov´ ych m´ıstech PALP po jednotliv´ ych produktech a obalech, • uskladnˇen´e mnoˇzstv´ı v paletov´ ych m´ıstech PALP celkem, • uskladnˇen´e mnoˇzstv´ı v paletov´ ych m´ıstech % ku kapacitˇe.
30
KAPITOLA 3. MODEL LOGISTIKY
Tok obal˚ u a produkt˚ u z v´ yrobn´ıch linek U jednoho skladu m˚ uˇze b´ yt linek v´ıce (ve skuteˇcnosti tomu tak opravdu je). Pˇr´ıspˇevky tok˚ u od kaˇzd´e linky se pak sˇc´ıtaj´ı do celkov´eho vektoru sl (t) definovan´eno sl (t) =
p X
sli (t),
i=1
kde p je poˇcet linek u dan´eho skladu a sli (t) je tok produkt˚ u a obal˚ u z dan´e linky podle (3.11).
Tok produkt˚ u a obal˚ u z transportu Sklad je obvykle napojen na celou distribuˇcn´ı s´ıt’, vede do nˇej a z nˇej tedy mnoho tras. Pˇr´ıspˇevky transport˚ u po vˇsech tras´ach je nutno seˇc´ıst shodn´ ym zp˚ usobem jako v pˇr´ıpadˇe pˇr´ıspˇevk˚ u z linky t(t) =
rU X
tUi (t) −
i=1
rL X
tLi (t),
i=1
kde t(t) je celkov´ y pˇr´ıspˇevek vˇsech transport˚ u, rU je poˇcet tras vedouc´ıch do pˇr´ısluˇsn´eho skladu, rL poˇcet tras vedouc´ı ze skladu (obvykle rU = rL ), tUi a tLi jsou pˇr´ıspˇevky tras vedouc´ıch do skladu a ze skladu respektive.
Uskladnˇ en´ e mnoˇ zstv´ı Vˇsechny ˇc´asti modelu internˇe pracuj´ı s jednotkou ks. Uskladnˇen´e mnoˇzstv´ı v pˇr´ısluˇsn´em skladˇe je znaˇceno s(t) a je definov´ano
s1 (t)
s1 (t) s(t) = . .. sm (t)
,
(3.25)
kde si (t) znaˇc´ı mnoˇzstv´ı produktu nebo obalu s indexem i na skladˇe. Pro pˇrepoˇcet t´eto veliˇciny do jednotky P ALP je tˇreba vektor s(t) pˇren´asobit vhodnou transformaˇcn´ı matic´ı sPALP (t) = T P ALP s(t).
ˇ ´I CENTRUM A SKLAD 3.3. DISTRIBUCN
31
Matice T PALP je podrobnˇeji rozebr´ana n´ıˇze. Skal´arn´ı veliˇcinu celkov´eho zaplnˇen´ı skladu sPALPc (t) z´ısk´ame prost´ ym seˇcten´ım prvk˚ u vektoru sPALP (t), tedy sPALPc (t) = ef sPALP (t), pˇriˇcemˇz ef je jednotkov´ y ˇr´adkov´ y vektor [1 1 . . . 1]. Procentu´aln´ı zaplnˇen´ı skladu sr (t) se pak urˇc´ı porovn´an´ım s kapacitou skladu C s (parametr popsan´ y n´ıˇze).
3.3.2
Parametry
Parametry modelu skladu jsou • kapacita skladu, • transformaˇcn´ı matice ks → PALP.
Transformaˇ cn´ı matice Jak uˇz bylo uvedeno, r˚ uzn´e v´ yrobky a obaly zab´ıraj´ı na jeden ks rozd´ıln´ y prostor ve skladu. Je tedy tˇreba prov´est pˇrepoˇcet z jednotky jednoho kusu na paletov´e m´ısto. K tomuto u ´ˇcelu slouˇz´ı transformaˇcn´ı matice t 0 ··· 0 PALP1 0 tPALP2 T PALP = . ... .. 0 tPALPm
,
hodnota tPALPi urˇcuje kolik paletov´ ych m´ıst zab´ır´a jeden kus v´ yrobku nebo obalu (nebo sp´ıˇse jakou ˇc´ast paletov´eho m´ısta zab´ır´a).
Kapacita skladu Z´akladn´ı jednotkou skladov´an´ı je paletov´e m´ısto. Proto i kapacita kaˇzd´eho skladu je ud´ana v t´eto jednotce. Kapacita skladu je znaˇcena Cs .
32
KAPITOLA 3. MODEL LOGISTIKY
3.3.3
Dalˇ s´ı vztahy
Stavov´a rovnice pro jeden sklad s pˇrilehlou linkou je ˙ s(t) = sl (t) + t(t), s(0) = s0 ,
(3.26)
kde sl (t) a t(t) jsou vstupn´ı veliˇciny definovan´e v´ yˇse a s0 je poˇc´ateˇcn´ı stav na pˇr´ısluˇsn´em skladˇe.
3.4
Transport
Principem transportu je naloˇzen´ı objekt˚ u a po urˇcit´em ˇcase potˇrebn´em na dopravu vyloˇzen´ı na jin´em m´ıstˇe. Tomu odpov´ıd´a jednotkov´ y pˇrenos s dopravn´ım spoˇzdˇen´ım. V distribuˇcn´ı s´ıti exsituje mnoho tras, v t´eto sekci bude pops´ana trasa jedna.
3.4.1
Vstupn´ı a v´ ystupn´ı veliˇ ciny modelu transportu
Intuitivnˇe lze urˇcit, ˇze vstupn´ı veliˇcinou do transportu je vektor nakl´adan´ ych objekt˚ u (v´ yrobk˚ u a obal˚ u) a v´ ystupn´ı veliˇcinou pak vektor vykl´adan´ ych objekt˚ u. Tyto veliˇciny jsou v modelu definov´any obdobnˇe. Vstupn´ı veliˇcinou je • vektor toku transportovan´ ych objekt˚ u a v´ ystupn´ımi veliˇcinami jsou • vektor toku nakl´adan´ ych objekt˚ u, • vektor toku vykl´adan´ ych objet˚ u.
Vektor toku transportovan´ ych objekt˚ u Hodnota kaˇzd´eho prvku z vektoru toku transportovan´ ych objekt˚ u t(t) ud´av´a, kolik kus˚ u tohoto v´ yrobku nebo obalu za ˇcas Tl je transportov´ano v ˇcase t. Hodnota Tl odpov´ıd´a
33
3.4. TRANSPORT dobˇe nakl´adky (pops´ano n´ıˇze), vektor t(t) m´a tedy tvar
t1
t2 .. . t mp t(t) = tmp +1 tmp +2 .. . tmp +mc
ta1 ta2 1 = .. Tl . ta(mp +mc )
,
(3.27)
kde tai je mnoˇzstv´ı produktu nebo obalu s indexem i naloˇzen´eho na n´akladn´ı v˚ uz. Je zˇrejm´e, ˇze, aby bylo naskladnˇeno opravdu mnoˇzstv´ı tai , mus´ı d´elka obd´eln´ıku pˇr´ısluˇsej´ıc´ı jednomu transportu b´ yt pr´avˇe Tl . Pokud by prob´ıhalo ve stejn´e dobˇe v´ıce transport˚ u, tak se pr˚ ubˇehy ti jednoduˇse seˇctou.
Vektor toku nakl´ adan´ ych objekt˚ u Vektor toku nakl´ad´an´ı tL (t) je simult´an´ı s vektorem toku transportovan´ ych objekt˚ u (3.27), jenom z form´aln´ıch d˚ uvod˚ u je zaveden vztah tL (t) = t(t).
Vektor toku vykl´ adan´ ych objekt˚ u Vyklad´an´ı je ˇcasovˇe opoˇzdˇeno za nakl´ad´an´ım o ˇcas Ttd , kter´ y je d´an ˇcasovou vzd´alenost´ı sklad˚ u na pˇr´ısluˇsn´e trase. Pro vektor toku vykl´adan´ ych objekt˚ u tU (t) tedy plat´ı tU (t) = t(t − Ttd ).
34
KAPITOLA 3. MODEL LOGISTIKY
3.4.2
Parametry
Parametry modelu transportu jsou • vzd´alenosti mezi sklady, • doba nakl´adky. Vzd´ alenosti sklad˚ u Matice D definuje hodinovou vzd´alenost jednotliv´ ych sklad˚ u od sebe a m´a tvar d d · · · d1n 11 12 d21 d22 D= . , . .. .. dn1 dnn
kde n je poˇcet sklad˚ u a prvek dij urˇcuje vzd´alenost skladu s indexem j od skladu s indexem i. Doba nakl´ adky Naloˇzen´ı kamionu neprobˇehne okamˇzitˇe, ale trv´a nˇekolik des´ıtek minut, bˇehem kter´ ych postupnˇe ub´ yv´a objekt˚ u ze skladu. Stejnˇe je definov´ano vyloˇzen´ı n´akladn´ıho vozu. Pˇrestoˇze nelze pˇredpokl´adat, ˇze kaˇzd´ y kamion bude naloˇzen (vyloˇzen) stejnˇe rychle, at’ uˇz z technick´ ych ˇci person´aln´ıch d˚ uvod˚ u, model poˇc´ıt´a s jedinou hodnotou. Pˇrirozenˇe naloˇzen´ı polopr´azdn´eho kamionu trv´a kratˇs´ı dobu, neˇz naloˇzen´ı plnˇe. Protoˇze vˇsak snahou je vyuˇz´ıvat kamiony vˇzdy nejefektivnˇeji, nen´ı tˇreba poˇc´ıtat s ˇc´asteˇcn´ ym naloˇzen´ım. Doba nakl´adky je znaˇcena Tn .
3.4.3
Shrnut´ı
Model transportu nem´a ˇz´adn´e stavov´e veliˇciny. V´ ystupn´ı veliˇciny jsou pˇr´ımo d´any vstupn´ı veliˇcinou. Rovnice modelu urˇcen´e v textu v´ yˇse jsou tedy tL (t) = t(t), tU (t) = t(t − Ttd ).
(3.28)
´ MODEL 3.5. CELKOVY
3.5
35
Celkov´ y model
V pˇredchoz´ıch sekc´ıch byly pops´any modely jednotliv´ ych prvk˚ u logistiky Pivovar˚ u Staropramen, a. s. V t´eto sekci budou tyto modely pouˇzity k tvorbˇe celkov´eho modelu logistick´eho procesu, kter´ y bude obsahovat n sklad˚ u, p linek a nt tras.
3.5.1
Veliˇ ciny celkov´ eho modelu
Model kaˇzd´eho prvku je pops´an pomoc´ı vektor˚ u obsahuj´ıc´ıch veliˇciny pˇr´ısluˇsn´e jednotliv´ ym produkt˚ um a obal˚ um. Protoˇze celkov´ y model bude jistˇe obsahovat v´ıce sklad˚ u, tras a linek, je tˇreba jim pˇr´ısluˇsn´e vektorov´e veliˇciny vhodnˇe uspoˇr´adat. Z hlediska pˇrehlednosti je nejv´ yhodnˇejˇs´ı maticov´ y popis obsahuj´ıc´ı
• matici skladov´an´ı, • matici v´ yroby, • matici transportu, • matici pˇr´ısluˇsnosti linek, • matici smˇeˇrov´an´ı.
Matice skladov´ an´ı Popisuje okamˇzit´e mnoˇzstv´ı kus˚ u v´ yrobk˚ u a obal˚ u na skladech. Jej´ı tvar je
sT 1 (t)
sT (t) 2 S(t) = . .. sT n (t)
,
kde n je poˇcet sklad˚ u a si (t) je vektor zaplnˇen´ı skladu i podle (3.25).
36
KAPITOLA 3. MODEL LOGISTIKY
Matice v´ yroby Obdobnˇe jako matice skladov´an´ı se matice v´ yroby L(t) skl´ad´a z ˇr´adk˚ u tvoˇren´ ych transponovan´ ymi toky v´ yrobk˚ u a obal˚ u z jednotliv´ ych linek podle (3.4) T s (t) l1 sT (t) l2 L(t) = . . .. (t) sT lp Hodnota p ud´av´a poˇcet v´ yrobn´ıch linek.
Matice transportu Jedn´a se o dvˇe matice odvozen´e z vekotr˚ u transportu tL (t) a tU (t) stejn´ ym zp˚ usobem jako matice skladov´an´ı a transportu, tedy T T t (t) t (t) L1 U1 tT (t) tT (t) L2 U2 T L (t) = , T U (t) = , . . .. .. T (t) tT (t) t Lnt Unt
kde nt je poˇcet tras.
Matice S(t), L(t), T L (t) a T U (t) maj´ı shodnˇe poˇcet sloupc˚ u rovn´ y poˇctu produkt˚ u a obal˚ u m.
Matice pˇ r´ısluˇ snosti linek K pˇriˇrazen´ı linek a jejich produkci jednotliv´ ym sklad˚ um slouˇz´ı matice P ve tvaru p p · · · p1p 11 12 p21 p22 P = . (3.29) . . .. .. pn1 pnp
Prvek pij urˇcuje zda linka j pˇr´ısluˇs´ı skladu i. Plat´ı pij = {0; 1}.
´ MODEL 3.5. CELKOVY
37
Tak´e je zˇrejm´e, ˇze v kaˇzd´em sloupci by se mˇela vyskytovat pouze jedin´a nenulov´a hodnota, jinak by jedna linka pˇr´ısluˇsela v´ıce sklad˚ um, tedy X
pij ≤ 1.
i
Matice smˇ eˇ rov´ an´ı K urˇcen´ı odkud kam vedou jednotliv´e trasy slouˇz´ı matice smˇeˇrov´an´ı R ve tvaru r r · · · r1nt 11 12 r21 r22 R= . . .. .. rn1 rnnt
(3.30)
a plat´ı
rij = {−1; 0; 1}, pˇriˇcemˇz hodnota −1 znaˇc´ı, ˇze ze skladu i vede trasa j a hodnota 1 znamen´a, ˇze ve skladu i trasa j konˇc´ı. Je pˇrirozen´e, ˇze plat´ı X
rij = 0,
i
nebot’ kaˇzd´a trasa m´a jeden zaˇc´atek a jeden c´ıl. Pro potˇreby modelu je nutn´e definovat matici RL , kter´a je tvoˇrena pouze nekladn´ ymi prvky matice R (ostatn´ı jsou nulov´e) a RU obsahuj´ıc´ı pouze nez´aporn´e prvky matice R. Plat´ı tedy R = RL + RU .
Matice P a R maj´ı shodnˇe poˇcet ˇr´adk˚ u rovn´ y poˇctu sklad˚ u n.
3.5.2
Shrnut´ı
Vztah urˇcuj´ıc´ı chov´an´ı celkov´eho modelu m´a tvar S(t) = P L(t) + RL T L (t) + RU T U (t).
(3.31)
38
KAPITOLA 3. MODEL LOGISTIKY
3.6
Verifikace modelu
V t´eto sekci bude provedeno ovˇeˇren´ı modelu za pomoc´ı skuteˇcn´ ych historick´ ych dat. Protoˇze veˇsker´a konkr´etn´ı ˇc´ısla t´ ykaj´ıc´ı se provozu logistiky Pivovar˚ u Staropramen, a. s., jsou povaˇzov´ana za citliv´e informace, bude v t´eto pr´aci d´an pˇrednost procentu´aln´ımu vyj´adˇren´ı odchylek, pˇr´ıpadnˇe budou data vhodn´ ym zp˚ usobem4 pozmˇenˇena. Protoˇze monitorovac´ı n´astroje pouˇz´ıvan´e zadavatelem neumoˇzn ˇuj´ı export dat vhodn´ ych pro verifikaci modelu, bylo nutn´e hodnoty opisovat ruˇcnˇe. Z toho d˚ uvodu je dat bohuˇzel velice omezen´e mnoˇzstv´ı - postihuj´ı jeden v´ yrobn´ı t´ yden. Jedn´a se pouze o historii provozu v´ yrobn´ı linky. K verifikaci model˚ u sklad˚ u a transport˚ u data nejsou k dispozici, avˇsak vzhledem k povaze tˇechto syst´em˚ u nen´ı verifikace nutn´a5 .
3.6.1
Verifikace modelu st´ aˇ cec´ı linky
K dispozici jsou data obsahuj´ıc´ı pr˚ ubˇeh t´ ydenn´ı produkce kegov´e linky. Zahrnuj´ı n´asleduj´ıc´ı informace: • ˇcasov´e intervaly st´aˇcen´ı urˇcit´ ych v´ yrobk˚ u, • n´ajezd a dojezd linky, • pl´anovan´e odst´avky (sanitace), • okamˇziky zmˇen v´ yrobk˚ u a obal˚ u na lince, • celkovˇe stoˇcen´e mnoˇzstv´ı od kaˇzd´eho v´ yrobku za den, • okamˇziky nepl´anovan´ ych odst´avek a poruch linky. Data mohou b´ yt vyj´adˇrena ve formˇe Ganttova diagramu na obr. 3.9, kde kaˇzd´a barva pˇredstavuje odliˇsn´ y st´aˇcen´ y produkt (pˇr´ıpadnˇe sanitaci). Jm´ena produkt˚ u nejsou uvedena, protoˇze pr˚ ubˇeh st´aˇcen´ı spad´a mezi citliv´e informace. Stejn´ ym zp˚ usobem budou v dalˇs´ı kapitole zobrazeny pl´any st´aˇcen´ı pˇri testov´an´ı optimaliz´atoru. 4´ 5
Uprava nesm´ı m´ıt vliv na chov´ an´ı syst´emu, tj. n´asoben´ı konstantou, odeˇcetn´ı konstanty apod. Jedn´a se o integr´ ator v pˇr´ıpadˇe skladu a zpoˇzd’ovac´ı linku v pˇr´ıpadˇe transportu, syst´emy jsou tedy
takˇrka trivi´ aln´ı.
39
3.6. VERIFIKACE MODELU
Pondělí
00
01
02
03
04
05
06
07
08
09
10
11
12 13 čas [h]
14
15
16
17
18
19
20
21
22
23
00
14
15
16
17
18
19
20
21
22
23
00
14
15
16
17
18
19
20
21
22
23
00
14
15
16
17
18
19
20
21
22
23
00
Úterý
00
01
02
03
04
05
06
07
08
09
10
11
12 13 čas [h]
Středa
00
01
02
03
04
05
06
07
08
09
10
11
12 13 čas [h]
Čtvrtek
00
01
02
03
04
05
06
07
08
09
10
11
12 13 čas [h]
Obr´azek 3.9: Gantt˚ uv diagram st´aˇcen´ı pro verifikaci modelu
Prvn´ı informac´ı, kterou lze z dat z´ıskat je efektivita linky e=
tON − tF · 100, tON
kde e je efektivita linky v procentech v˚ uˇci maxim´aln´ı, tON je doba chodu linky a tF souˇcet dob, po kter´ ych byla linka v poruˇse za sledovan´ y ˇcasov´ y interval. Obdobn´ ym zp˚ usobem lze snadno urˇcit nomin´aln´ı a efektivn´ı kapacitu linky: cef =
cef np , , cnom = 100 · tp e
pˇriˇcemˇz cef je efektivn´ı kapacita linky v
ks h
, np je poˇcet stoˇcen´ ych kus˚ u v´ yrobk˚ u za ˇcas tp
a cnom je nomin´aln´ı kapacita linky. Po nastaven´ı modelu podle z´ıskan´ ych hodnot je moˇzn´e urˇcit 1. odchylku sumy produkce jednotliv´ ych v´ yrobk˚ u zvl´aˇst’ za sledovan´e obdob´ı,
40
KAPITOLA 3. MODEL LOGISTIKY 2. odchylku sumy veˇsker´e produkce za sledovan´e obdob´ı.
Odchylka sumy veˇsker´e produkce m´a hodnotu Pi D D Pi M M nb ri ti − n ri ti = 1%, df = Pi D Db nb ri ti
(3.32)
kde nb je poˇcet v´ yrobn´ıch blok˚ u (ˇr´adk˚ u tab. 3.2), riD a riM znaˇc´ı rychlost produkce (efek-
M tivn´ı kapacitu) ve v´ yrobn´ım bloku i historick´ ych dat a modelu respektive, tD c´ı i a ti znaˇ
d´elku v´ yrobn´ıho bloku i z historick´ ych dat a modelu respektive. Odchylka sumy produkce u jednotliv´ ych v´ yrobk˚ u lze nejl´epe zobrazit pomoc´ı histogramu na obr. 3.10. 5 4.5 4
cetnost [−]
3.5 3 2.5 2 1.5 1 0.5 0 −70
−60
−50
−40
−30
−20
−10
0
10
odchylka [%]
Obr´azek 3.10: Histogram odchylky modelu od reality pro jednotliv´e v´ yrobky
3.6.2
Vyhodnocen´ı verifikace
Pro d˚ ukladnou verifikaci by bylo potˇreba mnohem v´ıce dat, avˇsak uˇz z tohoto vzorku je zˇrejm´e, ˇze efektivita linky v pr˚ ubˇehu t´ ydne znaˇcnˇe kol´ıs´a a to aˇz o des´ıtky procent. Je moˇzn´e, ˇze vˇetˇs´ı soubor dat by toto zjiˇstˇen´ı pouze podpoˇril. Jedn´ım z d˚ uvod˚ u udrˇzov´an´ı vysok´e hladiny z´asob na skladech je pr´avˇe moˇznost, ˇze poˇzadovan´e mnoˇzstv´ı nebude na distribuˇcn´ı centrum dodan´e vˇcas. To m˚ uˇze nastat z mnoha pˇr´ıˇcin, mezi nˇeˇz patˇr´ı i porucha
41
3.6. VERIFIKACE MODELU
Tabulka 3.2: Historie provozu linky
den
a b
zaˇ c´ atek konec iˇ c.a
produkce
ks h
odch.b [%]
po.
14:01
23:59
1
220
u ´t.
0:00
5:27
1
299
12
u ´t.
5:28
5:46
2
100
-62
u ´t.
5:47
8:38
6
260
-2
u ´t.
8:39
9:57
5
306
15
u ´t.
9:58
16:31
3
302
13
u ´t.
16:32
19:39
4
300
12
u ´t.
19:40
23:59
7
300
12
st.
0:00
0:08
7
302
13
st.
0:09
3:27
8
278
4
st.
3:28
6:09
9
300
12
st.
10:38
12:53
10
282
6
st.
12:54
23:59
1
260
-3
ˇct.
0:00
14:20
1
289
8
ˇct.
14:21
15:06
2
209
-21
ˇct.
15:07
20:08
8
259
-2
Identifikaˇcn´ı ˇc´ıslo produktu Odchylka od pr˚ umˇern´e hodnoty produkce v procentech
-17
42
KAPITOLA 3. MODEL LOGISTIKY
linky. Protoˇze poruchy lze aproximovat pouze pravdˇepodobnostnˇe, je nutn´e se spokojit s prostou pr˚ umˇernou hodnotou efektivity linky. N´ızk´a odchylka sumy veˇsker´e produkce (3.32) je nevyhnuteln´ ym d˚ usledkem v´ ypoˇctu efektivn´ı kapacity z dat, pomoc´ı kter´ ych je model verifikov´an. Teoreticky by mˇela b´ yt nulov´a, jej´ı procentn´ı hodnota plyne sp´ıˇse z numerick´e nepˇresnosti v´ ypoˇct˚ u. Odchylky jednotliv´ ych produkt˚ u aˇz na jedinou v´ yjimku nepˇrekroˇc´ı 10%. Pˇrestoˇze se tento v´ ysledek ned´a povaˇzovat za vynikaj´ıc´ı, d´a se pˇredpokl´adat, ˇze na vˇetˇs´ım datov´em souboru by se podaˇrilo dos´ahnout odchylky do urˇcit´e m´ıry niˇzˇs´ı. Zaznamenan´a odchylka kolem 60% lze pˇrisoudit sp´ıˇse chybˇe v z´aznamu. Odpov´ıd´a tˇret´ımu ˇr´adku hodnot tab. 3.2, kde se vyskytuje nezvykle kr´atk´ y v´ yrobn´ı blok. U delˇs´ıch blok˚ u jsou odchylky v´ yraznˇe niˇzˇs´ı.
Kapitola 4 Optimaliz´ ator V n´asleduj´ıc´ım textu bude navrˇzen zp˚ usob tvorby n´astroje optimalizuj´ıc´ıho pl´anov´an´ı logistick´ ych proces˚ u Pivovar˚ u Staropramen, a. s. K tomuto u ´ˇcelu bude vyuˇzit model uveden´ y v pˇredchoz´ı kapitole. Z´asadn´ı u ´lohou pˇredch´azej´ıc´ı samotn´e optimalizaci je navrˇzen´ı krit´eri´ı optimality – tedy, zjednoduˇsenˇe ˇreˇceno, urˇcen´ı co je optim´aln´ı a co nikoliv. T´ımto probl´emem se bude zab´ yvat kap. 4.1.2. V dalˇs´ıch sekc´ıch budou navrˇzeny metody optimalizace a pot´e posouzeny z hlediska vhodnosti k ˇreˇsen´ı tohoto probl´emu. Nakonec budou v´ ysledky pl´anov´an´ı vyhodnoceny v kap. 4.6. K vysvˇetlen´ı z´akladn´ıch princip˚ u a pojm˚ u ˇr´ızen´ı a optimalizace byla vˇenov´ana kap. 2.2.
4.1
C´ıl optimalizace
V t´eto sekci bude vysvˇetlen probl´em pl´anov´an´ı logistiky Pivovar˚ u Staropramen, a. s. Budou uvedena krit´eria hodnocen´ı optimality pl´anu a pˇredstaveny informaˇcn´ı zdroje pl´anov´an´ı. Z´akladn´ım probl´emem souˇcasn´eho pl´anovac´ıho procesu je decentralizovanost mezi r˚ uzn´a oddˇelen´ı (st´aˇcen´ı, vaˇren´ı, transport apod.). Rozdˇelen´ı zodpovˇednosti je pˇrirozen´e vzhledem k rozsahu probl´emu, celkov´e optim´alnosti logistiky to ovˇsem neprosp´ıv´a. C´ılem t´eto pr´ace je navrhnout optimaliz´ator, kter´ y by sluˇcoval pl´anov´an´ı alespoˇ n nˇekolika kl´ıˇcov´ ych prvk˚ u logistiky souˇcasnˇe (st´aˇcen´ı, skladov´an´ı, transport). 43
´ KAPITOLA 4. OPTIMALIZATOR
44
4.1.1
Proces pl´ anov´ an´ı
Pl´anov´an´ı lze zjednoduˇsenˇe popsat pomoc´ı sch´ematu na obr. 4.1. Data potˇrebn´a k vypredikce a objednávky
aktuální stav logistiky
plán
požadavky (úrovně zásob, filtrace apod.)
Obr´azek 4.1: Sch´ema pl´ anov´an´ı
tvoˇren´ı pl´anu jsou 1. poˇc´ateˇcn´ı stav logistiky, • z´asoby produkt˚ u na skladech, • mnoˇzstv´ı dostupn´ ych obal˚ u, 2. vstupn´ı data, • predikce prodeje, • zadan´e objedn´avky, 3. poˇzadavky a omezen´ı, • pˇr´ım´e nakl´adky, • ide´aln´ı hladina z´asob, • filtrace piva, • poˇzadavky technick´eho r´azu, • kapacity sklad˚ u.
4.1. C´IL OPTIMALIZACE
45
Poˇ c´ ateˇ cn´ı stav logistiky Pl´anuje se vˇzdy na nˇekolik dn˚ u dopˇredu. Poˇc´ateˇcn´ı stav logistiky pˇredstavuje data obsahuj´ıc´ı aktu´aln´ı skladov´e z´asoby produkt˚ u a obal˚ u v jednotliv´ ych distribuˇcn´ıch centrech. Pˇredevˇs´ım v sez´onˇe je jedn´ım z nejv´ıc omezuj´ıc´ıch faktor˚ u mnoˇzstv´ı obal˚ u k dispozici pro st´aˇcen´ı. M˚ uˇze se proto st´at, ˇze pˇrestoˇze by bylo efektivnˇejˇs´ı st´aˇcet v´ yrobek v jednom bloku, mus´ı se v´ yroba rozdˇelit do nˇekolika dn´ı, aby se linka staˇcila zav´est pˇr´ısluˇsn´ ymi obaly. Z´akazn´ıci si ˇcasto obaly drˇz´ı delˇs´ı dobu, coˇz m˚ uˇze zp˚ usobit nedostatek pro potˇreby st´aˇcen´ı. Vracen´ı obal˚ u je predikov´ano a nelze pˇr´ıliˇs ovlivnit. Je tedy tˇreba se spol´ehat na predikci a z´asoby. V pˇr´ıpadˇe nedostatku lze prov´est revizi pl´anu. Predikce prodeje Z´akladem pro tvorbu predikce jsou historick´a data, ale zohledˇ nuj´ı se i pomˇernˇe aktu´aln´ı faktory, jako jsou napˇr´ıklad pl´anovan´a zdraˇzen´ı (z´akazn´ıci nakupuj´ı dopˇredu z´asoby pˇred n´ar˚ ustem ceny) apod. Pˇredpovˇed’ je v´ ystupem softwarov´eho n´astroje a je zat´ıˇzena urˇcitou nepˇresnost´ı. Nejistota pˇredpovˇedi je sniˇzov´ana skuteˇcnˇe pˇrijat´ ymi objedn´avkami (pokud je objedn´avka pˇrijata s dostateˇcn´ ym pˇredstihem). Zadan´ e objedn´ avky Objedn´avky mohou, ale nemus´ı, b´ yt pˇrijaty s pˇredstihem. V pˇr´ıpadˇe, ˇze nejsou, je poˇzadavek vykryt z´asobou. Pˇ r´ım´ e nakl´ adky Z hlediska minimalizace v´ıcen´aklad˚ u za dopravu je optim´aln´ı odv´aˇzet od linky zboˇz´ı pˇr´ımo na distribuˇcn´ı centrum, kter´emu je urˇceno. Jinak by se musely v´ yrobky nejprve pˇrev´est do jednoho z prim´arn´ıch distribuˇcn´ıch center v bl´ızkosti linky a pot´e teprve odeslat na m´ısto urˇcen´ı. Tento probl´em je podpoˇren decentralizac´ı pl´anovac´ıho procesu a z´asadn´ım omezen´ım je mal´a kapacita skladu u linky. Ide´ aln´ı hladina z´ asob Aby bylo moˇzn´e vykr´ yt nepˇresnosti pˇredpovˇedi prodeje, je tˇreba udrˇzovat urˇcitou rezervu zboˇz´ı. Velikost z´asob kol´ıs´a jak v d˚ usledku jejich vyuˇz´ıv´an´ı, tak v d˚ usledku pl´anov´an´ı z´asob, pˇri kter´em jsou zohlednˇeny dopady hromadˇen´ı kapit´alu na ukazatele hospodaˇren´e spoleˇcnosti. Udrˇzuj´ı se z´asoby jak hotov´ ych v´ yrobk˚ u, tak pr´azdn´ ych obal˚ u, pˇriˇcemˇz nastaven´ı profilu hladiny z´asob se liˇs´ı mezi druhy produkt˚ u a obal˚ u i mezi distribuˇcn´ımi centry. Poˇ zadavky technick´ eho r´ azu Existuj´ı speci´aln´ı poˇzadavky na pl´an – napˇr. urˇcit´ ym v´ yrobkem se nesm´ı zaˇc´ınat ani konˇcit blok v´ yroby, nebo um´ıstˇen´ı sanitace linky.
´ KAPITOLA 4. OPTIMALIZATOR
46
Filtrace piva Je potˇreba tak´e zohlednit proces filtrace piva, kdy je nutn´e koordinovat st´aˇcen´ı mezi linkami z d˚ uvodu omezen´ ych filtraˇcn´ıch kapacit.
4.1.2
Krit´ erium optimality ˇ r´ızen´ı
Krit´erium optimality ˇr´ızen´ı, neboli tak´e u ´ˇcelov´a funkce, popisuje, jak vyhodnotit kvalitu ˇr´ızen´ı nebo, v naˇsem pˇr´ıpadˇe, pl´anu logistiky. V t´eto sekci bude slovnˇe pops´ano, jak´ ym zp˚ usobem je moˇzn´e posuzovat optimalitu navrˇzen´eho pl´anu. Jedn´a se o pl´anov´an´ı logistick´ ych proces˚ u komerˇcn´ıho podniku za u ´ˇcelem minimalizace n´aklad˚ u1 , pˇriˇcemˇz kaˇzd´a u ´loha, proveden´a na cestˇe od pr´azdn´eho obalu leˇz´ıc´ıho ve skladu aˇz k dod´an´ı hotov´eho produktu z´akazn´ıkovi, nˇeco stoj´ı. Nˇekdy lze penˇeˇzn´ı hodnotu u ´kon˚ u urˇcit pomˇernˇe snadno, jindy pouze odhadovat. Kvalita optimalizace je pˇritom ve stejn´e m´ıˇre z´avisl´a na pˇresnosti nastaven´ı cen jako na pˇresnosti modelu. Je tedy tˇreba vˇenovat tomuto probl´emu zv´ yˇsenou pozornost a intenzivn´ı spolupr´aci se zadavatelem.
Hodnocen´ı kvality st´ aˇ cen´ı Provoz linky je pravdˇepodobnˇe nejdraˇzˇs´ım procesem logistiky. To, co naˇrizuj´ı objedn´avky a predikce, se ale stoˇcit mus´ı – ot´azkou z˚ ust´av´a kdy. Pl´an se tvoˇr´ı na jeden t´ yden a m˚ uˇze se st´at, ˇze nˇekter´e poˇzadavky bude levnˇejˇs´ı pokr´ yt ze z´asob a nechat stoˇcen´ı aˇz na dalˇs´ı t´ yden. Pˇri st´aˇcen´ı lze hodnotit • celkovou dobu st´aˇcen´ı, • poˇcet n´ajezd˚ u (a v´ yjezd˚ u) linky, • poˇcet zmˇen v produkci lince (pˇrestavˇen´ı na jin´e v´ yrobky).
Hodnocen´ı kvality skladov´ an´ı Nepˇr´ımo u ´mˇernˇe kapacitˇe skladu lze hodnotit cenu za uskladnˇen´e mnoˇzstv´ı. Oproti tomu vˇsak je d´ano, jak´e mnoˇzstv´ı m´a b´ yt na skladˇe jako rezervn´ı z´asoba. Co tedy hodnotit? Odchylku od poˇzadovan´e hladiny z´asoby nebo absolutn´ı mnoˇzstv´ı na skladˇe? Oboj´ı, nebot’ 1ˇ
Castou u ´lohou v t´eto tˇr´ıdˇe probl´em˚ u b´ yv´a maximalizace zisku. Rozsah modelu vˇsak neumoˇzn ˇuje nijak ovlivnit zisk, nebot’ ten je jasnˇe dan´ y z predikc´ı a objedn´ avek, kter´e jsou vstupem modelu.
4.1. C´IL OPTIMALIZACE
47
u nˇekter´ ych sklad˚ u je c´ılem m´ıt okamˇzit´e zaplnˇen´ı co nejmenˇs´ı (ide´alnˇe nulov´e), napˇr´ıklad u linek, kde jsou sklady velice mal´e. V distribuˇcn´ıch centrech vˇsak je tˇreba uvaˇzovat odchylku od poˇzadovan´ ych rezerv. Absolutn´ı hodnoty tˇechto rezerv se vˇsak produkt od produktu liˇs´ı i ˇr´adovˇe a pokud by byla odchylka hodnocena za jednotku, pak by byla jasnˇe preferov´ana minimalizace odchylky od poˇzadovan´e hladiny z´asob produktu s nejvˇetˇs´ımi objemy. Je proto tˇreba uvaˇzovat odchylky relativn´ı. U sklad˚ u s nulovou c´ılovou rezervou vˇsak relativn´ı odchylka urˇcit nelze (dˇelen´ı nulou). Je proto nutn´e hodnotit n´asleduj´ıc´ı stavy: • relativn´ı odchylka od poˇzadovan´e hladiny z´asob, • absolutn´ı hodnota uskladnˇen´eho mnoˇzstv´ı u sklad˚ u (pˇr´ıpadnˇe produkt˚ u) s nulovou poˇzadovanou rezervou.
Hodnocen´ı kvality transportu Transportn´ı spoleˇcnosti se plat´ı za kilometr, je proto nutn´e hodnotit kaˇzdou trasu zvl´aˇst’. Stejnˇe tak moˇzn´e naplnˇen´ı transportu na r˚ uzn´ ych tras´ach se m˚ uˇze mˇenit (napˇr´ıklad limity na v´ahu vozu v Praze). Kaˇzd´ y transport m´a tak svou hodnotu a celkov´e n´aklady jsou d´any jejich poˇctem. Dalˇs´ım krit´eriem hodnocen´ı kvality transportu je m´ıra vyuˇzit´ı n´akladov´eho vozu, kdy s kaˇzd´ ym nezaplnˇen´ ym m´ıstem vznikaj´ı ztr´aty dan´e skuteˇcnost´ı, ˇze se plat´ı za cel´ y v˚ uz.
Shrnut´ı krit´ eri´ı Je opˇet tˇreba zd˚ uraznit, jak´ y vliv maj´ı hodnoty ocenˇen´ı na v´ ysledn´ y pl´an. Pokud napˇr´ıklad bude cena odchylky uskladnˇen´eho mnoˇzstv´ı urˇcit´eho v´ yrobku od poˇzadovan´e hladiny z´asob pˇr´ıliˇs n´ızk´a oproti cenˇe za v´ yrobu, pak bude vˇzdy v´ yhodnˇejˇs´ı nechat produkci na dalˇs´ı t´ yden (dokud nedojde k vyˇcerp´an´ı z´asob). Oproti tomu, pokud bude cena za odchylku pˇr´ıliˇs vysok´a, pak se bude optimaliz´ator snaˇzit dorovnat hodnotu na poˇzadovanou u ´roveˇ n za kaˇzdou cenu a to i za cenu ˇcast´e zmˇeny produkce na lince. Nˇekter´e z vypsan´ ych krit´eri´ı mohou b´ yt do urˇcit´e m´ıry nadbyteˇcn´e. Pˇr´ıkladem m˚ uˇze b´ yt celkov´a doba st´aˇcen´ı, kter´a jasnˇe plyne z mnoˇzstv´ı, kter´e je nutn´e stoˇcit. Je sice moˇzn´e odloˇzit st´aˇcen´ı na dalˇs´ı t´ yden, ale pokud by to bylo v´ yhodn´e z hlediska doby st´aˇcen´ı, pak by tato operace naopak zv´ yˇsila dobu st´aˇcen´ı dalˇs´ıho t´ ydne a v delˇs´ım horizontu by
´ KAPITOLA 4. OPTIMALIZATOR
48
nedoˇslo k u ´spoˇre. Lze tak´e polemizovat, zda je nutn´e hodnotit vyuˇzit´ı n´akladov´eho prostoru automobil˚ u. Protoˇze je z´aroveˇ n minimalizov´ano mnoˇzstv´ı proveden´ ych transport˚ u, je zˇrejm´e, ˇze uˇz to samotn´e nut´ı optimaliz´ator plnit n´akladn´ı vozy co nejv´ıce.
4.1.3
Pˇ r´ınosy optimaliz´ atoru
Potˇreba komplexn´ıho optimalizaˇcn´ıho pl´anovac´ıho n´astroje je d´ana pˇredevˇs´ım rozsahem probl´emu, kter´ y je v podstatˇe nemoˇzn´e plnˇe pojmout bez sofwarov´eho vybaven´ı. Pˇrestoˇze n´astroje pro urˇcit´e ˇc´asti pl´anovac´ıho procesu existuj´ı, jsou z hlediska pokryt´ı probl´emu lok´aln´ıho charakteru. C´ılem t´eto pr´ace je navrhnout optimaliz´ator pokr´ yvaj´ıc´ı co nejvˇetˇs´ı ˇc´ast logistiky (s moˇznost´ı dalˇs´ıho rozˇs´ıˇren´ı) a pracuj´ıc´ı jako n´apovˇedn´ı syst´em pro pl´anovaˇce. Nen´ı pˇrirozenˇe moˇzn´e oˇcek´avat, ˇze pl´anov´an´ı by se r´azem zcela automatizovalo, vˇzdy bude potˇreba kvalifikovan´ y pracovn´ık schopn´ y vhodnˇe pˇrizp˚ usobit vstup optimaliz´atoru aktu´aln´ımu stavu a vybrat jeden z moˇzn´ ych pl´an˚ u a ten v pˇr´ıpadˇe potˇreby doupravit. V´ yhodou bude eliminace ˇci redukce zbyteˇcn´ ych u ´kon˚ u spojen´ ych s pl´anov´an´ı (jako je ruˇcn´ı vyhodnocen´ı skladov´ ych z´asob, tvorba tabulek, koordinace s ostatn´ımi oddˇelen´ımi apod.) a pˇredevˇs´ım jiˇz nˇekolikr´at zm´ınˇen´a vˇetˇs´ı centralizace procesu a s t´ım souvisej´ıc´ı moˇznost dosaˇzen´ı v´ yhodnˇejˇs´ıho pl´anu z ekonomick´eho hlediska pramen´ıc´ı z • niˇzˇs´ıho poˇctu transport˚ u, • moˇznosti preferovat transporty v dobˇe mimo ˇspiˇcku (d˚ uleˇzit´e zejm´ena v Praze), • sn´ıˇzen´ı objemu kapit´alu drˇzen´em ve formˇe uskladnˇen´ ych v´ yrobk˚ u, • potˇreby menˇs´ıch skladovac´ıch prostor, • efektivnˇejˇs´ı vyuˇzit´ı pracovn´ı doby zamˇestnanci, • pohotovˇejˇs´ı tvorby reviz´ı pl´anu v pˇr´ıpadˇe potˇreby. Pˇredevˇs´ım z d˚ uvodu omezen´ı mohutnosti dopravy lze oˇcek´avat i tyto pozitivn´ı efekty: • odlehˇcen´ı ˇzivotn´ımu prostˇred´ı, • zlepˇsen´ı dopravn´ı situace v Praze (a jin´ ych velk´ ych mˇestech).
´ ´IHO R ˇ ´IZEN´I 4.2. METODY OPTIMALN
4.2
49
Metody optim´ aln´ıho ˇ r´ızen´ı
C´ılem t´eto pr´ace je optim´aln´ı ˇr´ızen´ı logistiky, s pouh´ ym ˇr´ızen´ım se nelze spokojit. Mnoˇzina pouˇziteln´ ych metod se omezuje na ty umoˇzn ˇuj´ıc´ı shrnout poˇzadavky na ˇr´ızen´ı do krit´eria kvality ˇr´ızen´ı. Dalˇs´ım poˇzadavkem na algoritmus je dle definice v´ yrobn´ıho vektoru (3.2) v kap. 3.2 podpora nespojit´ ych promˇenn´ ych. Nˇekter´e metody optim´aln´ıho ˇr´ızen´ı lze aplikovat pouze na statick´e syst´emy - tedy takov´e, u nichˇz se nevyskytuje ˇcas jako nez´avisl´a promˇenn´a [4]. Dynamick´e syst´emy lze do formy ˇreˇsiteln´e statick´ ymi optimalizaˇcn´ımi metodami pˇrev´est diskretizac´ı.
4.2.1
Pˇ resn´ e metody
Pˇresn´ ymi metodami rozum´ıme takov´e algoritmy a v´ ypoˇcty, jejichˇz v´ ysledkem je optim´aln´ı ˇreˇsen´ı, pokud existuje. Probl´emem tˇechto metod ˇcasto b´ yv´a ˇcasov´a n´aroˇcnost a pˇrestoˇze doba v´ ypoˇctu je koneˇcn´a, m˚ uˇze b´ yt extr´emnˇe dlouh´a. V´ yˇ ctov´ e metody Nejjednoduˇsˇs´ı metodou je hled´an´ı optima ve v´ yˇctu vˇsech pˇr´ıpustn´ ych ˇreˇsen´ı a prost´e vybr´an´ı toho s nejniˇzˇs´ı (nejvyˇsˇs´ı) hodnotou kriteri´aln´ı funkce. Poˇcet ˇreˇsen´ı je koneˇcn´ y, ale extr´emˇe vysok´ y. Proto je tato metoda vhodn´a pouze pro mal´e probl´emy s omezen´ ym poˇctem diskr´etn´ıch promˇenn´ ych. Ke kaˇzd´e kombinaci celoˇc´ıseln´ ych promˇenn´ ych se vyˇreˇs´ı u ´loha obsahuj´ıc´ı jiˇz jen spojit´e promˇenn´e napˇr´ıklad pomoc´ı simplexov´e metody [5]. Matematick´ e programov´ an´ı Metody hled´an´ı extr´em˚ u funkc´ı v´ıce promˇenn´ ych, kter´e podl´ehaj´ı r˚ uzn´ ym omezen´ım, naz´ yv´ame matematick´ ym programov´an´ım a maj´ı tvar [6] minimalizuj f0 (x), x ⊂ Rn za omezen´ı
fi (x) ≤ bi , i = 1, . . . , m,
(4.1)
kde x je vektor optimalizaˇcn´ıch promˇenn´ ych o d´elce n, f0 je kriteri´aln´ı funkce a fi jsou omezuj´ıc´ı podm´ınky.
´ KAPITOLA 4. OPTIMALIZATOR
50
Pokud jsou omezuj´ıc´ı podm´ınky i krit´erium line´arn´ı, tedy pro f0 , . . . , fm plat´ı fi (αx + βy) = αfi (x) + βfi (y), pak je tento optimalizaˇcn´ı probl´em naz´ yv´an line´ arn´ım programov´ an´ım. V pˇr´ıpadˇe kvadratick´e kriteri´aln´ı funkce v podobˇe f0 = xT Hx + f T x + c
(4.2)
naz´ yv´ame probl´em kvadratick´ ym programov´ an´ım. Tˇr´ıda u ´loh pro jej´ıˇz kriteri´aln´ı funkci a omezuj´ıc´ı podm´ınky plat´ı nerovnost fi (αx + βy) ≤ αfi (x) + βfi (y)
(4.3)
se naz´ yv´a konvexn´ı programov´ an´ı. Je zˇrejm´e, ˇze tˇr´ıda u ´loh kvadratick´eho programov´an´ı je podmnoˇzinou tˇr´ıdy konvexn´ıho programov´an´ı a line´arn´ı programov´an´ı zase speci´aln´ım pˇr´ıpadem kvadratick´eho programov´an´ı (pro H = 0). Existuje velk´e mnoˇzstv´ı metod pro v´ ypoˇcet r˚ uzn´ ych tˇr´ıd matematick´eho programov´an´ı. Velice efektivnˇe lze ˇreˇsit probl´emy line´arn´ıho a kvadratick´eho programov´an´ı pomoc´ı metod schopn´ ych pracovat v polynomi´aln´ım ˇcase. Pokud ovˇsem vˇsechny promˇenn´e nejsou spojit´e, pak se probl´em st´av´a NP-tˇeˇzk´ ym - nen´ı zn´am polynomi´aln´ı algoritmus [5] - a je tˇreba pˇri v´ ypoˇctu kombinovat nˇekolik metod (napˇr´ıklad simplexovou metodu a metodu vˇetv´ı a mez´ı). V n´asleduj´ıc´ıch odstavc´ıch budou nˇekter´e z´akladn´ı metody struˇcnˇe pops´any. Dantzigova simplexov´ a metoda Tato metoda je schopn´a velice rychle ˇreˇsit probl´emy line´arn´ıho programov´an´ı. Prostor pˇr´ıpustn´ ych ˇreˇsen´ı m´a tvar n-rozmˇern´eho polytopu, kter´ y je v prostoru Rn vymezen omezuj´ıc´ımi podm´ınkami. Optim´aln´ı ˇreˇsen´ı se pˇritom nach´az´ı na jednom z vrchol˚ u, kter´e pˇredstavuj´ı bazick´e ˇreˇsen´ı [7]. Zjednoduˇsenˇe ˇreˇceno pˇrech´az´ı simplexov´a metoda po hran´ach polytopu mezi vrcholy, dokud nenajde optim´aln´ı ˇreˇsen´ı. Protoˇze ale poˇcet vrchol˚ u polytopu je exponencielnˇe z´avisl´ y na poˇctu promˇenn´ ych a omezuj´ıc´ıch podm´ınek, nejedn´a se o algoritmus s polynomi´aln´ı rychlost´ı. Pˇresto vˇsak ve vˇetˇsinˇe pˇr´ıpad˚ u konverguje velice rychle, nebot’ nemus´ı vyzkouˇset vˇsechna bazick´a ˇreˇsen´ı. Metoda vˇ etv´ı a mez´ı Metoda je schopn´a ˇreˇsit u ´lohy sm´ıˇsen´eho line´arn´ıho programov´an´ı. Pokud probl´em obsahuje pouze bin´arn´ı a spojit´e promˇenn´e, pak algoritmus spoˇc´ıv´a ve vˇetven´ı probl´emu do stromu, kde uzly pˇredstavuj´ı podprobl´emy s hodnotami
´ ´IHO R ˇ ´IZEN´I 4.2. METODY OPTIMALN
51
dosazen´ ymi za urˇcit´e bin´arn´ı promˇenn´e a listy stromu probl´em obsahuj´ıc´ı jiˇz jen spojit´e promˇenn´e. Optim´aln´ı hodnotu kriteri´aln´ı funkce podprobl´em˚ u v listech jiˇz lze pomˇernˇe rychle dopoˇc´ıtat napˇr´ıklad pomoc´ı simplexov´e metody. Bˇehem vˇetven´ı se z´aroveˇ n urˇcuj´ı odhady mezn´ıch hodnot kriteri´aln´ı funkce probl´emu v kaˇzd´em uzlu. V listech je hodnota kriteri´aln´ı funkce jiˇz pˇresnˇe zn´ama. V kaˇzd´em kroku se porovn´avaj´ı meze uzl˚ u a vyˇrazuj´ı se takov´e, ze kter´ ych jiˇz nemohou vzej´ıt ˇreˇsen´ı s vyˇsˇs´ı hodnotou u ´ˇcelov´e funkce, neˇz je souˇcasn´a spodn´ı mez.
Metody seˇ cn´ ych nadrovin Metody seˇcn´ ych nadrovin jsou skupinou algoritm˚ u, zaloˇzen´ ych na opakovan´em ˇreˇsn´ı u ´lohy LP. V´ ypoˇcet je prov´adˇen iterativnˇe, tak ˇze v kaˇzd´em kroku je pˇrid´ana dalˇs´ı omezuj´ıc´ı podm´ınka zuˇzuj´ıc´ı oblast pˇr´ıpustn´ ych ˇreˇsen´ı. Kaˇzd´a nov´a omezuj´ıc´ı podm´ınka mus´ı splˇ novat tyto vlastnosti: • optim´aln´ı ˇreˇsen´ı nalezen´e pomoc´ı LP se stane nepˇr´ıpustn´ ym, • ˇz´adn´e celoˇc´ıseln´e ˇreˇsen´ı pˇr´ıpustn´e v pˇredchoz´ım kroku se nesm´ı st´at nepˇr´ıpustn´ ym. Nov´e omezen´ı splˇ nuj´ıc´ı tyto vlastnosti je pˇrid´ano v kaˇzd´e iteraci. Vznikl´ y ILP probl´em je vˇzdy znovu ˇreˇsen jako u ´loha LP. Proces je opakov´an, dokud nen´ı nalezeno pˇr´ıpustn´e celoˇc´ıseln´e ˇreˇsen´ı. Konvergence takov´eho algoritmu potom z´avis´ı na zp˚ usobu pˇrid´av´an´ı omezuj´ıc´ıch podm´ınek. Mezi nejzn´amˇejˇs´ı metody patˇr´ı Dantzigovi ˇrezy a Gomoryho ˇrezy [5].
4.2.2
Heuristick´ e metody
Metody vyuˇz´ıvaj´ıc´ı hrub´ ych odhad˚ u zaloˇzen´ ych na empirick´ ych informac´ıch se naz´ yvaj´ı heuristick´e. Jejich c´ılem nen´ı doj´ıt k optim´aln´ımu ˇreˇsen´ı, ale za rozumnou dobu nal´ezt ˇ ˇreˇsen´ı pˇr´ıpustn´e, kter´e se optim´aln´ımu alespoˇ n pˇribliˇzuje. Casto b´ yvaj´ı tyto algoritmy pouˇz´ıv´any pro z´ısk´an´ı v´ ychoz´ıho ˇreˇsen´ı pro pˇresn´e metody, c´ımˇz mohou v´ yraznˇe uˇsetˇrit v´ ypoˇcetn´ı ˇcas. Jejich v´ yhodou je schopnost pracovat s velice komplikovan´ ymi kriteri´aln´ımi funkcemi a menˇs´ı vliv zp˚ usobu formulace probl´emu na rychlost v´ ypoˇctu. Heuristick´e algoritmy jsou ˇcasto urˇceny pro jeden konkr´etn´ı probl´em, existuje vˇsak skupina heuristik pouˇziteln´ ych pro ˇsirˇs´ı skupinu u ´loh, jako jsou Genetick´e algoritmy, Simulovan´e ˇz´ıh´an´ı a Tabu prohled´av´ an´ı [8] naz´ yvan´e meta-heuristikami.
´ KAPITOLA 4. OPTIMALIZATOR
52 Genetick´ e algoritmy
Genetick´e algoritmy jsou metody zaloˇzen´e na abstraktn´ım modelu evoluˇcn´ı teorie. Z´akladn´ı myˇslenkou je udrˇzov´an´ı populace kandid´at˚ u na optim´aln´ı ˇreˇsen´ı, kter´a se postupnˇe vyv´ıj´ı (obsahuje ˇc´ım d´al v´ıc kvalitn´ı jedince) d´ıky selektivn´ımu v´ ybˇeru jedinc˚ u ke kˇr´ıˇzen´ı (tvorbˇe nov´ ych ˇreˇsen´ı). Jde o prohled´av´an´ı prostoru vˇsech ˇreˇsen´ı na z´akladˇe generov´an´ı nov´ ych ˇreˇsen´ı z mnoˇziny v´ıce ˇreˇsen´ı a ne podle vlastnost´ı jednoho jako u vˇetˇsiny algoritm˚ u. Algoritmus je n´asleduj´ıc´ı [8]: 1. Vygeneruj poˇc´ateˇcn´ı populaci (genotyp). 2. Ohodnot’ kaˇzd´eho jedince v populaci. 3. Vyber dvojici jedinc˚ u pro kˇr´ıˇzen´ı. 4. Vytv´aˇrej potomky, dokud nebude hotova nov´a generace. 5. Nahrad’ souˇcasnou populaci novˇe vytvoˇrenou a ˇc´ast´ı p˚ uvodn´ı. 6. Pokud nen´ı splnˇeno zastavovac´ı krit´erium, pokraˇcuj krokem 2. Aby bylo moˇzn´e prov´adˇet kˇr´ıˇzen´ı jedinc˚ u, mus´ı m´ıt chromoz´om vhodnou strukturu (podobaj´ıc´ı se skuteˇcn´emu). Vhodn´e je napˇr´ıklad bin´arn´ı pole hodnot. Stejnˇe tak vlastn´ı procedura kˇr´ıˇzen´ı mus´ı b´ yt definov´ana na m´ıru probl´emu.
Simulovan´ eˇ z´ıh´ an´ı Algoritmus je zaloˇzen na analogii s procesem ˇz´ıh´an´ı oceli, ve kter´em k pomal´emu rovnomˇern´emu ohˇrevu materi´alu a opˇetovn´emu pozvoln´em ochlazen´ı za u ´ˇcelem sn´ıˇzen´ı tvrdosti (ocel je pot´e vhodn´a k or´abˇen´ı za studena). Pokud by se materi´al zchladil pˇr´ıliˇs rychle, mohlo by doj´ıt k vytvoˇren´ı nedokonal´e krystalick´e mˇr´ıˇzky. Algoritmus se d´a shrnout do n´asleduj´ıc´ıch bod˚ u [8]: 1. Vygeneruj poˇc´ateˇcn´ı ˇreˇsen´ı S. Nastav poˇc´ateˇcn´ı teplotu T . 2. Zvol S ′ tak, aby se nach´azelo v sousedstv´ı S a urˇci zmˇenu ∆ v energetick´e hladinˇe (kriteri´aln´ı funkci).
´ ´IHO R ˇ ´IZEN´I 4.2. METODY OPTIMALN
53
3. Pokud je ∆ z´aporn´e nahrad’ S za S ′ . Pokud je ∆ kladn´e, akceptuj ˇreˇsen´ı S ′ s prav−∆ dˇepodobnost´ı, ˇze pro n´ahodn´e ˇc´ıslo δ v intervalu h0, 1i plat´ı δ < e( T ) . 4. Aktualizuj hodnotu teploty T na z´akladˇe poˇzadovan´eho pr˚ ubˇehu chlazen´ı, skuteˇcnosti, zda doˇslo ke zlepˇsen´ı apod.
Tabu prohled´ av´ an´ı Jedn´a se o lok´aln´ı prohled´av´an´ı obohacen´e o strategii modifikov´an´ı okol´ı aktu´aln´ıho stavu takov´ ym zp˚ usobem, abychom zamezili n´avratu do p˚ uvodn´ıho stavu. To je provedeno ukl´ad´an´ım atribut˚ u (vlastnost´ı stavu), kter´e byly zmˇenˇeny v urˇcit´em ˇcasov´em horizontu ˇ sen´ı, kter´a obsahuj´ı hodnotu atributu do pamˇeti a pˇriˇrazen´ım statusu tabu-aktivn´ı. Reˇ z tabu-active seznamu, jsou tabu a neprohled´avaj´ı se. Tyto stavy vˇsak nelze zak´azat natrvalo, mohly by v´est k optim´aln´ımu ˇreˇsen´ı. Po ˇcase se tedy povol´ı - aspirace [8].
4.2.3
Vyhodnocen´ı algoritm˚ u
´ celem optimalizaˇcn´ıho n´astroje je tvorba pl´anu na t´ Uˇ yden dopˇredu. Pˇrestoˇze je moˇzn´e podle okamˇzit´e situace v pr˚ ubˇehu t´ ydne pl´an upravovat, v ide´aln´ım pˇr´ıpadˇe se pl´an nemˇen´ı a na konci jeho p˚ usobnosti se vytvoˇr´ı pl´an na dalˇs´ı obdob´ı. Nejedn´a se proto o probl´em dynamick´eho ˇr´ızen´ı s pohybliv´ ym ˇcasov´ ym horizontem2 , ale sp´ıˇse o statick´e rozvrhov´an´ı, kdy se jednou urˇcen´ y pl´an jiˇz pˇr´ıliˇs neupravuje (v podstatˇe se jedn´a o ˇr´ızen´ı bez zpˇetn´e vazby). Vˇsechny metody uveden´e v pˇredchoz´ı sekci jsou vhodn´e pro u ´lohu statick´eho rozvrhov´an´ı (lze je teoreticky pouˇz´ıt i pro dynamick´e ˇr´ızen´ı). Deterministick´e metody uveden´e v kap. 4.2.1 nab´ızej´ı schopnost urˇcit optim´aln´ı ˇreˇsen´ı nebo alespoˇ n vzd´alenost v´ ysledn´eho ˇreˇsen´ı od optima, avˇsak nalezen´ı pouˇziteln´eho ˇreˇsen´ı m˚ uˇze trvat ne´ unosnˇe dlouhou dobu, kter´a je exponencielnˇe u ´mˇern´a rozsahu probl´emu. Oproti tomu heuristiky slibuj´ı v´ ysledek za mnohem kratˇs´ı dobu, ovˇsem nen´ı zaruˇcena kvalita ˇreˇsen´ı a dokonce ani to, ˇze bude nˇejak´e nalezeno. Ot´azka zn´ı, zda je potˇreba optim´aln´ı ˇreˇsen´ı, nebo se lze spokojit s ˇreˇsen´ım suboptim´aln´ım, kter´e by pˇrinejmenˇs´ım bylo vhodn´ ym z´akladem, na kter´em by mohlo stavˇet pl´anovac´ı 2ˇ
R´ıdic´ı syst´em v takov´em pˇr´ıpadˇe urˇc´ı optim´ aln´ı pr˚ ubˇehy vstupn´ıch veliˇcin na urˇcit´em ˇcasov´em ho-
rizontu a po uplynut´ı urˇcit´e doby (kratˇs´ı neˇz je doba horizontu) je ˇridic´ı sekvence pˇrepoˇc´ıt´ ana opˇet na dan´ y horizont.
´ KAPITOLA 4. OPTIMALIZATOR
54
oddˇelen´ı. Odpovˇed’ p˚ ujde snadno odvodit z penˇeˇzn´ı ˇc´astky skr´ yvaj´ıc´ı se pod jednoprocentn´ı odchylkou ˇreˇsen´ı od optima. Faktem je, ˇze tento probl´em je pravdˇepodobnˇe pˇr´ıliˇs rozs´ahl´ y pro pouˇzit´ı ˇcistˇe deterministick´ ych metod. Je nutn´e kombinovat tento pˇr´ıstup s heuristick´ ymi metodami. Existuje mnoˇzstv´ı softwarov´ ych n´astroj˚ u urˇcen´ ych pr´avˇe pro ˇreˇsen´ı probl´em˚ u popsan´ ych matematick´ ym programov´an´ım, kter´e v sobˇe kombinuj´ı (nejen) metody popsan´e v textu v´ yˇse – takzvan´e solvery . Ty kter´e jsou schopn´e ˇreˇsit sm´ıˇsen´e probl´emy (neobsahuj´ıc´ı pouze spojit´e promˇenn´e) jsou obvykle zaloˇzeny na metodˇe vˇetv´ı a mez´ı kombinovan´e se sloˇzit´ ymi heuristick´ ymi postupy proˇrez´av´an´ı a simplexovou metodou pro ˇreˇsen´ı ˇcistˇe line´arn´ıch podprobl´em˚ u. Pro ˇreˇsen´ı optimalizace logistiky Pivovar˚ u Staropramen, a. s., bude pouˇzit popis probl´emu pomoc´ı matematick´eho programov´an´ı (sm´ıˇsen´eho line´arn´ıho) a k v´ ypoˇctu optima bude pouˇzit vhodn´ y solver kombinuj´ıc´ı v´ıce optimalizaˇcn´ıch postup˚ u. Protoˇze model syst´emu vytvoˇren´ y v kap. 3 je dynamick´ y, je tˇreba nejprve prov´est diskretizaci, kter´a umoˇzn´ı kaˇzd´emu stavu, vstupu a v´ ystupu v kaˇzd´em ˇcasov´em kroku pˇriˇradit vlastn´ı promˇennou. T´ım vznikne statick´ y model.
4.3
Diskretizace
Matematick´ y popis dynamick´eho modelu logistiky (3.31) je uveden v kap. 3.5.2. Diskretizac´ı bude tento model pˇreveden na syst´em diskr´etn´ıch ud´alost´ı, kde m´ısto nez´avisl´e spojit´e promˇenn´e ˇcasu t bude vystupovat promˇenn´a diskr´etn´ıch hodnot k a popis obecn´eho spojit´eho line´arn´ıho ˇcasovˇe invariantn´ıho syst´emu (2.2) bude transformov´an do x(k + 1) = Ax(k) + Bu(k), y(k) = Cx(k) + Du(k),
(4.4)
kde k ∈ Z, x(k0 ) = xk0 ∈ Rn a k ≥ k0 [9].
4.3.1
Diskr´ etn´ı model linky
Diskr´etn´ı model linky bude odvozen ze z´akladn´ıho dynamick´eho modelu (3.11). Nebude tedy zahrnuta ˇz´adn´a aproximace n´ajezdu a odstaven´ı linky a to z d˚ uvodu komplikace
55
4.3. DISKRETIZACE
jiˇz tak rozs´ahl´eho modelu. Nav´ıc ze studia historick´ ych t´ ydenn´ıch pl´an˚ u st´aˇcen´ı plyne, ˇze najet´ı a tedy i odstaven´ı linky probˇehne za cel´ y t´ yden pouze jednou (pokud nedojde k mimoˇr´adn´e situaci). Lze tedy tvrdit, ˇze aproximace n´ajezdu linky nemus´ı b´ yt nezbytnˇe do diskr´etn´ıho popisu zahrnuta. Protoˇze v modelu linky nevystupuj´ı ˇz´adn´e stavov´e promˇenn´e, lze jednoduˇse prov´est diskretizaci nahrazen´ım ˇcasov´e promˇenn´e t za diskr´etn´ı promˇennou k s v´ yhradou, ˇze je nutn´e d´at pozor na jednotky. Vˇsechny veliˇciny vztaˇzen´e k ˇcasu, tedy napˇr´ıklad v´ yroba v
ks h
, mus´ı b´ yt pˇrevedeny na hodnoty vztaˇzen´e k d´elce vzorku (vzorkovac´ı periody), tedy
napˇr´ıklad
ks Tvz
. Diskretizovan´ y model linky m´a potom tvar " # l (k − Td ) 1 sl (k) = L , Tvz l (k )
(4.5)
kde matice L m´a shodn´ y tvar jako ve spojit´em pˇr´ıpadˇe (3.12), Td je dopravn´ı zpoˇzdˇen´ı linky zaokrouhlen´e na nejbliˇzˇs´ı n´asobek d´elky vzorku a Tvz je vzorkovac´ı perioda, tedy d´elka vzorku.
4.3.2
Diskr´ etn´ı model skladov´ an´ı
Spojit´ y model skladu integruje toky produkt˚ u a obal˚ u na vstupu, jedn´a se tedy o integr´ator. V diskr´etn´ı rovinˇe integr´atoru odpov´ıd´a sum´ator, jehoˇz stavov´a rovnice m´a tvar x(k + 1) = x(k) + u(k),
(4.6)
kde x(k) je stavov´a veliˇcina (pˇredstavuj´ıc´ı nasˇc´ıtanou hodnotu) a u(k) je vstupn´ı veliˇcina, kter´a se sˇc´ıt´a. Stavovou rovnici integr´atoru modelu skladu (3.26) je tedy nutn´e upravit do tvaru s(k + 1) = s(k) + sl (k) + t(k), s(0) = s0 ,
(4.7)
kde s(k) je zaplnˇen´ı skladu ve vzorku k, sl (k) je tok produkt˚ u a obal˚ u z linky, t(k) je tok produkt˚ u a obal˚ u z transportu.
4.3.3
Diskr´ etn´ı model transportu
Model transportu ve spojit´e formˇe funguje na principu zpoˇzd’ovac´ı linky (3.28). Vstupn´ı veliˇcina odpov´ıd´a obd´eln´ıku o d´elce doby nakl´adky Tl a amplituda rychlosti nakl´ad´an´ı,
´ KAPITOLA 4. OPTIMALIZATOR
56 tedy
M Tl
, kde M je mnoˇzstv´ı k naloˇzen´ı. Doba nakl´ad´an´ı by se pˇri diskretizaci musela
upravit tak, aby byla dˇeliteln´a d´elkou vzorku. To by vˇsak u hodnoty Tl niˇzˇs´ı nebo obdobn´e Tvz (coˇz bude pravdˇepodobnˇe platit) vedlo k definici Tl = Tvz . Diskr´etn´ı model je tedy definov´an se zanedb´an´ım doby nakl´adky Tl n´asledovnˇe tL (k) = t(k), tU (k) = t(k − Ttd ).
(4.8)
Vektory tL (k), tU (k) a t(k) jsou definov´any shodnˇe se spojit´ ymi protˇejˇsky, dopravn´ı zpoˇzdˇen´ı (d´elka trasy) Ttd mus´ı b´ yt n´asobkem Tvz . Hodnota jednotliv´ ych prvk˚ u vektoru tL (k) a tU (k) pak pˇr´ımo definuje kolik produkt˚ u a obal˚ u bude ve vzorku k na n´akladn´ı v˚ uz naloˇzeno a z vozu vyloˇzeno respektive.
4.3.4
Celkov´ y diskr´ etn´ı model
Matice skladov´an´ı S(t), matice v´ yroby L(t) a matice transportu T (t) vystupuj´ıc´ı ve spojit´em celkov´em modelu logistiky (3.31) jsou funkce ˇcasu. Diskretizac´ı jejich pr˚ ubˇeh navzorkujeme H vzorky s periodou Tvz . Matice S(k) je pak stav sklad˚ u ve vzorku k a popis cel´eho diskr´etn´ıho stavov´eho prostoru skladov´an´ı pro horizont H je d´an matic´ı S definovanou
S(1) S(2) S = . . . . S(H) Shodn´ ym zp˚ usobem je definov´ana i matice T popisuj´ıc´ı pr˚ ubˇeh transportu
T (1)
T (2) T = .. . T (H)
57
4.3. DISKRETIZACE a matice L, kter´a vyjadˇruje pr˚ ubˇeh stavu linky v cel´em horizontu L(1) L(2) L = . . .. L(H) Statick´ y model chov´an´ı logistick´eho procesu pak m˚ uˇze b´ yt pops´an S = S 0 − P D C D LRE + P Dd C D L (E − W ) + RD L,
(4.9)
kde E je jednotkov´a matice. Matice S 0 o rozmˇerech n · H × m, kde n je poˇcet sklad˚ u v modelu, m poˇcet produkt˚ u a obal˚ u a H je ˇcasov´ y horizont, je poˇc´ateˇcn´ı podm´ınkou stavu skladov´an´ı a je definov´ana
S(0)
S(0) S0 = . , .. S(0)
matice P D vyjadˇruje pˇriˇrazen´ı linek ke sklad˚ um a m´a tvar
PD
=
P 0
··· 0
P P ··· 0 P P ··· 0 , .. .. . . .. . . . . P P ··· P
pˇriˇcemˇz submatice P o rozmˇeru n × p, kde p je poˇcet linek, je matice pˇr´ısluˇsnosti linek (3.29) definov´ana v kap. 3.5. Obdobnˇe matice P Dd o rozmˇeru n × p je matice pˇr´ısluˇsnosti produkce linek a ud´av´a dopravn´ı zpoˇzdˇen´ı linek
P Dd
=
0
0
··· 0
P −1
0
P −1 + P −2 .. .
P −1 .. .
··· 0 ··· 0 . . . . .. . ··· 0
P −1 + · · · + P −H+1 P −1 + · · · + P −H+2
´ KAPITOLA 4. OPTIMALIZATOR
58
Submatice P−i je nulovou matic´ı, pokud ˇz´adn´a linka nem´a hodnotu dopravn´ıho zpoˇzdˇen´ı3 Td = i. Sloupec j submatice P−i se rovn´a sloupci j matice P , pokud pro linku pˇr´ısluˇsej´ıc´ı sloupci j plat´ı Td = i. ˇ Ctvercov´ a matice kapacit linek C D s rozmˇery p · H × p · H je blokovˇe diagon´aln´ı matice tvaru
CD =
C nom C ef 0
··· 0
0 .. .
C nom C ef · · · .. ... .
0
0
0 .. .
· · · C nom C ef
,
submatice na diagon´ale jsou tvoˇreny souˇcinem matic nomin´aln´ıch (3.6) a efektivn´ıch (3.7) kapacit linek definovan´ ych v kap. 3.2, kde je tak´e pops´an tvar matice receptury RE (3.5) a matice produkˇcn´ıch ztr´at W (3.8). Matice RD m´a rozmˇer n · H × nt · H, kde nt je poˇcet tras, a tvar RL 0 RL + RU−1 RL RU−1 RD = RL + RU−1 + RU−2 . .. .. .
··· 0 ··· 0 ··· 0 . . . .. .
RL + RU−1 + · · · + RU−H+1 RU−1 + · · · + RU−H+2 · · · RL
.
Submatice RL odpov´ıd´a nekladn´e ˇc´asti matice smˇeˇrov´an´ı (3.30) uveden´e v kap. 3.2. Submatice RU−i je, obdobnˇe jako P−i , nulov´a, pokud neexistuje trasa s ˇcasovou vzd´alenost´ı Ttd = i. Pokud existuje trasa j, jej´ıˇz vzd´alenost Ttd = i, pak j-t´ y sloupec matice RU−i odpov´ıd´a j-t´emu sloupci nez´aporn´e ˇc´asti matice smˇeˇrov´an´ı (3.30) RU definovan´e v kap. 3.2, ostatn´ı prvky submatice jsou nulov´e.
4.4
Softwarov´ e vybaven´ı
K v´ yvoji optimaliz´atoru bylo pouˇzito prostˇred´ı MATLAB urˇcen´e prim´arnˇe pro technick´e a matematick´e programov´an´ı. Nab´ız´ı zejm´ena v´ yteˇcnou podporu pr´ace s vektory a maticemi, snadn´e prezentov´an´ı v´ ysledk˚ u (grafy, export do excelu apod.) a pˇredevˇs´ım pro toto prostˇred´ı existuje mnoho softwarov´ ych n´astroj˚ u urˇcen´ ych pro optimalizaci. Jedn´ım 3
zaokrouhlenou na n´asobek d´elky vzorku
´ VYBAVEN´I 4.4. SOFTWAROVE
59
z nich je toolbox YALMIP [10]. Jedn´a se o n´astavbu MATLABu urˇcenou pro definice a ˇreˇsen´ı rozs´ahlejˇs´ıch optimalizaˇcn´ıch probl´em˚ u. D˚ uleˇzit´e je, ˇze je zdarma a nesm´ı b´ yt distribuov´an jako ˇc´ast komerˇcn´ıho produktu (avˇsak je moˇzn´e jej pouˇz´ıt jako v´ yvojov´ y n´astroj). YALMIP integruje i znaˇcn´e mnoˇzstv´ı trik˚ u, mimo jin´e pro aplikaci neline´arn´ıch funkc´ı typu max, abs, ceil na promˇenn´e probl´emu, pˇri zachov´an´ı linearity (obvykle za cenu pˇridan´ ych promˇenn´ ych). Pˇrestoˇze je MATLAB dod´av´an se z´aklan´ımi LP4 a QP5 solvery, pro ˇreˇsen´ı takto rozs´ahl´e u ´lohy nejsou dostateˇcnˇe v´ ykonn´e. Pro ˇreˇsen´ı probl´emu, kter´ ym se zab´ yv´a tato pr´ace, je tˇreba solveru schopn´eho pracovat se sm´ıˇsen´ ym line´arn´ım ˇci kvadratick´ ym probl´emem (MILP, MIQP resp., obsahuje i celoˇc´ıseln´e promˇenn´e). Z´akladn´ım parametrem, podle kter´eho lze tyto solvery rozliˇsovat, je zda jsou zdarma nebo komerˇcn´ı.
4.4.1
Nekomerˇ cn´ı solvery
LPSOLVE Z´akladn´ı solver schopn´ y ˇreˇsit MILP probl´emy s plnou podporou v prostˇred´ı YALMIP. Bohuˇzel jeho v´ ykon u probl´em˚ u s vyˇsˇs´ım mnoˇzstv´ım celoˇc´ıseln´ ych promˇenn´ ych je zcela nedostaˇcuj´ıc´ı.
GLPK Pomˇernˇe schopn´ y solver s podoporou celoˇc´ıseln´ ych promˇenn´ ych. Opˇet je plnˇe podporov´an prostˇred´ım YALMIP. Nev´ yhodou je nemoˇznost nastaven´ı limitu odchylky od ˇ optima. Casto postaˇcuje ˇreˇsen´ı s odchylkou nˇekolika procent (zejm´ena pro u ´ˇcely testov´an´ı) a konvergence se ke konci prohled´av´an´ı obvykle znaˇcnˇe zpomal´ı. Jeho v´ ykon je pr˚ umˇern´ y.
SCIP Jedn´a se o jeden z nejv´ ykonnˇejˇs´ıch nekomerˇcn´ıch solver˚ u. Nen´ı internˇe podporov´an prostˇred´ım YALMIP, dok´aˇze vˇsak importovat j´ım definovan´ y probl´em a ˇreˇsen´ı pot´e opˇet exportovat.
4.4.2
Placen´ e solvery
CPLEX Mˇel jsem moˇznost vyzkouˇset jedin´ y komerˇcn´ı solver a to CPLEX. Licenci ˇ vlastn´ı Katedra ˇr´ıdic´ı techniky CVUT FEL. Jedn´a se o jeden z nejv´ ykonnˇejˇs´ıch solver˚ u 4 5
line´arn´ı programov´ an´ı kvadratick´e programov´ an´ı
´ KAPITOLA 4. OPTIMALIZATOR
60
na trhu. Je schopn´ y ˇreˇsit probl´emy kvadratick´eho programov´an´ı ˇr´adovˇe vˇetˇs´ıch rozmˇer˚ u, neˇz jeho nekomerˇcn´ı protˇejˇsky a za mnohem kratˇs´ı ˇcas. Nev´ yhodou je jeho pomˇernˇe vysok´a cena, kter´a je vˇsak pˇri vyuˇzit´ı potenci´alu vzhledem k moˇznostem u ´spor rychle navr´acena.
4.5
Popis probl´ emu matematick´ ym programov´ an´ım
V t´eto sekci bude vytvoˇren popis probl´emu za pomoci matematick´eho programov´an´ı (4.1) a to konkr´etnˇe line´arn´ıho pˇr´ıpadu (4.2), kter´ y m˚ uˇze b´ yt definov´an minimalizuj cT x, za omezen´ı
Ax ≤ b, Aeq xeq = beq ,
(4.10)
xi ⊂ Z, ∀i ∈ XI , xj ⊂ R, ∀j ∈ XC , kde XI je mnoˇzina celoˇc´ıseln´ ych promˇenn´ ych a XC je mnoˇzina spojit´ ych promˇenn´ ych. V n´asleduj´ıc´ıch odstavc´ıch budou nejprve rozebr´any omezuj´ıc´ı podm´ınky probl´emu, tedy matice A a Aeq a pot´e navrˇzena konkr´etn´ı podoba u ´ˇcelov´e funkce - vektor c.
4.5.1
Definice promˇ enn´ ych
Existuj´ı tˇri druhy promˇenn´ ych, kter´e je moˇzn´e pouˇz´ıt pˇri ˇreˇsen´ı probl´emu sm´ıˇsen´eho line´arn´ıho programov´an´ı • spojit´e, • celoˇc´ıseln´e, • bin´arn´ı. Bin´arn´ı promˇenn´e jsou speci´aln´ım pˇr´ıpadem celoˇc´ıseln´ ych, kdy promˇenn´a sm´ı nab´ yvat pouze hodnot {0, 1}. Pˇr´ıkladem takov´ ych promˇenn´ ych v tomto probl´emu je v´ yrobn´ı matice L. Stav linky m´a vlastnost, ˇze bud’ pracuje na pln´ y dosaˇziteln´ y v´ ykon, nebo stoj´ı.
´ ´ PROGRAMOVAN ´ ´IM 4.5. POPIS PROBLEMU MATEMATICKYM
61
Nen´ı proto moˇzn´e jej popisovat spojitou promˇennou, protoˇze by se mohlo st´at, ˇze optimaliz´ator by navrhl chod linky napˇr´ıklad s tˇretinovou efektivitou, coˇz v re´aln´e situaci nen´ı v´ yhodn´e (neline´arn´ı spotˇrebn´ı charakteristika linky) a ˇcasto ani moˇzn´e. Nepˇr´ıjemn´ ym n´asledkem pouˇzit´ı bin´arn´ıch promˇenn´ ych je razantn´ı komplikace probl´emu a prodlouˇzen´ı doby potˇrebn´e na ˇreˇsen´ı. Proto je potˇreba je zav´adˇet pouze v pˇr´ıpadech, kdy je to nezbytnˇe nutn´e. Naˇstˇest´ı vˇetˇs´ı ˇc´ast probl´emu lze popsat spojit´ ymi promˇenn´ ymi.
4.5.2
Omezuj´ıc´ı podm´ınky
Tyto podm´ınky vymezuj´ı oblast pˇr´ıpustn´ ych ˇreˇsen´ı probl´emu - hled´a se minim´aln´ı hodnota kriteri´aln´ı funkce pˇri splnˇen´ı urˇcit´ ych podm´ınek, kter´e jsou d´any pˇredevˇs´ım modelem syst´emu. Prim´arn´ı omezuj´ıc´ı podm´ınkou tedy je S = S 0 − P CLRE + P d CL (E − W ) + RL + IC M ,
(4.11)
coˇz nen´ı nic jin´eho, neˇz vztah vyjadˇruj´ıc´ı chov´an´ı celkov´eho statick´eho (diskretizovan´eho) modelu logistiky (4.9) nav´ıc se ˇclenem IC M umoˇzn ˇuj´ıc´ım simulovat pr˚ ubˇeˇzn´ y odbˇer produkt˚ u z distribuˇcn´ıch center (a n´avrat obal˚ u). Matice I je blokov´a integraˇcn´ı matice o rozmˇeru n · H × n · H ve tvaru
I=
E 0
··· 0
E E ··· 0 E E ··· 0 , .. .. . . .. . . . . E E ··· E
ˇ kde E je jednotkov´a matice o rozmˇeru n × n. Clen C M pak urˇcuje spotˇrebu produkt˚ ua poˇcet vr´acen´ ych obal˚ u v kaˇzd´em kroku do kaˇzd´eho skladu
CM
C M (1) C M (2) = .. . C M (H)
a submatice C M (k) s rozmˇery n × m, kde m je poˇcet produkt˚ u a obal˚ u, urˇcuje spotˇrebu v k-t´em kroku.
´ KAPITOLA 4. OPTIMALIZATOR
62
Pˇrirozen´ ym poˇzadavkem je nez´apornost vˇsech promˇenn´ ych, nebot’ nelze produkovat ani transportovat z´aporn´e mnoˇzstv´ı a pˇrestoˇze se ve skladovac´ıch v´ ykazech obˇcas vyskytne z´aporn´a hodnota mnoˇzstv´ı na skladˇe, jedn´a se pouze o administrativn´ı chybu. Plat´ı tedy S ≥ 0, T
≥ 0,
(4.12)
v´ yznam nerovnost´ı pˇritom je, ˇze ˇz´adn´ y prvek matic nesm´ı b´ yt z´aporn´ y. V n´asleduj´ıc´ıch odstavc´ıch bude porovn´an´ı matice se skal´arn´ı hodnotou znamenat, ˇze dan´a podm´ınka plat´ı pro kaˇzd´ y prvek matice zvl´aˇst’. Pro matici v´ yroby L nen´ı nutn´e podm´ınku nez´apornosti explicitnˇe vyjadˇrovat, nebot’ plyne z bin´arn´ı povahy promˇenn´ ych produkˇcn´ıch vektor˚ u. Poˇzadavek na moˇznost v´ yroby pouze jednoho produktu souˇcasnˇe vˇsak implicitnˇe splnˇen nen´ı a mus´ı b´ yt definov´an X
L ≤ 1,
j
coˇz je v´ yraz shrnuj´ıc´ıci podm´ınky pro jednotliv´e v´ yrobn´ı vektory (3.3) uveden´e v kap. 3.2. V´ yraz (4.12) definuje spodn´ı omezen´ı pro hodnoty stav˚ u sklad˚ u, horn´ı omezen´ı pak plyne z kapacit sklad˚ u a lze vyj´adˇrit P
j
S ij ≤ cr ,
i = (k − 1)n + r, k = 1, 2, . . . , H,
kde n je poˇcet sklad˚ u, r je index skladu, cr je kapacita skladu r a H d´elka horizontu. Dalˇs´ım z´akladn´ım omezen´ım je zamezen´ı v´ yroby obal˚ u. Pokud by byl nenulov´ y prvek v´ yrobn´ıho vektoru odpov´ıdaj´ıc´ı produkci obalu, pak by ve skladu pˇrib´ yvaly obaly, aniˇz by cokoliv ub´ yvalo. To by se optimaliz´atoru jistˇe jevilo obzvl´aˇstˇe v´ yhodn´e. Mus´ı tedy platit Lij = 0, ∀i; j ∈ Co ,
(4.13)
kde Co je mnoˇzina vˇsech obal˚ u. Horn´ı omezen´ı hodnot matice transportu T je d´ano kapacitou n´akladn´ıch voz˚ u, coˇz pˇri rozd´ıln´e kapacitˇe na r˚ uzn´ ych tras´ach lze vyj´adˇrit P
j
T ij ≤ cTr ,
i = (k − 1)nt + r, k = 1, 2, . . . , H,
kde obdobnˇe jako u omezen´ı skladov´ ych kapacit je nt poˇcet tras, r je index trasy, cTr je kapacita n´akladn´ıho vozu na trase r a H d´elka horizontu. Abychom zcela zamezili
´ ´ PROGRAMOVAN ´ ´IM 4.5. POPIS PROBLEMU MATEMATICKYM
63
transport˚ um s neefektivn´ım vyuˇzit´ım n´akladov´eho prostoru, je moˇzn´e definovat bin´arn´ı promˇenn´e tb tak, aby platilo tmin tb ≤
X
T ij ≤ tmax tb ,
(4.14)
j
kde tmin a tmax je minim´aln´ı a maxim´aln´ı pˇr´ıpustn´e naloˇzen´ı respektive. Je zˇrejm´e, ˇze vektor bin´arn´ıch promˇenn´ ych tb m´a d´elku nt · H a vyjadˇruje, zda na dan´e trase v dan´em kroku doˇslo k transportu. Takto definovan´e omezen´ı z´aroveˇ n pˇredpokl´ad´a, ˇze v jednom kroku dojde maxim´alnˇe k jednomu transportu, coˇz je vzhledem k velikosti n´akladov´eho prostoru voz˚ u a d´elce periody vzorkov´an´ı (mezi ˇctvrthodinou aˇz hodinou) dostateˇcn´e. C´ılem posledn´ıho omezen´ı je zamezen´ı nelogick´eho transportu obal˚ u ze skladu linky a naopak dovoz produkt˚ u k lince. Tento jev m˚ uˇze nastat napˇr´ıklad, kdyˇz pˇri transportu k lince nen´ı dostatek obal˚ u k naplnˇen´ı n´akladn´ıho vozu. Optimaliz´ator by se pak mohl rozhodnout6 , ˇze je v´ yhodnˇejˇs´ı doplnit pr´azdn´e m´ısto produktem, neˇz vyslat neefektivnˇe zaplnˇen´ y v˚ uz. Pro z´akaz dovozu produkt˚ u na linku lze omezen´ı formulovat jako T ij = 0,
i = (k − 1)nt + ri ; j ∈ Pp , k = 1, 2, . . . , H,
(4.15)
kde ri jsou indexy tras, kter´e konˇc´ı ve skladu s linkou a Pp je mnoˇzina produkt˚ u. Shodn´ ym zp˚ usobem je definov´ano omezen´ı pro transport obal˚ u od linky T ij = 0,
i = (k − 1)nt + ro ; j ∈ Co , k = 1, 2, . . . , H.
4.5.3
(4.16)
´ celov´ Uˇ a funkce
Omezuj´ıc´ı podm´ınky probl´emu jsou jasnˇe dan´e jeho podstatou a strukturou. U u ´ˇcelov´e funkce tomu tak nen´ı a pˇrestoˇze je do urˇcit´e m´ıry moˇzn´e ji vytvoˇrit intuitivnˇe, zdaleka ne vˇsechny aspekty hodnocen´ı kvality pl´anu jdou pojmout takto jednoduˇse a ˇcasto je tˇreba vyuˇz´ıt empirick´ ych znalost´ı. V kap. 4.1.2 byly vysvˇeleny z´akladn´ı ukazatele, podle kter´ ych je moˇzn´e hodnotit pl´an logistiky. V t´eto sekci bude tˇemto bod˚ um navrˇzen odpov´ıdaj´ıc´ı matematick´ y z´apis. 6
pokud bude aplikov´ ana penalizace nezaplnˇen´ ych transport˚ u
´ KAPITOLA 4. OPTIMALIZATOR
64 Krit´ erium kvality st´ aˇ cen´ı
Nejintuitivnˇejˇs´ım poˇzadavkem na provoz linky je, aby byla v chodu co nejm´enˇe, v takov´em pˇr´ıpadˇe minimalizujeme krit´erium
Jp = c p
XX i
L,
j
kde cp je cena za produkci za dobu jednoho kroku. Jak bylo ovˇsem uvedeno v kap. 4.1.2, uˇziteˇcnost tohoto krit´eria je diskutovateln´a. Poˇzadavek na co nejniˇzˇs´ı v´ yrobu je totiˇz implicitnˇe obsaˇzen v dalˇs´ıch krit´eri´ıch, t´ ykaj´ıc´ıch se pˇredevˇs´ım skladov´an´ı. Vyhodnocen´ı poˇctu n´ajezd˚ u pro jedinou linku7 je moˇzn´e za pomoc´ı n´asleduj´ıc´ıho v´ yrazu
Jpst
X X X 1 = cpst ( Lij + L1j ), D 2 i j j
pˇriˇcemˇz cpst je cena za n´ajezd (a v´ yjezd) linky8 a D je diferenˇcn´ı matice rozmˇeru H × H (pro jednu linku) tvaru
−1
1
0
−1
0 .. .
0 .. .
0
0
0
0
D=
0
···
0
0
0 −1 · · · 0 0 .. . . .. .. . . . . . 0 · · · −1 1 0 · · · 0 −1 1
···
0
Obdobn´ ym zp˚ usobem je urˇcena i celkov´a cena za zmˇeny v produkci
Jpch =
7
XX 1 cpch |DLij | . 2 i j
Pokud by bylo uvaˇzov´ ano linek v´ıce, musel by se v´ yraz n´aleˇzitˇe upravit, aby se diference urˇcovala
vˇzdy z pr˚ ubˇehu na jedn´e lince. 8 ´ cel posledn´ıho ˇclenu Ve v´ yrazu se dˇel´ı dvˇemi, nebot’ se v souˇctu zapoˇc´ıt´ a jak n´ajezd tak v´ yjezd. Uˇ rovnice je zapoˇc´ıt´ an´ı i prvn´ıho vzorku.
´ ´ PROGRAMOVAN ´ ´IM 4.5. POPIS PROBLEMU MATEMATICKYM
65
Krit´ erium kvality skladov´ an´ı ´ celem je drˇzet uskladnˇen´e mnoˇzstv´ı co nejbl´ıˇze poˇzadovan´e hladinˇe z´asob. NejjedUˇ noduˇsˇs´ım zp˚ usobem je penalizovat absolutn´ı odchylku od reference, tedy XX Jabsres = cabsres |S ij − S ref | , i
j
kde cabsres je cena za jednotkovou odchylku. Jak bylo uvedeno v kap. 4.1.2, tento zp˚ usob nen´ı pˇr´ıliˇs vhodn´ y. Lepˇs´ı je penalizovat relativn´ı odchylku, pokud nen´ı reference nulov´a, u t´e je hodnocen´ı absolutn´ı odchylky nutn´e. Celkov´a hodnota vˇsech relativn´ıch odchylek je urˇcena Jres = cres
XX i
|S ij − S ref | ÷ S ref ,
j
pˇriˇcemˇz ÷ znaˇc´ı dˇelen´ı matic po prvc´ıch a kaˇzd´ y prvek matice S ref mus´ı b´ yt nenulov´ y. Protoˇze oba zm´ınˇen´e zp˚ usoby urˇcen´ı celkov´e ceny odchylky od reference jsou pomˇernˇe restriktivn´ı – penalizuj´ı i bˇeˇzn´e kol´ıs´an´ı zaplnˇenosti skladu zp˚ usoben´e napˇr´ıklad nakl´ad´an´ım a vykl´ad´an´ım – byla navrˇzena metoda vyuˇz´ıvaj´ıc´ı pr˚ umˇerov´an´ı pˇres urˇcit´ y ˇcasov´ yu ´sek. Cena za odchylku pˇres jeden ˇcasov´ yu ´sek se urˇc´ı lma X X T Jresa = cres Σa S − S ref ÷ S ref , ima i j
(4.17)
mus´ı pˇritom opˇet platit nenulovost prvk˚ u matice S ref . Parametry lma a ima jsou d´elka pr˚ umˇerovac´ıho okna a interval pr˚ umˇerov´an´ı respektive a Σ je sˇc´ıtac´ı matice o rozmˇeru
n · H × n a je definov´ana
0 . .. 0 E . . Σa = . , E 0 . .. 0
kde 0 a E jsou nulov´e a jednotkov´a matice respektive o rozmˇeru n × n, index a oznaˇcuje, o kter´ y souˇcet se jedn´a. Sˇc´ıtac´ı matice Σa je nenulov´a pouze v intervalu ˇr´adk˚ uj j ∈< a · ima · n + 1; a · ima · n + lma >,
´ KAPITOLA 4. OPTIMALIZATOR
66
kde je vyplnˇena jednotkov´ ymi maticemi, kter´e vytv´aˇrej´ı pr˚ umˇerovac´ı okno. Krit´ erium kvality transportu Dopravu lze hodnotit pomˇernˇe jednoduˇse pomoc´ı souˇctu poˇctu transport˚ u. Zda byl v urˇcit´em vzorku transport po dan´e trase proveden, je d´ano vektorem tb (4.14). Celkov´a cena za dopravu se tedy urˇc´ı Jtr = ctr
X
tbi .
i
V tomto v´ yrazu je implicitnˇe obsaˇzen i poˇzadavek na co nejvyˇsˇs´ı vyuˇzit´ı n´akladov´eho prostoru.
4.6
Vyhodnocen´ı optimalizace
´ cinnost optimalizace m˚ Uˇ uˇze b´ yt hodnocena z mnoha hledisek. Lze ji posuzovat zejm´ena podle n´asleduj´ıc´ıch kvalitativn´ıch a kvantitativn´ıch krit´eri´ı: • validita v´ ystupu, • rychlost optimalizace, • m´ıra zjednoduˇsen´ı oproti re´aln´emu probl´emu. V n´asleduj´ıc´ıch odstavc´ıch budou pˇredvedeny a vyhodnoceny uk´azky v´ ystupn´ıch dat optimaliz´atoru, k ˇcemuˇz poslouˇz´ı testovac´ı sc´en´aˇr prezentovan´ y v n´asleduj´ıc´ı sekci.
4.6.1
Testovac´ı sc´ en´ aˇ r
Aby bylo moˇzn´e jednoznaˇcnˇe vyhodnotit validitu v´ ysledk˚ u optimalizace, je nutn´e omezit probl´em natolik, aby nebylo obt´ıˇzn´e se v nˇem orientovat9 . Lze oˇcek´avat, ˇze pokud se v´ ystupn´ı pl´an bude shodovat s oˇcek´av´an´ım v kvantitativnˇe jednoduˇsˇs´ım probl´emu, bude optimalizace roz´ahlejˇs´ıch probl´em˚ u stejnˇe u ´spˇeˇsn´a. 9
Pro ˇreˇsen´ı rozs´ahl´ ych probl´em˚ u je tak´e tˇreba ne´ umˇernˇe v´ıce v´ ypoˇcetn´ıho ˇcasu. Velk´e mnoˇzstv´ı test˚ u
by v takov´e konfiguraci trvalo pˇrespˇr´ıliˇs dlouho.
4.6. VYHODNOCEN´I OPTIMALIZACE
67
Probl´ em Z´ akladn´ı u ´ daje D´elka ˇcasov´eho horizontu je nastavena na 2 dny pˇri vzorkov´an´ı po jedn´e hodinˇe, coˇz je ide´aln´ı kompromis mezi sloˇzitost´ı probl´emu, informaˇcn´ı hodnotou test˚ u a rychlost´ı v´ ypoˇctu. Budou prezentov´any i testy na delˇs´ıch sc´en´aˇr´ıch, zejm´ena za u ´ˇcelem vyhodnocen´ı ˇcasov´e n´aroˇcnosti optimalizace. Produkty a obaly Sc´en´aˇr zahrnuje dva z´akladn´ı obaly a tˇri produkty, kter´e v produkci zadavatele zauj´ımaj´ı pˇredn´ı m´ısta v objemu produkce. Produkty
Obaly
• 10◦ 50L KEG
• 50L KEG
• 10◦ 30L KEG
• 30L KEG
• 12◦ 30L KEG
Sklady Sc´en´aˇr zahrnuje 2 sklady pojmenovan´e Sm´ıchov a Most, kter´e jsou od sebe vzd´alen´e necel´e 2 hodiny j´ızdy. Sklady maj´ı nastaven´e urˇcit´e kapacity uveden´e v tab. 4.1, poˇc´ateˇcn´ı naskladnˇen´e mnoˇzstv´ı produkt˚ u a obal˚ u, viz tab. 4.2, a predikce prodeje produkt˚ u a n´avratu obal˚ u za hodinu (vzorek) udan´e v tab. 4.3. Poˇzadovan´a hladina z´asob je uvedena v tab. 4.4. Data t´ ykaj´ıc´ı se predikce pr˚ ubˇehu vr´acen´ı obal˚ u od z´akazn´ık˚ u nejsou k dipozici. V r´amci optimalizace se proto zav´ad´ı pr˚ ubˇeˇzn´ y navrat obal˚ u o objemech shodn´ ych s predikc´ı prodeje. Je tedy zaruˇceno, ˇze obal˚ u bude dostatek. Tabulka 4.1: Kapacity sklad˚ u testovac´ıho sc´en´ aˇre Sklad
kapacita [ks]
Sm´ıchov
15000
Most
25000
Linka Jedin´a linka je um´ıstˇena u sm´ıchovsk´eho skladu, kam nen´ı podle omezen´ı (4.16) a (4.15)) moˇzn´e vozit produkty a nelze z nˇej odv´aˇzet obaly. Kapacita linky je 500 sud˚ u za hodinu s efektivitou 86%, coˇz je hodnota urˇcen´a pˇri verifikaci modelu linky (3.6.1). Dopravn´ı zpoˇzdˇen´ı linky je nastaveno na 45 minut.
´ KAPITOLA 4. OPTIMALIZATOR
68
Tabulka 4.2: Poˇc´ateˇcn´ı mnoˇzstv´ı produkt˚ u a obal˚ u na skladech Sklad Sm´ıchov Most a
10◦ 50L KEGa
10◦ 30L KEG
12◦ 50L KEG
30L KEG
50L KEG
0
0
0
0
0
10000
4000
4000
600
2100
Vˇsechny hodnoty jsou uvedeny v kusech.
Tabulka 4.3: Odbˇer produkt˚ u a obal˚ u z distribuˇcn´ıch center Sklad Sm´ıchov Most a b
10◦ 50L KEGa
10◦ 30L KEG
12◦ 50L KEG
30L KEG
50L KEG
0
0
0
0
0
33
-42b
-117
83
42
Vˇsechny hodnoty jsou uvedeny v kusech. Z´aporn´e hodnoty znamenaj´ı pˇr´ısun do skladu.
Transport Je aplikov´ano omezen´ı, ˇze v kaˇzd´ y ˇcasov´ y vzorek sm´ı b´ yt proveden pouze jedin´ y transport. Kapacita n´akladn´ıho vozu je omezena na 1000 kus˚ u produkt˚ u nebo obal˚ u.
Nomin´ aln´ı nastaven´ı optimaliz´ atoru Nomin´aln´ı nastaven´ı kriteri´aln´ı funkce a parametr˚ u optimalizace je zvolen´e z´akladn´ı nastaven´ı, ke kter´emu se budou vztahovat v´ ysledky test˚ u. Jejich u ´ˇcelem bude urˇcit vliv zmˇen koeficient˚ u cenov´e funkce a parametr˚ u optimalizace na podobu optim´aln´ıho10 pl´anu. Nomin´aln´ı nastaven´ı rozhodnˇe nemus´ı b´ yt ide´aln´ı, avˇsak pl´an na nˇem zaloˇzen´ y je validn´ı. Nastaven´e hodnoty cenov´e funkce jsou uvedeny v tab. 4.5. Dalˇs´ı informace o nastaven´ı optimaliz´atoru jsou v tab. 4.6. 10
Lze hovoˇrit pouze o optimalitˇe vzhledem k urˇcit´emu nastaven´ı cenov´e funkce.
Tabulka 4.4: Poˇzadovan´e hladiny z´asob v jednotliv´ ych skladech Sklad Sm´ıchov Most a
10◦ 50L KEGa
10◦ 30L KEG
12◦ 50L KEG
30L KEG
50L KEG
0
0
0
0
0
10000
5000
4000
0
0
Vˇsechny hodnoty jsou uvedeny v kusech.
4.6. VYHODNOCEN´I OPTIMALIZACE
69
Tabulka 4.5: Koeficienty cenov´e funkce nomin´aln´ıho nastaven´ı optimaliz´atoru Koeficient
Hodnota
Popis Cena za n´ajezd a v´ yjezd linkya
cpst
100000
cpch
50000
Cena za zmˇenu produktu nebo obalu na linceb
cres
30000
Cena za 1% odchylky od referenˇcn´ı hladiny z´asob
ctr
40000
Cena za proveden´ y transport
xabsres
10000
Koeficient ud´avaj´ıc´ı kolik kus˚ u absolutn´ı odchylky stoj´ı stejnˇe jako jedno procento relativn´ı
a b
Zapoˇc´ıt´ av´ a se jak n´ajezd, tak v´ yjezd, efektivnˇe m´a tato cena tedy dvojn´ asobnou hodnotu. Zapoˇc´ıt´ av´ a se jak zaˇc´atek bloku, tak konec bloku, efektivnˇe m´a tato cena tedy dvojn´ asobnou hodnotu.
V´ ystup optimalizace s nomin´ aln´ım nastaven´ım V tab. 4.3 je zad´ano, jak´e mnoˇzstv´ı produkt˚ u si z´akazn´ık odebere kaˇzdou hodinu ze sklad˚ u, z´aroveˇ n existuje poˇzadavek (uveden´ y v tab. 4.4) na udrˇzen´ı urˇcit´e hladiny z´asob na skladech, coˇz je zajiˇstˇeno produkc´ı nov´ ych v´ yrobk˚ u – st´aˇcen´ım na lince – a jejich transportem na m´ısta urˇcen´ı. Avˇsak v´ yroba i transport stoj´ı urˇcit´e pen´ıze, kter´e jsou d´any hodnotami v tab. 4.5.
00
01
02
03
04
05
06
07
08
09
10
11
12 13 čas [h]
12° 50L KEG
10° 50L KEG
10° 30L KEG
Pondělí
14
15
16
17
18
19
20
21
22
23
00
Obr´azek 4.2: Gantt˚ uv diagram produkce pˇri nomin´aln´ım nastaven´ı
Poˇzadujeme, aby v´ yroba byla co nejplynulejˇs´ı, tzn. s co nejmenˇs´ım poˇctem n´ajezd˚ u a zmˇen v produkci. To je pˇri tomto nastaven´ı cenov´e funkce, jak lze pozorovat na Ganttovˇe diagramu na obr. 4.2, zcela uspokojeno. Protich˚ udn´ ym poˇzadavkem vˇsak jsou co nejmenˇs´ı odchylky od referenˇcn´ı hladiny z´asob – aby byla v kaˇzd´em okamˇziku odchylka minim´aln´ı, bylo by tˇreba, aby v´ yroba naopak stˇr´ıdala st´aˇcen´e produkty co nejˇcastˇeji. K um´ırnˇen´ı
´ KAPITOLA 4. OPTIMALIZATOR
70
Tabulka 4.6: Souhrn informac´ı o nomin´aln´ım nastaven´ı optimaliz´atoru Horizont [h]
48
Krok [h]
1
Pouˇzit´ y solver Maxim´ aln´ı povolen´ a odchylka od
SCIP optimaa
[%]
Doba potˇrebn´ a pro vyˇreˇsen´ı probl´emu [min] Poˇcet promˇenn´ ych
a
10 7,3 1712
Poˇcet bin´ arn´ıch promˇenn´ ych
582
Maxim´ aln´ı povolen´e naloˇzen´ı vozu
800
Minim´aln´ı povolen´e naloˇzen´ı vozu
1000
D´elka prumˇerovac´ıho okna odchylek od reference [h]
24
Interval pr˚ umˇerov´an´ı odchylek od reference [h]
12
L´epe procentu´aln´ı odchylka hodnoty krit´eria prim´ arn´ı u ´lohy od hodnoty krit´eria du´ aln´ı u ´lohy.
t´eto protich˚ udnosti slouˇz´ı zp˚ usob poˇc´ıt´an´ı odchylek od reference za uˇzit´ı pr˚ umˇerovac´ıho okna (4.17). To zajiˇst’uje, ˇze optim´aln´ı je rovnomˇern´e kol´ıs´an´ı mnoˇzstv´ı produkt˚ u na skladˇe kolem referenˇcn´ı hodnoty, jak lze vidˇet na obr. 4.3(a). Druh´ y den (obr. 4.3(b)) optimalizace nech´av´a na konci horizontu klesnout mnoˇzstv´ı produkt˚ u pod referenˇcn´ı hladinu v´ıce, nebot’ v´ yroba by jiˇz pˇr´ıliˇs zvedla cenu pl´anu. Odchylky od poˇzadovan´ ych z´asob produkt˚ u lze pozorovat na obr. 4.4(a) a obr. 4.4(b). Hodnoty se po vˇetˇsinu horizontu drˇz´ı v rozmez´ı 15%, pouze na konci horizont˚ u se vyˇsplhaj´ı aˇz ke 20%. Naj´ıˇzdˇet linku v t´e dobˇe by jiˇz bylo pˇr´ıliˇs drah´e a prodlouˇzen´ı bloku produkce pro vykryt´ı t´eto odchylky by zp˚ usobilo zv´ yˇsen´ı pˇrebytk˚ u na skladech v pr˚ ubˇehu horizontu a dalˇs´ı n´aklady s transportem. Podle tab. 4.4 je d´an d˚ uraz na udrˇzov´an´ı zaplnˇenosti sm´ıchovsk´eho skladu s linkou na co nejniˇzˇs´ı u ´rovni a to s ohledem na produkty i obaly. Pohledem na obr. 4.5 je moˇzn´e ovˇeˇrit, ˇze tomu tak skuteˇcnˇe je. Na obr. 4.5(a) lze jasnˇe pozorovat, ˇze pr´avˇe stoˇcen´e produkty se okamˇzitˇe odv´aˇz´ı na m´ısto urˇcen´ı, coˇz zobrazuje i tab. 4.7. Druh´ y den, kdy uˇz v´ yroba neprob´ıh´a, z˚ ust´av´a na skladˇe zbytkov´e mnoˇzstv´ı produkt˚ u a obal˚ u (obr. 4.5(b) a obr. 4.5(d)), coˇz je zp˚ usobeno nemoˇznost´ı stoˇcit za hodinu menˇs´ı mnoˇzstv´ı neˇz 430 sud˚ u (d´ano kapacitou a efektivitou linky v tab. 4.1), protoˇze nejmenˇs´ım ˇcasov´ ym u ´sekem je pr´avˇe jedna hodina. Pr˚ ubˇeh na obr. 4.5(d) ukazuje, ˇze dovezen´e obaly se bezodkladnˇe spotˇrebuj´ı a nezab´ıraj´ı tak zbyteˇcnˇe skladovac´ı prostory.
4.6. VYHODNOCEN´I OPTIMALIZACE
71
11000 11000 10000 10000 9000
na sklade [ks]
na sklade [ks]
9000 8000 10° 50L KEG 10° 30L KEG 12° 50L KEG
7000 6000 5000
8000 10° 50L KEG 10° 30L KEG 12° 50L KEG
7000 6000 5000
4000
4000
3000 0
2
4
6
8
10
12
14
16
18
20
3000 0
22
2
4
6
8
10
cas [h]
12
14
16
18
20
22
20
22
cas [h]
´ y (b) Uter´
(a) Pondˇel´ı
Obr´azek 4.3: Stavy produkt˚ u v DC Most pˇri nomin´aln´ım nastaven´ı optimalizace
15 10
odchylka od zasoby [%]
odchylka od zasoby [%]
10° 50L KEG 10° 30L KEG 12° 50L KEG
10
5
0
−5
−10
10° 50L KEG 10° 30L KEG 12° 50L KEG
5 0 −5 −10 −15 −20
−15 0
2
4
6
8
10
12
14
16
18
20
cas [h]
(a) Pondˇel´ı
22
−25 0
2
4
6
8
10
12
14
16
18
cas [h]
´ y (b) Uter´
Obr´azek 4.4: Odchylky od poˇzadovan´ ych z´asob produkt˚ u v DC Most pˇri nom. nastaven´ı
´ KAPITOLA 4. OPTIMALIZATOR
72
80 900 800 700
60
600
na sklade [ks]
na sklade [ks]
70
10° 50L KEG 10° 30L KEG 12° 50L KEG
500 400 300
50 40
10° 50L KEG 10° 30L KEG 12° 50L KEG
30 20
200
10
100
0
0 0
2
4
6
8
10
12
14
16
18
20
0
22
2
4
6
8
10
12
14
16
18
20
22
20
22
cas [h]
cas [h]
´ y – produkty (b) Uter´
(a) Pondˇel´ı – produkty 1000
400
30L KEG 50L KEG
900 800
350
na sklade [ks]
na sklade [ks]
700 600 500 400 300 200
300 30L KEG 50L KEG
250 200 150
100
100
0 0
2
4
6
8
10
12
14
16
18
cas [h]
(c) Pondˇel´ı – obaly
20
22
0
2
4
6
8
10
12
14
16
18
cas [h]
´ y – obaly (d) Uter´
Obr´azek 4.5: Stavy produkt˚ u a obal˚ u v DC Sm´ıchov pˇri nom. nastaven´ı optimalizace
4.6. VYHODNOCEN´I OPTIMALIZACE
73
Tabulka 4.7: Transport ze sm´ıchovsk´eho skladu do DC Most v pondˇel´ı – nom. nastaven´ı ˇ a Cas
10◦ 50Lb
10◦ 30Lc
12◦ 50Ld
30L KEGe
50L KEGf
Celk.g
M 10:00
140
860
0
0
0
1000
M 12:00
1000
0
0
0
0
1000
M 14:00
1000
0
0
0
0
1000
M 16:00
440
0
417
0
0
857
M 18:00
0
0
800
0
0
800
2580
860
1217
0
0
4657
Celk. aˇ
Cas proveden´ı transportu Mnoˇzstv´ı naloˇzen´ ych pades´ atilitorv´ ych sud˚ u naplnˇen´ ych 10◦ pivem v kusech c Mnoˇzstv´ı naloˇzen´ ych tˇricetilitrov´ ych sud˚ u naplnˇen´ ych 10◦ pivem v kusech d Mnoˇzstv´ı naloˇzen´ ych pades´ atilitorv´ ych sud˚ u naplnˇen´ ych 12◦ pivem v kusech e Mnoˇzstv´ı naloˇzen´ ych pr´azdn´ ych tˇricetilitrov´ ych sud˚ u v kusech f Mnoˇzstv´ı naloˇzen´ ych pr´azdn´ ych pades´ atilitorv´ ych sud˚ u v kusech g Celkovˇe naloˇzen´e mnoˇzstv´ı v kusech b
Pro u ´plnost jsou v tab. 4.8 uvedeny v´ ysledn´e hodnoty krit´eri´ı. Je zde napˇr´ıklad velice dobˇre vidˇet, ˇze pokud by mˇela b´ yt zm´ınˇen´a odchylka od reference na konci horizontu kompenzov´ana dalˇs´ı v´ yrobou, zvedla by se hodnota krit´eri´ı Jpch a Jpst penalizuj´ıc´ıch zmˇeny na lince mnohem v´ıce, neˇz by mohla klesnou hodnota Jres penalizuj´ıc´ı odchylku od poˇzadovan´e hladiny z´asob. Tabulka 4.8: Hodnoty krit´eria nomin´aln´ıho nastaven´ı optimaliz´atoru Koeficient
Hodnota
Popis
Jpst
200000
Cena za vˇsechny n´ajezdy a v´ yjezdy linky
Jpch
300000
Cena za vˇsechny zmˇeny obal˚ u a produkt˚ u na lince
Jres
397215
Cena za odchylky od referenˇcn´ı hladiny z´asob
Jtr
440000
Cena za vˇsechny proveden´e transporty
J
4.6.2
1337215
Celkov´a hodnota krit´eria
Validita v´ ystupu
Pod t´ımto ˇsirok´ ym pojmem se skr´ yv´a nejen ot´azka, zda model korektnˇe postihuje re´aln´ y proces, ale tak´e zda soubor omezuj´ıc´ıch podm´ınek je spr´avnˇe definov´an a je vyˇcerp´avaj´ıc´ı.
´ KAPITOLA 4. OPTIMALIZATOR
74
Pokud totiˇz chyb´ı nˇejak´e na prvn´ı pohled nepˇr´ıliˇs zˇrejm´e omezen´ı (napˇr´ıklad z´akaz odvozu obal˚ u od linky), tak nehledˇe na bezchybn´ y model d´av´a optimaliz´ator nelogick´e v´ ysledky. Jedn´ım z nejd˚ uleˇzitˇejˇs´ıch pˇredpoklad˚ u pro validn´ı v´ ystup optimalizaˇcn´ıho n´astroje je vˇsak dobˇre sestaven´a u ´ˇcelov´a funkce. V t´eto ot´azce je tˇreba u ´zce spolupracovat se zadavatelem. Nˇekter´a cenov´a ohodnocen´ı vˇsak jdou urˇcit jin´ ym zp˚ usobem neˇz empiricky jen velice obt´ıˇznˇe (napˇr´ıklad cena odchylky od reference). V takov´em pˇr´ıpadˇe nezb´ yv´a neˇz prov´est rozs´ahl´ y soubor test˚ u a ten vyhodnotit. V n´asleduj´ıc´ıch odstavc´ıch bude vyhodnocen vliv hodnot r˚ uzn´ ych nastaven´ı optimaliz´atoru na validitu v´ ystupn´ıho pl´anu. Jako reference bude pouˇzito nomin´aln´ıho nastaven´ı definovan´eho v pˇredchoz´ı sekci a v kaˇzd´em testu bude pozmˇenˇena pouze jedna hodnota z tab. 4.5. Protoˇze pro zobrazen´ı vˇsech dat nen´ı v t´eto pr´aci m´ısto a ani by to nepˇrispˇelo k pˇrehlednosti textu, budou vˇzdy zobrazena data, kter´a budou co nejrelevantnˇejˇs´ım zp˚ usobem ilustrovat vliv dan´eho parametru na chov´an´ı optimaliz´atoru.
Test ˇ c. 1 cres = 10000 Pokud hodnocen´ı odchylky od reference bude m´ıt hodnotu 10000 (nam´ısto 30000 v nomin´aln´ım nastaven´ı), pak lze oˇcek´avat razantn´ı zmˇeny ve v´ ysledn´em pl´anu oproti nomin´aln´ımu ˇreˇsen´ı. U stejn´eho pl´anu, jako byl vytvoˇren pˇri nomin´aln´ım nastaven´ı optimaliz´atoru, by totiˇz celkov´a hodnota krit´eria penalizuj´ıc´ıcho vˇsechny odchylky od reference byla tˇrikr´at niˇzˇs´ı neˇz v tab. 4.8, tedy 132405. V´ yroba a transport by se tak jevily mnohem draˇzˇs´ı. V tab. 4.9 jsou uvedeny hodnoty optim´aln´ıho ˇreˇsen´ı (maxim´aln´ı odchylka 10% od optima) pro cres = 10000. Je zˇrejm´e, ˇze neprobˇehl jedin´ y transport a linka po celou dobu horizontu st´ala. Pˇresto je celkov´a hodnota krit´eria niˇzˇs´ı neˇz v pˇr´ıpadˇe nomin´aln´ıho nastaven´ı cenov´ ych koeficient˚ u kriteri´aln´ı funkce v tab. 4.5. Je jasn´e, ˇze cena za odchylku cres = 10000 je pˇr´ıliˇs n´ızk´a. Tabulka 4.9: Hodnoty krit´eria pro test ˇc. 1 Koeficient
Hodnota
Popis
Jpst
0
Cena za vˇsechny n´ajezdy a v´ yjezdy linky
Jpch
0
Cena za vˇsechny zmˇeny obal˚ u a produkt˚ u na lince
Jres
457350
Jtr J
0 457350
Cena za odchylky od referenˇcn´ı hladiny z´asob Cena za vˇsechny proveden´e transporty Celkov´a hodnota krit´eria
4.6. VYHODNOCEN´I OPTIMALIZACE
75
Test ˇ c. 2 cres = 150000 V tomto testu bude naopak hodnota cenov´eho koeficientu cres oproti nomin´aln´ı hodnotˇe znaˇcnˇe nav´ yˇsena. Tlak na co nejniˇzˇs´ı hodnotu rozd´ılu od reference jiˇz pˇrevaˇzuje snahu o plynulou v´ yrobu, coˇz je zˇreteln´e na obr. 4.6. Na obr. 4.7 je patrn´a snaha optimaliz´atoru o nastaven´ı pr˚ ubˇeh˚ u zaplnˇen´ı tak, aby pr˚ umˇern´a hodnota okna (24 hodin) byla co nejniˇzˇs´ı. Toho doc´ılil kladnou odchylkou na poˇc´atku okna, kter´a se postupnˇe sniˇzuje, aˇz na konci okna je z´aporn´a, coˇz je nejl´epe vidˇet na obr. 4.7(d).
00
01
02
03
04
05
06
07
08
09
10
11
12 13 čas [h]
14
15
16
17
18
19
20
21
10° 30L KEG
10° 50L KEG
12° 50L KEG
10° 30L KEG
10° 50L KEG
Pondělí
22
23
00
Obr´azek 4.6: Gantt˚ uv diagram produkce testu ˇc. 2
Test ˇ c. 3 xabsres = 1000 Hodnota xabsres ud´av´a m´ıru penalizace absolutn´ıch odchylek11 . Hodnota 1000 znaˇc´ı, ˇze pokud bude naskladnˇeno 1000 kus˚ u v´ yrobku, jehoˇz z´asoba v dan´em skladu m´a b´ yt nulov´a, pak se cena takov´e odchylky bude rovnat cenˇe za jedno procento u relativn´ıch odchylek. ˇ ım niˇzˇs´ı tedy hodnota xabsres je, t´ım vyˇsˇs´ı je cena za absolutn´ı odchylku. Tomu odpov´ıd´a C´ nesoustavn´a v´ yroba na obr. 4.8 i niˇzˇs´ı pr˚ ubˇeh zaplnˇen´ı sm´ıchovsk´eho skladu na obr. 4.9 v porovn´an´ı s pr˚ ubˇehy nomin´aln´ıho nastaven´ı (na obr. 4.5).
Test ˇ c. 4 xabsres = 14000 Pokud bude oproti testu ˇc. 3 hodnota xabsres zv´ yˇsena, zmenˇs´ı se d˚ uraz na omezov´an´ı absolutn´ıch odchylek pˇri zachov´an´ı ceny relativn´ıch odchylek. Vliv je moˇzn´e pozorovat na obr. 4.10, kde zejm´ena z obr. 4.10(a) je patrn´e, ˇze optimaliz´ator jiˇz povol´ı urˇcit´e ˇcek´an´ı stoˇcen´eho zboˇz´ı na odvoz. U vyˇsˇs´ıch hodnot xabsres jiˇz je z hlediska cenov´e funkce levnˇejˇs´ı 11
odchylek vztaˇzen´ ych k nulov´e referenci
´ KAPITOLA 4. OPTIMALIZATOR
76
11000
11000
10000
10000 9000
na sklade [ks]
na sklade [ks]
9000 8000 10° 50L KEG 10° 30L KEG 12° 50L KEG
7000 6000
8000
6000
5000
5000
4000
4000
3000 0
2
4
6
8
10
12
14
16
18
20
10° 50L KEG 10° 30L KEG 12° 50L KEG
7000
3000 0
22
2
4
6
8
10
cas [h]
14
16
18
20
22
20
22
´ y – produkty (b) Uter´
(a) Pondˇel´ı – produkty 10
15 10° 50L KEG 10° 30L KEG 12° 50L KEG
10
10° 50L KEG 10° 30L KEG 12° 50L KEG
8
odchylka od zasoby [%]
odchylka od zasoby [%]
12
cas [h]
5
0
−5
6 4 2 0 −2 −4 −6
−10
−8 −10
0
2
4
6
8
10
12
14
16
18
cas [h]
(c) Pondˇel´ı – odchylky produkt˚ u
20
22
0
2
4
6
8
10
12
14
16
18
cas [h]
´ y – odchylky produkt˚ (d) Uter´ u
Obr´azek 4.7: Stavy produkt˚ u v DC Most a jejich odchylky od reference pˇri testu ˇc. 2
4.6. VYHODNOCEN´I OPTIMALIZACE
77
00
01
02
03
04
05
06
07
08
09
10
11
12 13 čas [h]
10° 50L KEG
12° 50L KEG
10° 30L KEG
10° 50L KEG
Pondělí
14
15
16
17
18
19
20
21
22
23
00
14
15
16
17
18
19
20
21
22
23
00
10° 50L KEG
Úterý
00
01
02
03
04
05
06
07
08
09
10
11
12 13 čas [h]
Obr´azek 4.8: Gantt˚ uv diagram produkce testu ˇc. 3
nevyr´abˇet a netransportovat. To, ˇze k tomuto doch´az´ı pˇri hodnotˇe tak bl´ızk´e nomin´aln´ı, m˚ uˇze napov´ıdat, ˇze nomin´aln´ı hodnota je pˇr´ıliˇs vysok´a.
Test ˇ c. 5 cpch = 5000 Vliv tohoto koeficientu je jasnˇe demonstrov´an na obr. 4.11. Chod linky je sice nepˇretrˇzit´ y, ale doch´az´ı k ˇcast´ ym zmˇen´am st´aˇcen´eho produktu, coˇz pom´ah´a l´epe vykr´ yvat odchylky od referenˇcn´ı hladiny z´asob. Pˇr´ıliˇsn´a hodnota koeficientu cpch by naopak vy´ ustila v omezen´ı produkce, protoˇze podobnˇe jako v testu ˇc. 1, by byla vzhledem k cenˇe za sledov´an´ı reference pˇr´ıliˇs drah´a.
Test ˇ c. 6 cpst = 0 Pˇri nulov´e penalizaci poˇctu n´ajezd˚ u a v´ yjezd˚ u linky se nejv´ıce projev´ı vliv koeficientu cpst – viz obr. 4.12. V´ yrobn´ıch blok˚ u je stejnˇe jako v nomin´aln´ım nastaven´ı, protoˇze penalizace zmˇen na lince je st´ale aplikov´ana. Pokud by i hodnota cpch byla nulov´a, pak by optim´aln´ı v´ yrobn´ı proces vypadal jako na obr. 4.13.
´ KAPITOLA 4. OPTIMALIZATOR
78
1600
900 800
1200
600
na sklade [ks]
na sklade [ks]
1400
10° 50L KEG 10° 30L KEG 12° 50L KEG
700
500 400 300
800 600 400
200 100
200
0
0
0
30L KEG 50L KEG
1000
2
4
6
8
10
12
14
16
18
20
22
0
2
4
6
8
cas [h]
10
12
14
16
18
20
22
20
22
cas [h]
(a) Pondˇel´ı – produkty
(b) Pondˇel´ı – obaly
Obr´azek 4.9: Pondˇeln´ı stavy produkt˚ u a obal˚ u ve sm´ıchovsk´em skladu pˇri testu ˇc. 3
900
900
800
10° 50L KEG 10° 30L KEG 12° 50L KEG
800 700
600
na sklade [ks]
na sklade [ks]
700
500 400 300
500 400 300
200
200
100
100
0
0
0
2
4
6
8
10
12
14
16
18
cas [h]
(a) Pondˇel´ı – produkty
20
22
30L KEG 50L KEG
600
0
2
4
6
8
10
12
14
16
18
cas [h]
(b) Pondˇel´ı – obaly
Obr´azek 4.10: Pondˇeln´ı stavy produkt˚ u a obal˚ u ve sm´ıchovsk´em skladu pˇri testu ˇc. 4
4.6. VYHODNOCEN´I OPTIMALIZACE
79
00
01
02
03
04
05
06
07
08
09
10
10° 50L KEG
10° 30L KEG
12° 50L KEG
10° 50L KEG
10° 30L KEG
Pondělí
11
12 13 čas [h]
14
15
16
17
18
19
20
21
22
23
00
20
21
22
23
00
Obr´azek 4.11: Gantt˚ uv diagram produkce testu ˇc. 5
00
01
02
03
04
05
06
07
08
09
10
11
12 13 čas [h]
12° 50L KEG
10° 30L KEG
10° 50L KEG
Pondělí
14
15
16
17
18
19
Obr´azek 4.12: Gantt˚ uv diagram produkce testu ˇc. 6
Test ˇ c. 7 tmin = 1000 = tmax Nucen´e naplnˇen´ı vˇsech transport˚ u se m˚ uˇze projevit jak ve v´ yrobˇe prodlouˇzen´ım produkce, aby byl dostatek zboˇz´ı k naplnˇen´ı n´akladn´ıho vozu, tak ve vlastn´ım poˇctu transport˚ u, kdy je moˇzn´e, ˇze urˇcit´ y transport v˚ ubec neprobˇehne z d˚ uvodu nedostatku komodit k naloˇzen´ı. To lze pozorovat pˇri porovn´an´ı obr. 4.14 a tab. 4.10 s v´ ystupem pˇri nomin´aln´ım nastaven´ı (obr. 4.2 a tab. 4.7).
Test ˇ c. 8 lma = 1, ima = 1 Nastaven´ım hodnot lma a ima na 1 dojde k obyˇcejn´emu seˇcten´ı absolutn´ıch hodnot odchylek bez pr˚ umˇerov´an´ı (na znam´enko odchylky tak nebude br´an zˇretel). Optimaliz´ator se bude snaˇzit, aby zaplnˇen´ı sklad˚ u pˇresnˇe kop´ırovalo referenci s nejmenˇs´ımi v´ ykyvy, co lze pozorovat na obr. 4.15(b). To vˇsak lze prov´est jen na u ´kor poˇzadavku na co nejkratˇs´ı setrv´an´ı stoˇcen´ ych produkt˚ u ve sm´ıchovsk´em skladˇe (obr. 4.15(a)).
´ KAPITOLA 4. OPTIMALIZATOR
80
00
01
02
03
04
05
06
07
08
09
10
11
12 13 čas [h]
14
15
16
17
18
19
10° 30L KEG
12° 50L KEG
10° 50L KEG
10° 50L KEG
12° 50L KEG
10° 30L KEG
10° 50L KEG
10° 30L KEG
10° 50L KEG
12° 50L KEG
Pondělí
20
21
22
23
00
22
23
00
Obr´azek 4.13: Gantt˚ uv diagram produkce testu ˇc. 6 pˇri cpch = 0
00
01
02
03
04
05
06
07
08
09
10
11
12 13 čas [h]
12° 50L KEG
10° 50L KEG
10° 30L KEG
Pondělí
14
15
16
17
18
19
20
21
Obr´azek 4.14: Gantt˚ uv diagram produkce testu ˇc. 7
Test ˇ c. 9 ttr = 0 Cena transportu na jednu stranu podporuje snahu o co nejmenˇs´ı produkci, protoˇze co je stoˇceno, to se mus´ı odv´ezt. Na druhou stranu z hlediska ceny dopravy nez´aleˇz´ı na ˇcasu odvozu, proto p˚ usob´ı proti sniˇzov´an´ı odchylky od reference jen nepˇr´ımo. Pokud by byl transport pˇr´ıliˇs drah´ y, pak by se nevyplatilo produkci odv´aˇzet a linku zav´aˇzet a tedy by se ani nest´aˇcelo. Oproti tomu nulov´a cena transportu sniˇzov´an´ı odchylky od hladiny z´asob nijak zvl´aˇst’ usnadnit nem˚ uˇze. V´ yjimkou je na prvn´ı pohled nelogick´e chov´an´ı, kdy pro sn´ıˇzen´ı hodnoty kriteri´aln´ı funkce optimalizace uschov´a“ produkty nebo obaly do ” n´akladn´ıho vozu, kde jsou po celou dobu transportu. Jedn´a se pak o doˇcasn´ y bezplatn´ y ” skladovac´ı prostor“. Pokud by nav´ıc bylo moˇzn´e vozit na linku produkty a z linky obaly, pak by takov´eto nastaven´ı zapˇr´ıˇc´ınilo neust´al´e transporty obˇema smˇery za u ´ˇcelem sn´ıˇzit zaplnˇen´ı sklad˚ u. Tento probl´em lze pozorovat na obr. 4.16.
4.6. VYHODNOCEN´I OPTIMALIZACE
81
1400 11000
1200
10° 50L KEG 10° 30L KEG 12° 50L KEG
9000
na sklade [ks]
na sklade [ks]
1000
10000
800 600 400
8000 10° 50L KEG 10° 30L KEG 12° 50L KEG
7000 6000 5000
200
4000
0 0
2
4
6
8
10
12
14
16
18
20
3000 0
22
2
4
6
8
10
cas [h]
12
14
16
18
20
22
16
18
20
22
cas [h]
(a) Sm´ıchov
(b) Most
Obr´azek 4.15: Pondˇeln´ı stavy produkt˚ u pˇri testu ˇc. 8
30L KEG 50L KEG
800
3500
700 3000
na sklade [ks]
na sklade [ks]
600 2500 2000 1500
500 400 300 200
1000
100 500
0
30L KEG 50L KEG 2
4
6
8
10
12
14
16
18
0 20
cas [h]
(a) Nomin´ aln´ı nastaven´ı
22
0
2
4
6
8
10
12
14
cas [h]
(b) ttr = 0
Obr´azek 4.16: Srovn´an´ı u ´tern´ıch stav˚ u obal˚ u v DC Most pro test ˇc. 9 a nom. nastaven´ı
´ KAPITOLA 4. OPTIMALIZATOR
82
Tabulka 4.10: Transport ze sm´ıchovsk´eho skladu do DC Most v pondˇel´ı pro test ˇc. 3 ˇ a Cas
10◦ 50Lb
10◦ 30Lc
12◦ 50Ld
30L KEGe
50L KEGf
Celk.g
M 12:00
140
860
0
0
0
1000
M 13:00
1000
0
0
0
0
1000
M 15:00
1000
0
0
0
0
1000
M 18:00
140
0
860
0
0
1000
2280
860
860
0
0
4000
Celk. aˇ
Cas proveden´ı transportu Mnoˇzstv´ı naloˇzen´ ych pades´ atilitorv´ ych sud˚ u naplnˇen´ ych 10◦ pivem v kusech c Mnoˇzstv´ı naloˇzen´ ych tˇricetilitrov´ ych sud˚ u naplnˇen´ ych 10◦ pivem v kusech d Mnoˇzstv´ı naloˇzen´ ych pades´ atilitorv´ ych sud˚ u naplnˇen´ ych 12◦ pivem v kusech e Mnoˇzstv´ı naloˇzen´ ych pr´ azdn´ ych tˇricetilitrov´ ych sud˚ u v kusech f Mnoˇzstv´ı naloˇzen´ ych pr´ azdn´ ych pades´ atilitorv´ ych sud˚ u v kusech g Celkovˇe naloˇzen´e mnoˇzstv´ı v kusech b
Shrnut´ı V t´eto sekci byl uk´az´an vliv koeficient˚ u kriteri´aln´ı funkce na konkr´etn´ıch pˇr´ıkladech. Lze tvrdit, ˇze zmˇeny v´ ystupu optimaliz´atoru byly v n´avaznosti na odch´ ylen´ı tvaru u ´ˇcelov´e funce od nomin´aln´ıho zcela logick´e. Chov´an´ı optimaliz´atoru se tedy jev´ı validn´ı. Proveden´ı s´erie test˚ u tak´e vzbudila ot´azku, zda souˇcasn´e nomin´aln´ı nastaven´ı je ide´aln´ı. Pravdou ovˇsem je, ˇze vˇetˇsina koeficient˚ u kriteri´aln´ı funkce je v tuto chv´ıli urˇcena empiricky a bude nutn´e, aby zadavatel dodal co nejpˇresnˇejˇs´ı jemu zn´am´e hodnoty.
4.6.3
Rychlost optimalizace
Doba, za kterou solver dojde k optim´aln´ımu ˇreˇsen´ı (potaˇzmo ˇreˇsen´ı s pˇresnˇe definovanou odchylkou od optima), z´avis´ı pˇredevˇs´ım na • pouˇzit´em solveru, • v´ ypoˇcetn´ım v´ ykonu stroje, • rozsahu probl´emu, • konkr´etn´ı podobˇe probl´emu
4.6. VYHODNOCEN´I OPTIMALIZACE
83
– tvaru omezen´ı, – tvaru u ´ˇcelov´e funkce, – typu promˇenn´ ych. Protoˇze tvar omezen´ı ani typ promˇenn´ ych nelze ovlivnit (pˇrinejmenˇs´ım zat´ım) a vˇsechny testy jsou prov´adˇeny na tomt´eˇz stroji12 , lze porovn´avat ˇcasovou n´aroˇcnost v´ ypoˇctu jen vzhledem k pouˇzit´emu solveru, rozsahu probl´emu a tvaru u ´ˇcelov´e funkce. Z´ avislost ˇ casov´ e n´ aroˇ cnosti na tvaru u ´ˇ celov´ e funkce K prozkoum´an´ı t´eto z´avislosti budou vyuˇzity v´ ysledky z testov´an´ı vlivu hodnot koeficient˚ uu ´ˇcelov´e funkce na v´ ysledn´ y optim´aln´ı pl´an. Vˇsechny tyto testy byly provedeny na solveru CPLEX a ˇcas potˇrebn´ y k z´ısk´an´ı optim´aln´ıho ˇreˇsen´ı byl zaznamen´an. V´ ysledky jsou zobrazeny v tab. 4.11. V pˇr´ıpadˇe, ˇze jsou k dipozici v´ ysledky i ze solveru SCIP, jsou v tabulce takt´eˇz zaznamen´any. Tabulka 4.11: Z´avislost ˇcasov´e n´aroˇcnosti v´ ypoˇctu na tvaru u ´ˇcelov´e funkce Nast.a
CPLEX [s]
SCIP [s]
31
541
Test ˇc. 1
2
2
Koeficient cres sn´ıˇzen na 10000
Test ˇc. 2
1291
-
Koeficient cres zv´ yˇsen na 150000
Test ˇc. 3
6269
-
Koeficient xabsres sn´ıˇzen na hodnotu 1000
Test ˇc. 4
37
183
Koeficient xabsres zv´ yˇsen na hodnotu 14000
Test ˇc. 5
44
849
Koeficient cpch sn´ıˇzen na 5000
Test ˇc. 6
36
625
Koeficinet cpst nastaven na 0
Test ˇc. 7
76
-
Transport moˇzn´e naloˇzit pouze 1000 kusy
Test ˇc. 8
91
-
D´elka a interval pr˚ umˇerovac´ıho okna nastaven´e na 1
Test ˇc. 9
87
1012
Nomin´ aln´ı
a
Popis Nomin´ aln´ı nastaven´ı koeficient˚ u
Koeficient ceny transportu nastaven na 0
Nastaven´ı koeficient˚ uu ´ˇcelov´e funkce.
Z hodnot v tab. 4.11 se d´a usuzovat, ˇze probl´em se spr´avnˇe navrˇzenou kriteri´aln´ı funkc´ı je i relativnˇe m´alo ˇcasovˇe n´aroˇcn´ y13 . Nomin´aln´ı probl´em byl totiˇz vyˇreˇsen solverem 12
Ve skuteˇcnosti na dvou stroj´ıch, solver SCIP bˇeˇz´ı na obyˇcejn´em dom´ ac´ım poˇc´ıtaˇci a cplex je provo-
zov´ an na ˇskoln´ım serveru. Protoˇze ale ani v jenom pˇr´ıpadˇe se nejedn´a o verzi schopnou paralelismu, pak v´ ykony poˇc´ıtaˇc˚ u jsou ˇra´dovˇe srovnateln´e. 13 Plat´ı pˇrirozenˇe pro tento konkr´etn´ı probl´em a nikoli obecnˇe.
´ KAPITOLA 4. OPTIMALIZATOR
84
CPLEX za dobu kratˇs´ı, neˇz kter´ ykoliv z test˚ u. Vyj´ımku tvoˇr´ı test ˇc. 1, kter´ y ovˇsem nelze v ˇz´adn´em pˇr´ıpadˇe povaˇzovat za validn´ı. Lze tedy tvrdit, ˇze pokud vypoˇcet trv´a pˇr´ıliˇs kr´atkou nebo pˇr´ıliˇs dlouhou dobu, pak je pravdˇepodobnˇe kriteri´aln´ı funkce ˇspatnˇe navrˇzena. U rozs´ahlejˇs´ıch probl´em˚ u by se vˇsak toto pravidlo dokazovalo obt´ıˇznˇe.
Z´ avislost ˇ casov´ e n´ aroˇ cnosti na pouˇ zit´ em solveru a rozsahu probl´ emu V tab. 4.11 je moˇzn´e srovnat v´ ykon solveru CPLEX se solverem SCIP. V t´eto sekci bude srovn´an´ı rozˇs´ıˇreno jeˇstˇe o solvery GLPK a LPSOLVE. V´ ysledn´e hodnoty jsou uvedeny v tab. 4.12. Chybˇej´ıc´ı hodnota znaˇc´ı, ˇze se solveru nepodaˇrilo naj´ıt optim´aln´ı ˇreˇsen´ı v pˇrijateln´em ˇcase. Pro testov´an´ı byly zvoleny probl´emy o d´elce 24, 48, 72 a 96 vzork˚ u s nomin´aln´ım nastaven´ım u ´ˇcelov´e funkce. Lze tedy pozorovat i z´avislost na rozsahu probl´emu. Tabulka 4.12: Z´avislost ˇcasov´e n´aroˇcnosti v´ ypoˇctu na pouˇzit´em solveru
a b
Ha
LPSOLVE [s]
GLPK [s]
SCIP [s]
CPLEX [s]
24
8
7
2
2
48
-
-
541
31
72
-
-
20889
3560
96
-
-
-
133030b
poˇcet vzork˚ u odchylka od optima 11%
4.6.4
M´ıra zjednoduˇ sen´ı oproti re´ aln´ emu probl´ emu
M´ırou zjednoduˇsen´ı neboli relaxac´ı probl´emu nen´ı myˇslen sn´ıˇzen´ y poˇcet komodit, sklad˚ u ˇci linek v testovac´ım probl´emu, nebot’ chov´an´ı optimaliz´atoru by bylo shodn´e i pro probl´em vˇetˇs´ıho rozmˇeru. Za relaxaci se povaˇzuje opomenut´ı nebo aproximace nˇekter´ ych subproces˚ u a vlastnost´ı logistiky, jako je • n´ajezd a v´ yjezd linky, • poˇcet nakl´adac´ıch m´ıst, • nakl´ad´an´ı v´ıce voz˚ u souˇcasnˇe.
4.6. VYHODNOCEN´I OPTIMALIZACE
85
N´ajezdu a v´ yjezdu linky byla vˇenov´ana velik´a pozornost pˇri modelov´an´ı procesu v kap. 3, proˇc je tedy nezahrnout? V pˇr´ıpadˇe lichobˇeˇzn´ıku i syst´emu druh´eho ˇr´adu se jedn´a o aproximaci komplikuj´ıc´ı v´ ysledn´ y syst´em, coˇz uˇz pˇri takto rozs´ahl´em probl´emu nen´ı ˇz´adouc´ı. Hlavn´ım d˚ uvodem vˇsak je, ˇze v obvykl´em skuteˇcn´em pl´anu st´aˇcen´ı dojde k n´abˇehu a odstaven´ı pouze jednou na poˇc´atku a na konci produkˇcn´ıho t´ ydne. V takov´em pˇr´ıpadˇe m´a pominut´ı n´ajezd˚ u na kvalitu optimalizace vliv minim´aln´ı. Poˇcet nakl´adac´ıch m´ıst je v souˇcasn´e podobˇe optimaliz´atoru omezen na hodnotu 1. Toto omezen´ı dovoluje pouˇzit´ı bin´arn´ıch promˇenn´ ych na m´ısto obecnˇe celoˇc´ıseln´ ych, coˇz m˚ uˇze urychlit v´ ypoˇcet. V tab. 4.13 jsou uvedeny doby potˇrebn´e pro nalezen´ı optim´aln´ıho ˇreˇsen´ı pro solvery CLPEX a SCIP v pˇr´ıpadech s pouˇzit´ım celoˇc´ıseln´ ych a bin´arn´ıch promˇenn´ ych pro popis transportu. Tabulka 4.13: Z´avislost ˇcasov´e n´aroˇcnosti v´ ypoˇctu na zp˚ usobu popisu transportu Solver
SCIP [s]
CPLEX [s]
Ha
binb
intc
bin
int
48
541
560
31
28
60
2169
5705
115
150
72
20889
19590
3560
872
-
133030d
124895e
96
-
a
poˇcet vzork˚ u bin´ arn´ı promˇenn´e c celoˇc´ıseln´e promˇenn´e d odchylka od optima 11% e odchylka od optima 15% b
Navzdory pˇredpoklad˚ um nezp˚ usobilo uˇzit´ı celoˇc´ıseln´ ych promˇenn´ ych pro transport v testech uveden´ ych v tab. 4.13 optimaliz´atoru nam´ısto bin´arn´ıch v´ yznamnou komplikaci probl´emu. Lze tedy poˇc´ıtat s variantou, pˇri kter´e bude v´ıce transport˚ u v tent´ yˇz vzorek umoˇznˇeno. Poˇcet transport˚ u je pak omezen poˇctem nakl´adac´ıch m´ıst s pˇrihl´ednut´ım na dobu nakl´ad´an´ı. Pokud by doba nakl´adky byla 30 minut, vzorkovac´ı perioda 1 hodina a nakl´adac´ıch m´ıst 5, pak by bˇehem vzorku mohlo b´ yt odbaveno celkem 10 transport˚ u (na vˇsech tras´ach u pˇr´ısluˇsn´eho skladu). Na druhou stranu velk´e mnoˇzstv´ı transportovan´eho zboˇz´ı nar´az by zp˚ usobilo znaˇcn´e v´ ykyvy v hladinˇe z´asob sklad˚ u, coˇz je obecnˇe nev´ yhodn´e. Proto je pravdˇepodobn´e, ˇze optimaliz´ator pˇres moˇznost vys´ılat tranport˚ u nar´az v´ıc, pouˇzije vˇetˇsinou pouze jeden.
86
´ KAPITOLA 4. OPTIMALIZATOR
Z hodnot v tab. 4.13 tak´e vypl´ yv´a, ˇze solver CPLEX dok´aˇze s obecnˇe celoˇc´ıseln´ ymi hodnotami pracovat mnohem l´epe, neˇz solver SCIP. Z´aleˇz´ı vˇsak tak´e na konkr´etn´ı podobˇe probl´emu, takˇze generalizovat, ˇze pouˇzit´ı celoˇc´ıseln´ ych promˇenn´ ych na m´ısto bin´arn´ıch uˇsetˇr´ı ˇcas, nelze.
Kapitola 5 Z´ avˇ ereˇ cn´ e vyhodnocen´ı Tato pr´ace si vzala za c´ıl prozkoumat moˇznosti usnadnˇen´ı a zefektivnˇen´ı pl´anovac´ıho procesu spoleˇcnosti Pivovary Staropramen, a. s. Souˇcasn´ y zp˚ usob pl´anov´an´ı se pot´ yk´a zejm´ena se znaˇcnou decentralizovanost´ı, kter´a v podstatˇe glob´aln´ı optimalitu ani nepˇripouˇst´ı. Probl´em je tak obs´ahl´ y, ˇze ani nen´ı moˇzn´e, aby vˇse ˇreˇsil jedin´ y ˇclovˇek. Jedn´ım z v´ ysledk˚ u t´eto pr´ace je tak´e zjiˇstˇen´ı, ˇze i pro jedin´ y v´ ypoˇcetn´ı stroj je to tˇeˇzk´ y oˇr´ıˇsek. Z´akladn´ım u ´skal´ım optimalizace tohoto procesu je totiˇz pr´avˇe jeho rozsah. Pˇrestoˇze pro ˇreˇsen´ı byly testov´any prostˇredky vyuˇz´ıvaj´ıc´ı nejpokroˇcilejˇs´ıch heuristick´ ych technik v tomto oboru, st´ale se jedn´a o prohled´av´an´ı prostoru moˇzn´ ych ˇreˇsen´ı a ten roste s kaˇzdou promˇennou exponenci´alnˇe. Kaˇzd´ y zaveden´ y produkt, sklad nebo linka nekomplikuje probl´em jen zlomkovˇe, sp´ıˇse ho n´asob´ı. Odtud plyne jasn´ y poˇzadavek na co nejvˇetˇs´ı optimalizaci popisu probl´emu z hlediska rychlosti ˇreˇsen´ı, kter´e lze doc´ılit vhodn´ ymi kompromisy, jako je napˇr´ıklad r˚ uzn´e vzorkov´an´ı v´ yroby a transportu nebo pouˇzit´ım pokroˇcilejˇs´ıch metod z´apisu probl´emu. Jednou z moˇznost´ı je napˇr´ıklad pouˇzit´ı tzv. Special Ordered Sets (SOS, [11]) pro z´apis vektoru promˇenn´ ych, z nichˇz pouze jedin´a m˚ uˇze b´ yt nenulov´a – t´ımto zp˚ usobem by bylo moˇzn´e nahradit napˇr. v´ yrobn´ı vektor souborem spojit´ ych promˇenn´ ych definovan´ ych jako SOS. Solvery pak dok´aˇz´ı s takto definovanou mnoˇzinou promˇenn´ ych pracovat efektivnˇeji pomoc´ı speci´aln´ıch algoritm˚ u. Dalˇs´ı skuteˇcnost byla, ˇze takto rozs´ahl´ y probl´em si ˇz´ad´a nem´enˇe velk´e objemy dat. K jejich z´ısk´an´ı byly pˇres naprostou vstˇr´ıcnost a ochotu zadavatele vˇenov´any cel´e mˇes´ıce a to pr´avˇe pˇredevˇs´ım z d˚ uvodu decentralizace. Pˇres veˇskerou snahu ani v okamˇzik dokonˇcen´ı t´eto pr´ace nejsou k dispozici vˇsechna potˇrebn´a data. Urˇcit´e informace chyb´ı i zadavateli (napˇr´ıklad predikce pr˚ ubˇehu stahov´an´ı pr´azdn´ ych obal˚ u z trhu). Tyto mezery byly doplnˇeny daty vytvoˇren´ ymi obvykle u ´vahou a bude d´ale na zadavateli, zda to bude 87
88
´ ERE ˇ CN ˇ E ´ VYHODNOCEN´I KAPITOLA 5. ZAV
postaˇcuj´ıc´ı. Plat´ı, ˇze v´ ystup optimaliz´atoru je vˇzdy optim´aln´ı vzhledem k nastaven´ı cenov´e funkce a vstupn´ım veliˇcin´am. Je tedy prioritou pro dalˇs´ı obdob´ı projektu z´ıskat co nejkvalitnˇejˇs´ı data pro urˇcen´ı cenov´ ych koeficient˚ u, kter´e nelze urˇcit jinak neˇz empiricky; d´ale tak´e identifikace cen, kter´e jde stanovit pˇresnˇe. V tuto chv´ıli je pˇripravena kostra optimaliz´atoru vhodn´a pro dalˇs´ı testov´an´ı a pˇr´ıpadn´e rozˇs´ıˇren´ı. Implementace je provedena ve v´ yvojov´em prostˇred´ı MATLAB se ˇskoln´ı licenc´ı za pouˇzit´ı toolboxu YALMIP, jehoˇz licence neumoˇzn ˇuje distribuci s komerˇcn´ım softwarem. ˇ sen´ı samotn´e optimalizace prob´ıhalo z vˇetˇs´ı ˇc´asti na komerˇcn´ım solveru CPLEX – opˇet Reˇ se ˇskoln´ı licenc´ı. Pˇrestoˇze k dokonˇcen´ı optimalizaˇcn´ıho n´astroje zb´ yvaj´ı jeˇstˇe roky pr´ace, je tˇreba se zamyslet nad t´ım, jak´ ym zp˚ usobem bude koneˇcn´ y n´astroj provozov´an. Nejvˇetˇs´ı flexibilitu zajist´ı souˇcasn´e uspoˇr´ad´an´ı MATLAB & YALMIP & CPLEX, avˇsak pouˇzit´ı MATLABu nevyhovuje z hlediska uˇzivatelsk´eho komfortu ani v´ ykonu. Solver CPLEX bude nutn´e pouˇz´ıt v kaˇzd´em pˇr´ıpadˇe, nebot’ tvorba dedikovan´eho solveru by jistˇe vyˇsla dr´aˇz, neˇz koupˇe licence. Funkˇcnost prostˇred´ı MATLABu, kter´ y je urˇcen zejm´ena pro v´ yvoj a testov´an´ı, by mohl nahradit software s pˇr´ıjemnˇejˇs´ım uˇzivatelsk´ ym rozhran´ım vytvoˇren´ ym napˇr´ıklad v jazyce C#. Krokem, kter´ y vˇsak bude muset pˇredch´azet rozhodnut´ı o koupi jak´ekoliv licence, bude vypracov´an´ı studie s konkr´etn´ımi hodnotami moˇzn´ ych u ´spor pˇri aplikaci optimaliz´atoru. K tomuto bude potˇreba v´ıce zdroj˚ u, neˇz bylo k dispozici pro tuto pr´aci, a to zejm´ena dlouhodob´ y pˇr´ıstup k solveru CPLEX, nebot’ testy mohou zpoˇc´atku trvat i nˇekolik dn´ı. Tyto testy budou ovˇsem urˇceny sp´ıˇse pro potˇrebu managementu za u ´ˇcelem z´ısk´an´ı souhlasu veden´ı k pˇr´ıpadn´ ym v´ ydaj˚ um za projekt. Faktem je, ˇze optimaliz´ator se spr´avnou podobou cenov´e funkce optim´aln´ı pl´an urˇc´ı, ot´azkou z˚ ust´av´a, jak dlouho mu to bude trvat. Pˇrestoˇze tato pr´ace se zab´ yv´a t´emˇeˇr v´ yhradnˇe matematick´ ym programov´an´ım, neznamen´a to, ˇze by ostatn´ı metody byly pro tento probl´em zavrˇzeny. Rozhodnˇe zaj´ımav´e by bylo zkusit aplikovat meta-heuristickou metodu genetick´eho programov´an´ı. Nespornou v´ yhodou by byla moˇznost definice libovolnˇe sloˇzit´e kriteri´aln´ı funkce bez vlivu na n´aroˇcnost probl´emu. Pokud by byl vhodnˇe vyˇreˇsen probl´em popisu jedince a zp˚ usobu kˇr´ıˇzen´ı, pak by bylo moˇzn´e z´ıskat mnoˇzstv´ı suboptim´aln´ıch ˇreˇsen´ı, pomoc´ı kter´ ych by byl proˇrez´an strom popisuj´ıc´ı prostor vˇsech ˇreˇsen´ı a urychleno ˇreˇsen´ı exaktn´ımi metodami. V´ ysledkem t´eto pr´ace nen´ı a ani nemohl b´ yt vˇseobj´ımaj´ıc´ı perfektnˇe funguj´ıc´ı optima-
89 liz´ator. Sp´ıˇse se jedn´a o n´avrh, jak´ ym smˇerem se pr´ace bude ub´ırat d´ale. Projekt takov´ ych rozmˇer˚ u si bude ˇz´adat jeˇstˇe nˇekolik let v´ yvoje, proto bylo rozhodnuto zaˇz´adat o grant Ministerstva pr˚ umyslu a obchodu. T´ım se otevˇrou moˇznosti pro intenzivnˇejˇs´ı spolupr´aci se zadavatelem. V´ yhodou odvˇetv´ı matematick´e optimalizace je velice rychl´ y v´ yvoj v´ ypoˇcetn´ı techniky a zejm´ena dneˇsn´ı trend paralelizace, kter´a velice svˇedˇc´ı napˇr. metodˇe vˇetv´ı a mez´ı. Je moˇzn´e, ˇze co n´am dnes z hlediska v´ ykonu poˇc´ıtaˇc˚ u pˇrijde takˇrka nemoˇzn´e, za p´ar let p˚ ujde zcela bez probl´em˚ u. Pot´ıˇz je ovˇsem v tom, ˇze naˇse n´aroky stoupaj´ı snad jeˇstˇe rychleji, neˇz roste schopnost je uspokojit. Proklet´ı rozmˇernosti tak nikdy nezmiz´ı.
90
´ ERE ˇ CN ˇ E ´ VYHODNOCEN´I KAPITOLA 5. ZAV
Literatura ˇa ´ k, M. Modelov´ [1] Dvor an´ı logistick´ych proces˚ u v Pivovarech Staropramen, a. s. Baˇ e vysok´e uˇcen´ı technick´e v Praze, Fakulta elektrotechnick´a, Kakal´aˇrk´a pr´ace, Cesk´ tedra ˇr´ıdic´ı techniky. 2007. [2] Turza, P. Modelov´ an´ı logistick´ych proces˚ u Pivovar˚ u Staropramen, a. s. Bakal´aˇrsk´a ˇ e vysok´e uˇcen´ı technick´e v Praze, Fakulta elektrotechnick´a, Katedra ˇr´ıdic´ı pr´ace, Cesk´ techniky. 2006. [3] Franklin, G. F., Powell, J. D. and Emami-Naeini, A. Feedback Control of Dynamic Systems. 5th edition. Prentice Hall, 2006. ˇ ˇ [4] Stecha, J. Optim´ aln´ı rozhodov´ an´ı a ˇr´ızen´ı. Vydavatelstv´ı CVUT, 2000. ˇ˚ [5] S ucha, P. Celoˇc´ıseln´e line´arn´ı programov´an´ı. 2004. URL http://dce.felk.cvut.cz/hanzalek/_private/ref/sucha_ilp.pdf [6] Boyd, S. and Vandenberghe, L. Convex Optimization. Cambridge University Press, 2004. [7] Vanderbei, J. R. Linear programming: foundations and extensions. 2nd edition. Springer Science+Business Media, Inc., 2001. [8] Kelly, J. P. Meta-Heuristics: Theory and Applications. Kluwer Academic Publishers, 1996. [9] Antsaklis, P. J. and Michel, A. N. A Linear Systems Primer. Birkh¨auser, 2007. ¨ fberg, J. YALMIP : A Toolbox for Modeling and Optimization in MATLAB. [10] Lo in Proceedings of the CACSD Conference, Taipei, Taiwan, 2004. URL http://control.ee.ethz.ch/~joloef/yalmip.php 91
92
LITERATURA
[11] Beale, E. M. L. and Forrest, J. J. H. Global optimization using special ordered sets. Mathematical Programming, vol. 10, 1976: p. 52–69.
Pˇ r´ıloha A Nomenklatura CM
Spotˇreba produkt˚ u a poˇcet vr´acen´ ych obal˚ u v kaˇzd´em kroku do kaˇzd´eho skladu (str. 61)
L
Matice v´ yroby diskr´etn´ıho modelu pro cel´ y horizont (str. 57)
S
Matice poˇc´ateˇcn´ıho stavu skladov´an´ı diskr. modelu pro cel´ y horizont (str. 57)
S
Matice skladov´an´ı diskr´etn´ıho modelu pro cel´ y horizont (str. 56)
T
Matice transportu diskr´etn´ıho modelu pro cel´ y horizont (str. 56)
c(t)
Vektor toku obal˚ u na linku (str. 14)
CD
Matice kapacit linek diskr´etn´ıho modelu (str. 58)
C ef
Matice efektivn´ıch kapacit linky (str. 16)
C nom
Matice nomin´aln´ıch kapacit linky (str. 16)
D
Matice vzd´alenost´ı sklad˚ u ud´avan´ ych v hodin´ach (str. 34)
L
Produkˇcn´ı matice (str. 18)
L(t)
Matice v´ yroby (str. 36)
l(t)
V´ yrobn´ı vektor (str. 14)
lt (t)
Transformovan´ y v´ yrobn´ı vektor (str. 26)
P
Matice pˇr´ısluˇsnosti linek (str. 36) I
ˇ ´ILOHA A. NOMENKLATURA PR
II p(t)
Vektor toku produkt˚ u z linky (str. 14)
P Dd
Matice pˇriˇrazen´ı produkce linek ke sklad˚ um diskr´etn´ıho modelu pro cel´ y horizont (str. 58)
PD
Matice pˇriˇrazen´ı linek ke sklad˚ um diskr. modelu pro cel´ y horizont (str. 57)
R
Matice smˇeˇrov´an´ı (str. 37)
RD
Matice smˇeˇrov´an´ı tras diskr´etn´ıho modelu pro cel´ y horizont (str. 58)
RE
Matice receptury (str. 15)
RL
Matice smˇeˇrov´an´ı pro nakl´ad´an´ı (str. 37)
RU
Matice smˇeˇrov´an´ı pro vykl´ad´an´ı (str. 37)
S(t)
Matice skladov´an´ı (str. 35)
sl (t)
Vektor okamˇzit´e produkce v´ yrobk˚ u a spotˇreby obal˚ u modelem linky (str. 14)
t(t)
Vektor toku transportovan´ ych produkt˚ u a obal˚ u po urˇcit´e trase (str. 33)
T L (t)
Matice transportu – nakl´ad´an´ı (str. 36)
tL (t)
Vektor toku nakl´adan´ ych produkt˚ u a obal˚ u na urˇcit´e trase (str. 33)
T PALP (t)
Transformaˇcn´ı matice ks → PALP (str. 31)
T U (t)
Matice transportu – vykl´ad´an´ı (str. 36)
tU (t)
Vektor toku vykl´adan´ ych produkt˚ u a obal˚ u na urˇcit´e trase (str. 33)
W
Matice produkˇcn´ıch ztr´at (str. 17)
Cs
Kapacita skladu (str. 31)
H
D´elka ˇcasov´eho horizontu pl´anu (str. 62)
m
Poˇcet komodit (produkt˚ u a obal˚ u) (str. 11)
mc
Poˇcet obal˚ u (str. 11)
mp
Poˇcet produkt˚ u (str. 11)
III nt
Poˇcet tras (str. 35)
p
Poˇcet linek (str. 30)
r(t)
Vstupn´ı sign´al transformace (str. 20)
rL
Poˇcet tras vedouc´ıch z urˇcit´eho skladu (str. 30)
rU
Poˇcet tras vedouc´ıch do urˇcit´eho skladu (str. 30)
sPALPc (t)
Celkovˇe uskladnˇen´e mnoˇzstv´ı v urˇcit´em skladˇe v paletov´ ych m´ıstech (str. 31)
sPALPc (t)
Vektor uskladnˇen´ ych mnoˇzstv´ı v urˇcit´em skladˇe v kusech (str. 30)
sPALPc (t)
Vektor uskladnˇen´ ych mnoˇzstv´ı v urˇcit´em skladˇe v pal. m´ıstech (str. 31)
Td
Dopravn´ı zpoˇzdˇen´ı linky (str. 17)
Tl
Doba nakl´adky na transport (str. 33)
Tn
Doba n´abˇehu linky (str. 17)
To
Doba pˇrekryvu (str. 27)
Ttd
ˇ Casov´ a vzd´alenost urˇcit´ ych sklad˚ u v hodin´ach (str. 33)
z(t)
Transformovan´ y sign´al (str. 20)
IV
ˇ ´ILOHA A. NOMENKLATURA PR
Pˇ r´ıloha B Obsah pˇ riloˇ zen´ eho CD • Diplomov´a pr´ace ve form´atu PDF, • v´ ystupn´ı PDF soubory generovan´e optimaliz´atorem.
V
