Search

Tvarkaraščių sudarymo uždaviniai – viena iš sunkiau sprendžiamų problemų, kylančių įvairiose gamybinėse struktūrose, grupė. Darbo pradžioje supažindinama su bendrais tvarkaraščių sudarymo uždavinių bruožais ir jų sprendimo algoritmais. Detaliau nagrinėti šiame darbe parenkamas vienas sunkiausių gamybinių tvarkaraščių ir apskritai kombinatorinių optimizavimo uždavinių – darbo fabriko uždavinys (angl. job shop scheduling problem), kuris be abejo nėra tiksliai sprendžiamas per polinominį sprendimo laiką. Šio uždavinio pradiniai duomenys yra duotos darbų ir įrenginių aibės. Kiekvienas darbas apdorojamas specifine įrenginių tvarka. Uždavinio tikslas – minimizuoti visų darbų atlikimo laiką. Šiam uždaviniui spręsti pristatėme du apytikslius tabu – atkaitinimo modeliavimo bei paieškos kintamose aplinkose algoritmus, priklausančius metaeuristinių metodų šeimai. Iš tabu – atkaitinimo modeliavimo galima nesunkiai gauti paprastą tabu paiešką, tad prie dviejų minėtų algoritmų galima pridėti ir paprastąją tabu paiešką. Šiame darbe atlikta minėtų algoritmų programinė realizacija. Pristatytų algoritmų efektyvumui įvertinti ir algoritmų parametrų parinkimo rekomendacijoms pateikti, buvo pasirinkti gerai literatūroje žinomi bei sunkiau sprendžiami etaloniniai darbo fabriko uždavinių pavyzdžiai. Darbo pabaigoje pateikiamos minėtų algoritmų parametrų parinkimo rekomendacijos ir aptariamas algoritmų efektyvumas, kuris nagrinėtuose uždaviniuose nebuvo pastovus minėtų trijų algoritmų atvejais, t.y. nebuvo tokio algoritmo, kuriuo būtų visada gaunami geresni rezultatai už kitų visuose nagrinėtuose uždaviniuose ir išryškėjo uždaviniai, kurie palankesni vienam ar kitam algoritmui, tačiau nagrinėjant vidutinį efektyvumą, geresnis jis buvo gaunamas su tabu – atkaitinimo modeliavimo ir paprastos tabu paieškos algoritmų kombinacija (spręstus uždavinius priskiriant vienam iš algoritmų) nei paieškos kintamose aplinkose algoritmo atveju., At the beginning of this work we introduce to the combinatorial optimization, scheduling problems and methods used to solve them. In computer science scheduling problems is considered strongly NP-complete. The combinatorial optimization problem considered in this paper is a static job shop problem scheduling arising in the manufacturing processes. In the static job shop scheduling problem, a finite number of jobs are to be processed by a finite number of machines. Each job consists of a prederminated sequence of task operations, each of which needs to be processed without preemption for a given period of time on a given machine. Tasks of the same job cannot be processed concurrently and each job must visit each machine exactly once. A schedule is an assignment of operation to time slots on a machine. The makespan is the maximum completion time of the jobs and the objective of the job shop scheduling problem is to find a schedule that minimizes the makespan. When the size of problem increases, the computational time of the exact methods grows exponentially. Therefore, the recent research on job shop and other scheduling problems is focused on heuristic algorithms. We also presented some meta-heuristic algorithms such as Tabu search – Simulated annealing (TS/SA), Tabu Search (TS), Variable Neighborhood Search (VNS) and showed their results on some job shop instances. At the end of this work we tell recommendations about choosing suitable parameters.

Genetiniai algoritmai priklauso aproksimacinių metaeuristinių algoritmų klasei. Šiame darbe nagrinėjamas jų taikymas trijų tipų gamybinių tvarkaraščių (darbų, srautinio ir atvirojo fabriko) sudarymui. Algoritmų tyrimas atliktas, siekiant nustatyti parametrų įtaką vių trijų tipų tvarkarašių uždavinių sprendimui. Remiantis tyrimo rezultatais trys algoritmo strategijos ir jas atitinkančios parametrų kombinacijos yra pasiūlytos., Genetic algorithms are widely used in various mathematical and real world problems. They are approximate metaheuristic algorithms, commonly used for solving NP-hard problems in combinatorial optimisation. Industrial scheduling is one of the classical NP-hard problems.We analyze three classical industrial scheduling problems: job-shop, flow-shop and open-shop. Canonical genetic algorithm is applied for those problems varying its parameters.We analyze some aspects of parameters such as selecting optimal parameters of algorithm, influence on algorithm performance. Finally, three strategies of algorithm – combination of parameters and new conceptualmodel of genetic algorithm are proposed.