Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
Rozdział2
Dwumaszynowyproblemprzepływowy
zminimalizacjąsumykosztówspóźnień
Wwieluprocesachprodukcyjnychmamydoczynieniazprzepływemwytwarzanych
elementówwciągutechnologicznym.Poddawanesąoneoperacjomobróbkinastanowi-
skachroboczychwyposażonychw"maszyny".Wsystemachwytwarzaniadokładniena
czaswymaganejestwykonaniekażdegoelementuprzedupływemustalonegoterminu.
Zajegoprzekroczenie(spóźnienie)naliczanajestkara.Wtymprzypadkuoptymalizacja
procesuprodukcyjnegopoleganawyznaczeniutakiejkolejnościwykonywaniaelemen-
tów,któradajeoptymalneefektymierzonewartościąpewnegokryterium(np.maksymal-
negolubśredniegospóźnienia,sumąkarzaspóźnienia,itd.).
ProblemprzepływowyzminimalizacjąterminuzakończeniawykonywaniazadańCmax
należydonajtrudniejszychinajczęściejbadanychproblemówoptymalizacjidyskretnej.
Udowodnionowielejegospecyficznychwłasnościdziękiktórymmamydzisiajbardzodo-
brealgorytmymetaheurystyczne.Wprzypadkudwóchmaszynproblemtenjestwielomia-
nowy(algorytmrozwiązaniamazłożonośćO(nlnn),gdzienjestliczbązadań).Przed-
stawionywtymrozdzialedwumaszynowyproblemprzepływowyzminimalizacjąkarza
zbytpóźnewykonaniezadań(F2||ΣwźTź)należydoklasyproblemówNP-trudnych.
Maznaczniekrótsząhistorięizdecydowaniemniejpoświęconychmuprac.Ciąglejednak
brakjestspecyficznychwłasności,którebyzwiększałyefektywnośćalgorytmówdokład-
nychorazprzybliżonych.Historiarozwiązywaniaproblemuprzepływowegozkryterium
Cmaxwskazuje,żedopierozastosowaniewkonstrukcjachalgorytmów"własnościeli-
minacyjnebloków"pozwoliłonawyznaczanierozwiązańwpełniakceptowanychprzez
teoretykówjakipraktyków.Dlarozpatrywanegowtymrozdzialeproblemudefiniujemy
tzw.quasibloki,któreniestetynieposiadająidentycznychwłasnościjakklasycznebloki
