Flow-Shop uždavinio aprašymas

2003, VGTU, Lauras Čeponis, doktorantas

Įvadas

Dokumente aprašoma Flow-Shop optimizavimo uždavinio realizacija. Tai optimizavimo teorijos ir praktikos kurso praktinis darbas. Darbą atliko ir dokumentą paruošė Lauras Čeponis, VGTU doktorantas. Darbą priėmė prof. Jonas Mockus.

Uždavinio aprašymas

Uždavinio samprata

Flow-Shop priklauso tvarkarasčio optimizavino uždavinių klasei. Šiame uždavinyje reikia parinkti tokią vienodos sekos, tačiau skirtingos trukmės darbų eilės tvarką, kad bendras atlikimo laikas būtų trumpiausias. Uždavinį gerai iliustruoja siuvykla: vienoda užduočių seka yra dažymas, kirpimas, siuvimas lyginimas. Kadangi siuvami skirtingi drabužiai, tai darbų sekos yra skirtingos trukmės, todėl svarbu gerai išdėstyti darbus. Pavyzdžiui pradedame darbą nuo palto, nes jam reikia daugiausia darbo, o smulkesnius drabužius po jo.

Optimizavimo principai

Optimizavimo metu atliekama daug iteracijų, kurių metu ieškomas vis geresnis rezultatas. Flow-Shop uždavinyje vienos iteracijos metu optimizuojama gali būti dviem būdais:

  1. Parenkama pradinė darbų seka. Vienos iteracijos metu joje yra sukeičiami du darbai vietomis ir patikrinama gautas bendras laikas yra trumpesnis arba ilgesnis. Darbai, kuris bus sukeistas ir kuris bus parinktas išrenkami pagal vieną kelių taisyklių (heuristiką). Šis būdas dar vadinamas sukeitimų (angl. permutation) būdu.
  2. Darbų seka yra sudaroma nuo pradžių nuosekliai parenkant darbus. Kuris darbas bus parinktas sekantis priklauso nuo pasirinktos vienos iš kelių taisyklių (heuristikų). Šis būdas dar vadinamas godžiu (greedy)

Jei aprašytuose būduose griežtai laikomasi taisyklių, tai heuristikos vadinamos grynomis (angl. greedy). Jei taisyklė taikoma su tam tikra tikimybe, tai heuristikos vadinamos išsibarčiusiomis (angl. randomized). Pastaruoju atveju sprendimai daromi su tam tikra teisingumo tikimybe ri

Darbe yra naudojamas antrasis optimizavimo būdas, kai darbai pradedami dėti į tuščią seką, kol sekoje dalyvauja visi darbai.

Optimizavimo algoritmas

Uždavinyje yra du svarbūs parametrai: Darbų skaičius ir Mašinų skaičius. Kiekvienam darbui atlikti reikia vienodos mašinų sekos. Tačiau mašinos atliekamas etapas gali skirtis įvairiuose darbuose. Šiame uždavinyje tikslo funkcija yra visų darbų pabaiga - reikia kuo greičiau atlikti visus darbus.

Kiekvienos iteracijos metu yra užpildoma visa darbų seka. Tai atliekama per tiek žingsnių, kiek yra darbų. Kiekvieno žingsnio metu yra suskaičiuojamos tų darbų heuristikos, kurios dar sekoje nepanaudotos. Šios heuristikos yra panaudojamos apskaičiuojant kiekvieno darbo panaudojimo tikimybę ri. Tuoment yra generuojamas atsitiktinis skaičius nuo 0.0 iki SUM(ri). Sekantis darbas yra parenkamas pagal tai, į kurios tikimybės reikšmių intervalą patenko tas atsitiktinis skaičius.

Apskaičiuojant darbų heuristikas ir panaudojimo tikimybes naudojamos ta formulės, kurios buvo pasirinktos darbų parametruose.

Kievienos iteracijos metu tikslo funkcijos reikšmė nėra įsimenama - kievienoje iteracijoje gautas tvarkaraštis yra palyginamas su geriausiu iki tol. Jei rezultatas geresnis, jis tampa geriausiu.

Naudojimosi instrukcija

Diegimas

Pirmiausia reikia įsitikinti, kad kataloge yra tinkama failų išdėstymo struktūra. Pasirinktame kataloge turi būti pradinių kodų failai ( *.java ), paleidžiamasis failas FlowShop.htm ir kompiliavimo failas ( compile.bat arba compile.sh ). Tai pat tame kataloge turi būti katalogas FlowShop, o jame sukompiliuoti programos moduliai ( *.class ). Jei modulių nėra, juos reikia sukompiliuoti. Plačiau apie tai skaitykite Kompiliavimo instrukcijoje.

Programa paleidžiama kaip interneto naršyklės apletas. Tam reikia akyvuoti HTML failą FlowShop.htm arba iškviesti JAVA apletų aktyvavimo priemonę appletviewer FlowShop.htm.

Kompiliavimas

Kompiliavimą atlieka komandiniai failai compile.bat (Windows OS) ir compile.sh (Unix OS). Juose abejuose reikia pakeisti kelia iki katalogo, kuriame guli pradiniai kodai (kintamasis WORKING_DIR) ir (jei reikia) nurodyti kelia iki kompiliatoriaus javac (kintamasis COMPILER).

Naudojimasis

Programa intuityviai nurodo atlikti keturis paruošiamuosius žingsnius:

  1. Nurodome uždavinio pagrindinius parametrus: Darbų skaičių, Mašinų skaičių, Iteracijų skaičių.
  2. Pasirenkame duomenų šaltinį.
    Duomenų šaltinyje gali būti ir daugiau duomenų negu reikia - bus paimtas tik nurodytas duomenų kiekis. Duomenys turi būti įvesti stulpeliu - iš pradžių visi pirmojo darbo visų etapų laikai, tuomet antrojo ir t.t.
  3. Pasirenkama išbarstymo (angl. randomization) funkcija. Tai gali būti Taylor, Legendre ir Delta. Juose maksimalus dėmenų skaičius yra 3. Atitinkamai šalia nurodomas kiekvieno dėmens svoris. Visų svorių suma turi būti lygi 1.0. Priešingu atveju programa praneš apie klaidą.
  4. Pasirenkama darbų prioritetų taisyklė (heuristika): ilgiausio darbo, ilgiausio likusio laiko ir Gupta

Atlikus paruošiamuosius darbus spaudžiame mygtuką Calculate. Jei jis neaktyvus, tai reiškia, kad duomenys nuskaityti nesėkmingai.

Kai suskaičiuojami rezultatai, juos galima peržiurėti paspaudus mygtuka View Results. Analizes lango apačioje reikia pasirinkti bandymą ir bus pademonstruotas jo rezultatas. Galima padaryti iki 10 bandymų ir juos tada peržiurinėti analizės lange. Tokiu būdu programa leidžia ekspertui parinkti geriausius tikimybinės funkcijos r(hi) parametrus x[1], x[2], x[3].

Adresai

Sukurta birželio 04, 2003