Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
16
Rozdział2.Dwumaszynowyproblemprzepływowyzminimalizacjąsumykosztów
(tj.eliminowaniarozwiązańprzezprzeglądpośredni).Pomimotegobędziemyjestosowa-
liwkonstrukcjialgorytmuprzeszukiwaniaztabu.Przeprowadzoneliczneeksperymenty
obliczeniowewykazały,żedziękinimnastąpiłoznaczneskrócenieczasuobliczeńoraz
poprawawartościwyznaczanychrozwiązań.
2.1.Wstęp
Wdwumaszynowymproblemieprzepływowymzminimalizacjąsumykosztówspóź-
nień(ang.totaltardinessminimalizationintwomachineflowshopproblem,którywskrócie
będziemyoznaczaliprzezT2FS),każdeznzadańnależywykonaćkolejnonapierwszej,
anastępnienadrugiejmaszynie.Danesączasywykonywaniazadańoraznajpóźniej-
szeterminyichzakończenia(nadrugiejmaszynie).Przekroczenietegoterminupowodu-
jenaliczaniekary,którazależyododwielkościspóźnieniaorazstałegowspółczynnika
kary.Należywyznaczyćkolejnośćwykonywaniazadań(takąsamąnaobumaszynach),
któraminimalizujesumękar.Rozpatrywanyproblemszeregowaniazadańjestuogólnie-
niemNP-trudnego,jednomaszynowegoproblemuzminimalizacjęsumykarzaspóźnienia
1||ΣwźTź.Dokładnyopistegoproblemu,jegospecyficznewłasnościorazbardzoefek-
tywnyalgorytmopartynametodzieprzeszukiwaniaztabuzamieszczonowpracyBożejko,
GrabowskiiWodecki[5].Zawartetamwłasnościsąpewnymrozwinięciemideizawartych
wpracachWodeckiego[39]oraz[40]dotyczącychproblemówwielomaszynowychzsu-
mokosztowymifunkcjamicelu.Wtymrozdzialeprzedstawiamydokładnyopisrozpatry-
wanegoproblemuorazjegomodelmatematyczny.Dowodzimyspecyficznychwłasności
(tzw."własnościeliminacyjnychbloków"),któreznaczniepoprawiająefektywnośćalgoryt-
mówrozwiązywaniawielomaszynowychproblemówzkryteriumCmaxorazjednomaszy-
nowychzminimalizacjąsumykosztówspóźnień.Wprzypadkuichzastosowaniawkon-
strukcjachalgorytmówopartychnametodzielokalnychposzukiwańnastępujeznaczne
zmniejszeniegenerowanego,wkażdejiteracjiotoczenia.Dwumaszynowyproblemprze-
pływowyzkryteriumCmax(tj.minimalizacjąmomentuzakończeniawykonywaniawszyst-
kichzadań)jestproblememwielomianowym(algortmJohnsona).Natomiast,zkryterium
sumokosztowymΣwźTźnależydoklasyproblemówNP-trudnych.
Wrozpatrywanymproblemieszeregowanianadwóchmaszynachkolejnośćwykony-
waniazadańnakażdejmaszyniejesttakasama.Podobneproblemywystępująwlitera-
turzezarównozdodatkowymiograniczeniami,jakiróżnymikryteriami.WpracySchalle-
ra[32]przedstawionodwumaszynowyproblemprzepływowyzkryteriumsumyspóźnień
(ang.totaltardiness,F2||ΣTźjtj.bezwagspóźnień).Podano5własnościeliminacyj-
nychpostaci:"jeślizachodząpewnezależnościpomiędzyparametramizadańźik,to
