Adam+Tynski.pdf

(1158 KB) Pobierz
Naprawachr¦kopisu
INSTYTUTINFORMATYKI,AUTOMATYKIIROBOTYKI
POLITECHNIKIWROCAWSKIEJ
Raportserii:PREPRINTYnrPRE-32/2006
Zagadnienia szeregowania zada«
zuwzgl¦dnieniemtransportu.
Modele,wªasno±ciialgorytmy
(rozprawadoktorska)
AdamTy«ski
PROMOTOR:
Prof.drhab.in».CzesªawSmutnicki
Sªowakluczowe:
{ optymalizacja
{ szeregowaniezada«
{ transport
{ AGV
{ algorytmyprzybli»one
WROCAW
czerwiec2006
Spistre±ci
Streszczenie
v
Abstract
vii
1 Wprowadzenie 1
1.1 Tezypracy . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Zakrespracy . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2 Problemy szeregowania zada« 5
2.1 Klasykacjaproblemów . . . . . . . . . . . . . . . . . . . . 6
2.1.1 Permutacyjnyproblemprzepªywowy . . . . . . . . . 10
2.1.2 Problemgniazdowy . . . . . . . . . . . . . . . . . . 11
2.2 Algorytmyrozwi¡zywaniaproblemówszeregowaniazada« . 13
2.2.1 Algorytmyposzukiwa«zzabronieniami . . . . . . . 15
2.2.2 Algorytmysymulowanegowy»arzania . . . . . . . . 16
2.2.3 Algorytmygenetyczne . . . . . . . . . . . . . . . . . 17
2.2.4 Algorytmyposzukiwaniarozproszonego . . . . . . . 19
2.3 Metodybadaniajako±cialgorytmówheurystycznych . . . . 20
2.4 Problematykatransportuwelastycznychsystemachproduk-
cyjnych . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3 Wªasno±ciproblemugniazdowegozustalonymprzydziaªem
wózków AGV 29
3.1 Modelmatematyczny. . . . . . . . . . . . . . . . . . . . . . 30
3.1.1 Modelpermutacyjno-grafowy . . . . . . . . . . . . . 33
3.1.2 Przykªadilustracyjny . . . . . . . . . . . . . . . . . 34
3.2 Zbioryruchówis¡siedztwa . . . . . . . . . . . . . . . . . . 37
3.2.1 Efektywnametodaprzegl¡dus¡siedztwa . . . . . . . 45
3.3 Wªasno±cigrafuipermutacjicz¦±ciowej . . . . . . . . . . . 49
3.3.1 Efektywnametodawyznaczanianajlepszejpozycji . 56
3.4 Wªasno±ciprzestrzenirozwi¡za« . . . . . . . . . . . . . . . 60
i
3.4.1 Miaryodlegªo±ci . . . . . . . . . . . . . . . . . . . . 61
3.4.2 Wielkadolina . . . . . . . . . . . . . . . . . . . . . . 62
3.4.3 Innewªasno±ciprzestrzenirozwi¡za«dopuszczalnych 65
3.5 Wnioskiiuwagi. . . . . . . . . . . . . . . . . . . . . . . . . 67
4 Algorytmyrozwi¡zywaniaproblemu gniazdowego zustalo-
nym przydziaªem wózków AGV 69
4.1 Algorytmykonstrukcyjne . . . . . . . . . . . . . . . . . . . 70
4.1.1 Algorytmypriorytetowe . . . . . . . . . . . . . . . . 70
4.1.2 Algorytmtypuwstaw . . . . . . . . . . . . . . . . . 72
4.2 Algorytmylokalnychposzukiwa« . . . . . . . . . . . . . . . 72
4.2.1 Algorytmyposzukiwa«zzabronieniamiiposzukiwa-
niarozproszonego . . . . . . . . . . . . . . . . . . . 73
4.2.2 Algorytmsymulowanegowy»arzania . . . . . . . . . 77
4.2.3 Algorytmygenetyczne . . . . . . . . . . . . . . . . . 81
4.3 Wynikibada«numerycznych . . . . . . . . . . . . . . . . . 88
4.3.1 Instancjetestowe . . . . . . . . . . . . . . . . . . . . 89
4.3.2 Wynikibada«algorytmówkonstrukcyjnych . . . . . 90
4.3.3 Wynikibada«algorytmówpopraw{instancjeTR . 93
4.3.4 Wynikibada«algorytmówpopraw{instancjeHK . 99
4.4 Wnioskiiuwagi. . . . . . . . . . . . . . . . . . . . . . . . . 104
5 Problem gniazdowy ze swobodnym przydziaªem wóz-
ków AGV 107
5.1 Modelmatematyczny. . . . . . . . . . . . . . . . . . . . . . 108
5.1.1 Modelpermutacyjno-grafowy . . . . . . . . . . . . . 110
5.2 Wªasno±cigrafuipermutacjicz¦±ciowej . . . . . . . . . . . 111
5.2.1 Efektywna metoda wyznaczania najlepszej maszyny
ipozycji . . . . . . . . . . . . . . . . . . . . . . . . . 113
5.3 Zbiórruchówis¡siedztwo . . . . . . . . . . . . . . . . . . . 117
5.3.1 Efektywnametodaprzegl¡dus¡siedztwa . . . . . . . 118
5.4 Algorytmykonstrukcyjne . . . . . . . . . . . . . . . . . . . 122
5.4.1 Algorytmypriorytetowe . . . . . . . . . . . . . . . . 123
5.4.2 Algorytmtypuwstaw . . . . . . . . . . . . . . . . . 125
5.5 Algorytmylokalnychposzukiwa« . . . . . . . . . . . . . . . 126
5.5.1 Algorytmposzukiwa«zzabronieniami . . . . . . . . 127
5.5.2 Algorytmgenetyczny. . . . . . . . . . . . . . . . . . 130
5.6 Wynikibada«numerycznych . . . . . . . . . . . . . . . . . 132
5.6.1 Instancjetestowe . . . . . . . . . . . . . . . . . . . . 133
5.6.2 Wynikibada«algorytmówkonstrukcyjnych . . . . . 134
5.6.3 Wynikibada«algorytmówpopraw{instancjeTM . 137
ii
5.6.4 Wynikibada«algorytmówpopraw{instancjeEX . 141
5.7 Wnioskiiuwagi. . . . . . . . . . . . . . . . . . . . . . . . . 147
6 Problem przepªywowy z jednym wózkiem AGV 149
6.1 Modelmatematyczny. . . . . . . . . . . . . . . . . . . . . . 150
6.1.1 Modelpermutacyjno-grafowy . . . . . . . . . . . . . 154
6.1.2 Przykªadilustracyjny . . . . . . . . . . . . . . . . . 155
6.1.3 Politykapracywózka. . . . . . . . . . . . . . . . . . 158
6.2 Eliminacyjnewªasno±ciblokówzada«. . . . . . . . . . . . . 159
6.3 Algorytmyrozwi¡zywaniaproblemu . . . . . . . . . . . . . 163
6.4 Wynikibada«numerycznych . . . . . . . . . . . . . . . . . 167
6.5 Wnioskiiuwagi. . . . . . . . . . . . . . . . . . . . . . . . . 172
7 Wnioski ko«cowe
175
Literatura
177
Spis tabel
189
Spis rysunków
191
iii
Streszczenie
Pracadotyczyproblemówoptymalizacjirównoczesnegoplanowaniaza-
da« i zarz¡dzania transportem w elastycznych systemach produkcyjnych
(ESP, ang. exible manufacturing system ). ESP to system wytwarzania
zªo»onyzwpeªnizautomatyzowanychpodsystemówwykonawczych,maga-
zynowychitransportowych,którychpracajestkoordynowanaprzezkom-
puterowy system sterowania. Ze wzgl¦du na determinizm funkcjonowania
ESPjakonarz¦dziedoanalizyioptymalizacjijegopracywykorzystywana
mo»eby¢deterministycznateoriaszeregowaniazada«.Wrozprawierozwa-
»anosystemautomatycznegotransporturealizowanegoprzezwózkiAGV(z
ró»n¡polityk¡obsªugi)orazprzepªywow¡igniazdow¡struktur¦stanowisk
dlaprzepªywudowolnychzada«.Zakryteriumprzyj¦tomomentzako«cze-
nia wykonywania wszystkich zada« (maksymalny stopie« wykorzystania
parku maszynowego). W pracy proponuje si¦ modele i algorytmy rozwi¡-
zywania postawionych zagadnie«, które pozwalaj¡ na coraz doskonalsze
modelowaniefunkcjonowaniacorazwi¦kszejgrupyrzeczywistychsystemów
produkcyjnych,cozkoleideterminujewzrostwydajno±ciichpracy.Szcze-
góln¡ uwag¦ zwrócono na efektywno±¢ proponowanych algorytmów w ich
zastosowaniachwstrukturachsterowaniaESP.
Naprac¦skªadasi¦7rozdziaªów.Wrozdzialepierwszymzawartes¡te-
zy,celizakrespracy.Rozdziaªdrugizawierawprowadzeniewproblematyk¦,
podstawowedenicje,problemyszeregowaniastanowi¡cebaz¦douogólnie«
w dalszej cz¦±ci pracy, klasyczne i najnowsze tendencje w optymalizacji
dyskretnejorazaktualnystanwiedzynatematrozwi¡zywaniaproblemów
szeregowaniazada«zuwzgl¦dnieniemogranicze«transportowych.Rozdzia-
ªy3-6stanowi¡zasadnicz¡cz¦±¢pracy,wktórejzaprezentowanes¡orygi-
nalnerezultatyuzyskaneprzezautora.
Wrozdzialetrzecimrozwa»asi¦ESPostrukturzegniazdowejzezbiorem
dedykowanychwózkówAGVwkontek±cieogólnychiszczególnychwªasno-
±ci zagadnienia. Dla tego problemu zaproponowano model matematyczny
(kombinatoryczny)wrazzwygodn¡doanalizyreprezentacj¡permutacyjno-
grafow¡, uwzgl¦dniaj¡cy szczególnie praktyczny tryb pracy wózków ÿza-
bierzizostaw".Korzystaj¡czwprowadzonejreprezentacjirozwi¡zania,za-
proponowanolokalnes¡siedztwogenerowanewoparciuoruchytypuzamie«
s¡siednieoperacje,dedykowanedlaspecjalizowanychalgorytmówposzuki-
wa«lokalnych.Dzi¦kiwykazaniupewnychwªasno±citeoretycznychs¡siedz-
twa,zaprezentowanowysoceefektywn¡metod¦jegoprzegl¡du.Wykazano
dodatkowo nowe wªasno±ci tzw. grafu cz¦±ciowego, szczególnie przydatne
dlaniektórychalgorytmówkonstrukcyjnychis¡siedztwgenerowanychprzez
ruchy typu "wstaw". Uzupeªnieniem przedstawionych wªasno±ci s¡ ekspe-
v

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin