The object of Master Thesis is the creation and research optimization of blank realization procedures. Four main parts comprise the thesis: analysis of the problem, theoretical solutions, research and outcomes, conclusions and recommendations. Optimization methods, their advantages and limitations have been analyzed in the first part. The most appropriate optimization method for problem solving was selected. Designed optimization methods have been presented in the theoretical solutions part: exhaustive search, tabu search and a new one, presented by the author. A program was created for comparison of these methods. In the third part of the thesis outcomes of the research are presented. Designed methods were tested and compared by their routes length, process time, computations duration and other parameters. Conclusions of the thesis and recommendations for implementation of analyzed procedures have been presented in the part of conclusions. Literature in Lithuanian, English was used in preparing the thesis. There are 19 tables and 29 pictures in the thesis.

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... [toliau žr. visą tekstą] / 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.

Tabu search based algorithms are among the widely used heuristic algorithms for combinatorial optimization problems. In this project, we propose an improved enhanced tabu search algorithm for the well-known combinatorial optimization problem, the quadratic assignment problem (QAP). The new algorithm was tested on a number of instances from the library of the QAP instances  QAPLIB. The results obtained from the experiments show that the proposed algorithm appears to be superior to the earlier "pure" tabu search algorithms on many instances of the QAP.

To understand evolution, and to discover how different species are related, gene order analysis is a useful tool. Problems in this area can usually be formulated in a combinatorial language. We regard genomes as signed, or unsigned permutations, and thus evolutionary operations like inversions (reversing the order of a segment of genes) are easy to describe combinatorially. A commonly studied problem is to determine the evolutionary distance between two species. This is estimated by several combinatorial distances between gene order permutations, for instance the inversion distance. The main objective of this work was to survey the existing algorithms for genome comparison and to present new approach for solving this problem. The work led to these results: - We have surveyed existing approaches of genome comparison, namely comparison by inversion distance in signed and unsigned cases. It appeared that sorting signed genomes by inversions is done in quadratic time, but sorting unsigned genomes by inversions is NP-hard. - We have proposed the method of how to apply heuristic algorithms for sorting unsigned genomes by inversions. - We have applied tabu search and genetic algorithm to solve the sorting unsigned genomes by inversions problem. - We have experimentally proven, that the worst case solutions to sorting unsigned genomes by inversions found by heuristics (tabu search and genetic algorithm) are better then ones expected from best known approximating algorithm used for... [to full text]

Šiame darbe nagrinėjamas patobulintas tabu paieškos metodas, žinomas kaip iteratyvioji tabu paieška (ITP). Pasiūlytos kai kurios ITP metodo modifikacijos, besiremiančios tam tikromis sprendinių mutavimo (pertvarkymo) procedūromis (inversijos, įterpimai ir kt.), kurios įgalina pagerinti gaunamų sprendinių kokybę. Atlikti išsamūs sudaryto ITP algoritmo ir kitų pasiūlytų modifikacijų eksperimentiniai tyrimai, panaudojant testinius KU pavyzdžius iš KU testinių pavyzdžių bibliotekos TSPLIB. Gauti rezultatai patvirtina pasiūlytų modifikacijų pranašumą kitų ITP variantų atžvilgiu. / In this work, one of the heuristic algorithm – the iterated tabu search and its modifications are discussed. The work is organized as follows. Firstly, some basic definitions and preliminaries are given. Then, the iterated tabu search algoritm and its variants based on special type mutations are considered in more details. The ITS algorithms modifications were tested on the TSP instances from the TSP library TSPLIB. The results of this tests (experiments) are presented as well. The work is completed with the conclusions.

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]