| Abstract [eng] |
At the begining of this work introduction to the scheduling problem and its basics is given. The goal of a scheduling problem is to make a schedule for a certain production situation. In the problem it is stated what must take place, and the solution describes exactly what should happen at what time. These problems occur in factories, personnel planning, transportation, airfields, railroad stations etcetera. Since mathematical descriptions of scheduling problems are often distilled from practical situations there are many variants of scheduling problems. A selection had to be made which problem is going to be a target of the study. The job shop scheduling problem was chosen. In the first chapter there is definitions of the problems we are trying to solve, introduction of important concepts (properties, bounds, definitions) from the field of scheduling. The last section takes a small detour into theoretical computer science in order to make precise that scheduling problems are hard to solve. In the second chapter introduction of genetic and ant colony optomization algorithms and its basius is given. It is used to solve scheduling problem, which was mentioned before. Introduction of all genetic and ant colony optimization algorithm operators and settings are given here. Then follows the introduction to software witch was made to solve and visualize solutions of scheduling problem. A great number of plots and figures are used in the experimental chapter to explain what experiments has been done and what the results are. As usual everything said will be rephrased and put together in the conclusion chapter. Findings for the problem are summarized in this section. Conclusions are made about realization of algorithms and its specifics in solving scheduling problem. Based on the problems and algorithms of this work, these publications were presented: 1. „Study of genetic algorithm for machine scheduling problem“, Mathematics and its lecturing, 2006; 2. „ Scheduling problem“,VI student conference KTU, 2006; 3. “The Analysis of machine scheduling problem algorithm”, XLVII conference of Lithuanian Mathematicians Association, 2006. Also a publication „Comparison of algorithms for the scheduling problem“ was submited to the XLVIII conference of Lithuanian Mathematicians Association. |
