Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
2.1.Wstęp
17
wrozwiązaniuoptymalnymzadanieźjestprzedzadaniemk".Sąoneodpowiednikiem
podobnychwłasnościzamieszczonychwpracyRinnoyiin.[30]poświęconejproblemowi
szeregowaniazadańnajednejmaszynie1||ΣwźTź.Dziękinim,przeszukującotocze-
nie,możnapominąćwielenieoptymalnychrozwiązań.Wpracy[32],korzystajączwyni-
kówKoulamusa[22],przedstawionotakżeideędowodusilnejNP-trudnościrozważanego
wtymrozdzialeproblemu.LeeiKim[23]rozpatryjądwumaszynowyproblemprzepływo-
wyF2"ΣTźzdodatkowymograniczeniemdotyczącymmomentówdostępnościzadań
napierwszejmaszynie.Algorytmymetaheurystycznedlategoproblemusązamieszczo-
newpracyTa,iin.[35].Zkolei,algorytmyoptymalne(opartenaschemacieB&B)dla
różnychwariantówproblemuszeregowaniazadańnadwóchmaszynachzsumokoszto-
wymikryteriamisąopisanewpracach:Bankaiin.[4],Moukrimiin.[26],atakżeHamdi
iin.[15].Jakpisząautorzy,wrozsądnymczasie,możnarozwiązywaćprzykładyzliczbą
zadańnieprzekraczajcą50.Znaczniewięcejjestpracpoświęconychalgorytmomprzybli-
żonym:konstrukcyjnym,metaheurystykomorazichhybrydom.Szczególnieinteresujące
sątuprace,któreukazałysięwostatnichlatach:Hnaieniin.[16],Ahmadiiin.[1],Cheng
iin.[7],atakżeArdakaniin.[3].
WpracyAl-Salemaiin.[2]jestrozpatrywanyproblemszeregowaniazadańnadwóch
maszynachwsystemieJustinTime.Przedstawionotamalgorytmopartynametodzie
programowaniadynamicznego.Dlamałychprzykładówjesttoalgorytmoptymalny.Na-
tomiast,dlawiększychprzykładówsąstosowaniepewneodcięciapowodujące,żealgo-
rytmdziałaznacznieszybciej,jednakwyznaczonerozwiązaniasąjedyniesuboptymalne.
ZkoleiKharbecheiHaouari[21]dorozwiązaniategoproblemuzastosowalimetodępro-
gramowaniacałkowitoliczbowego.
Jeststosunkowomałopracpoświęconychwyłącznieproblemowirozpatrywanemu
wtymrozdzialeorazmetodamijegorozwiązywania.RuiziStützle[31]przedstawilialgo-
rytmzachłanny,Liaoetal.[24]algorytmopartynametodzieprzeszukiwaniaztabu.Pewne
wynikiteoretyczneorazdobrealgorytmyaproksymacyjnesąprzedstawionewpracach:
GuptyiHarariego[14],Lina[25]orazBulfinaiHallaha[6].ZkoleiKhaliliiin.[20]rozpatrują
problemoptymalizacjiwielokryterialnejzdwomafunkcjamicelu:maksymalnymczasem
zakończeniawykonywaniazadań(ang.makespan)orazważonąsumąkosztówspóźnień
(ang.totalweightedtardiness).Dojegorozwiązywaniastosująalgorytmelektromagne-
tyczny.
WdalszejczęścitegorozdziałuprzedstawiamydokładnyopisproblemuF2FSorazje-
gomodelmatematyczny.Dowodzimyspecyficznychwłasności,któreznaczniepoprawiają
efektywnośćalgorytmówrozwiązywaniawielomaszynowychproblemówszeregowaniaza-
dań.Wprzypadkuichzastosowaniawkonstrukcjachalgorytmówopartychnametodzie
