Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
18
Rozdział2.Dwumaszynowyproblemprzepływowyzminimalizacjąsumykosztów
lokalnychposzukiwańnastępujeznacznezmniejszeniegenerowanegowkażdejiteracji
otoczenia.ProblemprzepływowydladwóchmaszynzkryteriumCmax(tj.minimalizacją
momentuzakończeniawykonywaniawszystkichzadań)należydoklasyproblemówwie-
lomianowych,natomiastzrozważanymwtymrozdzialekryteriumsumokosztowymnależy
jużdoklasyproblemówNP-trudnych.
Listastosowanychoznaczeń
n
-
liczbazadań,
m
-
liczbamaszyn,
J
-
zbiórzadań,
pź,j
-
czaswykonywaniazadaniaźnamaszyniej,
wź
-
wagafunkcjikaryzspóźnieniezadania,
dź
-
żądanyterminzakończeniazadania,
π
-
permutacjazadań,
Y(π)
-
zbiórelementówpermutacjiπ,
o
źk
πk
M
Oź,j
Sź,j
Cź,j
Cź
Cmax
Tź
T
T−blok
qT−blok
l(π)
l
-
quasiblokzadańterminowych,
-
zbórwszystkichpermutacjielementówzJ,
-
ruchtypuwstaw(ang.insert),
-
permutacjagenerowanazπprzezruchźk
l(π),
-
zbiórmaszyn,
-
operacjazadaniaźnamaszyniej,
-
terminrozpoczęciaoperacjiOź,jj
-
terminzakończeniaoperacjiOź,jj
-
terminzakończeniazadaniaźj
-
terminzakończeniawykonywaniawszystkichzadań,
-
-
spóźnieniezadaniaźj
sumakosztówspóźnień,
-
blokzadańterminowych,
D−blok
qD−blok
-
quasiblokzadańspóźnionych,
-
blokzadańspóźnionych,
δaprd
-
średnibłądwzględnyrozwiązań.
