Flow-Shop uždavinys

Uždavinio aprašymas

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 r_i

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ę r_i. Tuoment yra generuojamas atsitiktinis skaičius nuo 0.0 iki SUM(r_i). 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

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į.
   
   • Iš lokalaus failo diske (tam reikia leisti java skaityti failus diske)
   • Įvedant interaktyviai. Šiuo režimu galima duomenis ir perduoti per sisteminę viešąją atmintį (Clipboard).
   • Iš failo Internete (bene patogiausias būdas ir jau yra paruoštas testinių duomenų failas data.txt)
   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 darbų prioritetų taisyklė (heuristika): ilgiausio darbo, ilgiausio likusio laiko ir Gupta arba atsitiktinį pasirinkimą iš jų su tikimybėmis x. Visų svorių suma turi būti lygi 1.0

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 viršuje reikia pasirinkti bandymą ir bus pademonstruotas jo rezultatas. Galima padaryti iki 10 bandymų. Tokiu būdu programa leidžia ekspertui parinkti geriausius tikimybinės funkcijos r(h_i) parametrus x[1], x[2], x[3].