Plati tvarkaraščių sudarymo uždavinio sritis yra industrinių, taip vadinamų gamybinių, tvarkarščių sudarymas. Yra trys gaminių tvarkaraščių klasės: darbų fabrikas, atvirasis fabrikas ir srautinis fabrikas. Bendra uždavinio specifikacija gali būti apibrėžta tokiu būdu: yra darbų aibė ir mašinų aibė, kurios tarpusavyje turi sąveikauti tam tikru specifiniu būdu. Paprastai šios problemos yra sunkiai išsprendžiamos tradiciniais (tiksliaisias) metodais. Metaeuristiniai algoritmai dažniausiai pateikia tiktai artimus optimumui sprendinius, tačiau per apibrėžtą laiką.
Šiame darbe įgyvendinta keletas metaeuristikų: genetiniai algoritmai (besiskiriantys jų parametrų reikšmėmis) ir tabu paieškos algoritmai (besiskiriantys sprendinio aplinka). Kai kurios genetinio algoritmo strategijos pasiūlytos kaip genetinio algoritmo parametrų tyrimo išvada. Aštuoni algoritmai yra tiriami atsitiktinėms gamybinių tvarkaraščių sudarymo problemoms, lyginant pradinius sprendinius ir minimumus, pasiektus sprendinius ir minimumus, skaičiavimo trukmes ir skirtumą tarp pradinių bei pasiektų sprendinių.
Pabaigoje pateikiama išvada apie tai, kad vieno tipo genetiniai parametrai (kryžminimo ir mutacijos lygiai) yra ypač reikalingi algoritmo konvergavimo, diversifikacijos ir intensifikacijos prasme, kito tipo (iteracijų skaičius ir populiacijos dydis) turi priklausyti nuo resursų, trečio tipo (elitizmas) yra geri “buferiai”. Galiausiai, kuomet paprasčiausios formos tabu paieška yra silpnesis konkurentas... [toliau žr. visą tekstą] / A wide area of scheduling problem is industrial so called shop scheduling. There are three classes of shop scheduling: Job Shop, Open Shop and Flow Shop. General problem specification could be specified as follows: there is set of jobs and set of machines, which should interact with each other in some specific way. Typically these problems are hard to solve in traditional (exact) methods. Metaheuristics algorithms mostly produce only nearby-optima, but in proper time.
We implemented several metaheuristics: genetic algorithms (separated by values of their parameters) and several Tabu search algorithms (separated by neighborhood of solution). Some strategies of genetic algorithms are suggested as conclusion of genetic algorithm parameter research. Eight algorithms are examined for random shop scheduling problems in terms of initial solutions and minimum, gained solutions and minimum, processing time and difference between initial and gained solutions.
In the end, author concludes, that one kind of genetic parameters (crossover and mutation rates) are especially demanding in sense of algorithm convergence, diversification and intensification aspects, other (number of iterations and population size) should depend on resources, third (elitism) is good “buffers”. Finally, while with its simplest form, Tabu search seems to be less competitive in algorithm effectiveness research, its dynamic modification outperforms all proposed genetic algorithms, but both – tabu search with... [to full text]
| Identifer | oai:union.ndltd.org:LABT_ETD/oai:elaba.lt:LT-eLABa-0001:E.02~2008~D_20080716_112811-81808 |
| Date | 16 July 2008 |
| Creators | Šakurovas, Edgaras |
| Contributors | Saulis, Leonas, Valakevičius, Eimutis, Aksomaitis, Algimantas Jonas, Janilionis, Vytautas, Navickas, Zenonas, Pekarskas, Vidmantas Povilas, Rudzkis, Rimantas, Listopadskis, Narimantas, Misevičius, Alfonsas, Kaunas University of Technology |
| Publisher | Lithuanian Academic Libraries Network (LABT), Kaunas University of Technology |
| Source Sets | Lithuanian ETD submission system |
| Language | Lithuanian |
| Detected Language | Unknown |
| Type | Master thesis |
| Format | application/pdf |
| Source | http://vddb.library.lt/obj/LT-eLABa-0001:E.02~2008~D_20080716_112811-81808 |
| Rights | Unrestricted |
Page generated in 0.0031 seconds