Anton Glivka

INTRODUCTION

1. THEME'S ACTUALITY

2. WORK COMMUNOCATION WITH SCIENTIFIC PROGRAMS, PLANS AND THEMES

3. AIM AND RESEARCH TASKS

4. THE PROBABLE SCIENTIFIC NAVELTY

5. PRACTICAL IMPORTANCE OF WORK

6. WORK APPROBATION

7. REVIEW OF RESEARCH AND DEVELOPMENT

8. THE BASIC CONTENT OF MASTER'S WORK

CONCLUSIONS

LIST OF USED LITERATURE

* Important remark

A modern industrial undertaking is a complicated multilayer system. A manufacturing scheduling module in enterprise planning and management systems is constructed on basis of mathematic models of process. Its accuracy depends on volumetric calendar plans optimum.

The one of the most important industrial enterprise management system research and construct methods is the modeling. The modern factory management system can not be represented without using of models as a quantitative basis of taking a decision in organization, scheduling and management of manufacture.

>> content

The problem of volumetric calendar scheduling is a very important and on the whole influences on the work result of undertaking.

For the enterprises of discrete type of manufacture it is typical an ostentatious scheduling in case of great variety of nomenclature of produced products and technological operations, which greatly complicate the operation calendar scheduling task on that enterprises.

Thus there is a necessity in development of operation calendar work scheduling of discrete manufacture enterprise method, which allows to make an optimization of production time-table according several quality criteria including the existing limitations, to form shift-daily tasks for department subdivision and also assures getting optimal or near optimum solutions.

>> content

Qualification master’s work was carried out during 2008-2009 years according to scientific directions of the chair «Automated control systems» of Donetsk National Technical University.

>> content

Aim of work

An aim of master’s work is a theoretical substantiation and models and methods development to increase the efficiency of machine-building work due to composition of suboptimal time-tables of work on two levels: on the production level and department level, on the chosen optimization criteria basis.

Idea of the work

By means of using of the modern handling methods and intellectual data analysis we need to create computer system, which could react upon the changes in production setting (equipment breakage, material deficit etc.), and then could accordingly change (create) an optimal in that case plan.

We posed the following problems to realize the idea and reach the aim of master’s work:

     - to analyze methodical and theoretical materials in machine-building production mathematic models;

     - to analyze existing artificial intelligence methods, which are used for an operation scheduling, to compare methods and to choose the best one that allows to get an optimal time-table of the manufacturing works;

     - to analyze the data handling systems and chose the tooling to reach the aim of master’s thesis;

     - to analyze criteria and methods of operation production scheduling in case machine-building enterprise;

     - to develop a program for getting suboptimal time-tables follow the learned theoretical information;

     - to approve the program module with real data.

Subject of researches

Subject of researches: the computer system for optimization operation production scheduling in machine-building.

Object of researches

Object of researches: the process of the operation scheduling of products producing in case of joint-stock company "NORD".

Methods of researches

The methodological basis of the researches is formed by systems analysis regulations, scheduling methods of the production program, economical mathematical methods and models, expert methods, management deciding methods. To develop a computer system for optimization operation production scheduling in machine-building we chose the ant algorithm, which gives the best results in comparison with other innovation methods, and genetic algorithm, which takes into account main regularities of production and products selling on the basis of natural selection process.

>> content

The probable scientific novelty consists of program module realization on the basis of artificial intelligence methods, which allow to do efficiently an operation calendar scheduling of work on two levels: on the production level and department level.

>> content

The practical importance of received results consists of an operation production scheduling system development. The elaborated program module lets decrease the material and time resources costs for production process scheduling, increase the information handling quality and handling results quality, except mistakes bond with human factor.

>> content

The work approbation is planning on September, 2009, during the practice in machine-building enterprise joint-stock company "NORD". I am going to make the experimental investigations and choose criteria of the optimization algorithms that will give the best results.

>> content

Simulation models

The main requirements to simulation models are a model adequacy, a maximum algorithm proximity to object programming methodology and universality as a possibility of all the system discrete states set representation. The using of Petry networks in simulation modeling in most cases is limited by a construction of simple cyclic models with visible quantity of system states.[1]

Mathematical modeling

The one of the most important requirements making to operation calendar scheduling (OCS) systems is accuracy of forming work time-tables. The accuracy of any model usually depends on completeness of its representation, accordance to real production system conditions. In most OCS models time-tables traditionally are constructed relatively to the main attendant devices class.[2]

Such a model is optimized by the one of numerical methods and we get the optimal solution on the mentioned time interval. A horizon of scheduling can be an eight-hour shift. A disadvantage of a such type of modeling is that operation scheduling is a quite complicated dynamical system, and its mathematical models is described by quite difficult equation. The composition of this equation is not possible without certain assumptions that affect its accuracy.[3]

Graphs and networks theory

For the heterogeneous elements systems research the apparatus of the mass servicing networks theory (MSNT) is useful. A mass servicing network is an aggregate of the mass servicing systems, where requirements are circulated changing systems. In the basis of MSNT is network describing of technological article handling process. The network mirrors interconnections between autonomous functioned elements and subsystems. The network is a graph consists of the set of nodes and oriented arcs connecting these nodes. In the network department structure representation nodes are autonomous devices or handling positions, arcs show the direction of the requirements (articles) flow in system. Depends on the task and researching function we can change the number of nodes, their composition and connections between them.[4]

Theory of mass service

These models are based on a hypothesis, about probabilistic character of flowing of processes and co-operation of equipment.[5] At the design of work of workshops (by the vehicle of q-charts), assumptions are used:

     - sequence of implementation of operations of technological routes. A technological route is used only for the calculation of probability of frequency and duration of stay of wares distribution on workings positions;

     - the production system is examined as the closed system, I.e. at every instant there is a permanent amount of wares in it;

     - every working position has a store of unlimited capacity.

Object oriented method

Object oriented method is a subclass of simulation models. Produce system is the most powerful and significant representation models of knowledge about discrete process in actual time (AT). Although a lot of difficulties emerge during describing of the complicated monitoring, control and management processes using the great amount of external discrete objects. Nowadays object produce knowledge model (OPKM) is used, which is a decomposition of the produce model of an actual time system “PRODUS” on the basis of object oriented method. In this model there are no such disadvantages as lack of rule base structuring and decomposition means, real parallel mechanism and repeated using of knowledge, and also is offered the new decentralized mechanism of an interpretation evident management and parallel objects synchronization.[6]

Time-table theory

The quality of modern manufacture functioning in many respects is defined by a decision, which is reached on the calendar scheduling and operation management phases. It is extremely relevant when there are constructed a lot of modern automated manufactures – flexible manufacturing systems (FMS). The modern production operation calendar scheduling systems are also constructed on the basis of so-called “time-tables theory” achievements.

Time-tables theory is a science occupying with researches of determinate attendant systems for the purpose of time-tables functioning optimization.[7]

Time-table is some totality of instructions about what exactly requirements are servicing by what exactly apparatus in each time moment.

Optimization methods

Branch-and-bound

Methodological basis of research was made by positions of analysis of the systems, methods of planning of the production program of enterprise, ekonomiko-mathematical methods and models, expert methods, methods of acceptance of administrative decisions. For development of computer subsystem of the operative planning of production in an engineer an ant algorithm which gives the most good results as compared to other innovative methods, and genetic algorithms, adequately taking into account basic conformities to law of production and realization of products, is chosen on the basis of processes of natural selection.[8]

Genetic algorithm

The one of the modern methods based on heuristic algorithm is genetic algorithm (GA).

The generation of the GA is started from reproduction. We choose chromosomes for the next generation rotating roulette wheel so many times that correspond to initial population capacity. The value of ratio Fi(x)/SumF(x) is called the copy (chromosome) choice probability with reproduction operator (RO) and indicate Pi(RO). Here Fi(x) is a value of criterion function (CF) of i-chromosome in population, SumF(x) is a total value of CF of all chromosomes in population. The Pi(RO) value also is called the normalized quantity. The expecting number of copies of i-chromosome after OR define N=Pi(RO)*n, where n is a number of analyzed chromosomes.[9]

In most problems there is special knowledge that helps to construct an approximation model. Using the GA can decrease the volume and time of calculations and simplify function modeling, decrease the number of modeling errors.

Ant algorithm

The main idea of this algorithm is the modeling of ants’ behavior, collective adaptation. A colony is a system with very simple individual’s behavior rules. But despite the primitiveness of the each ant’s behavior, the behavior of whole the colony is very intelligent [5]. Thus the basis of the ants’ behavior is the low-level interaction; because of this the colony in general is an intelligent multi-agent system.[10]

Properties of ant

Each ant has its own "memory", where is saved a list of cities , which ant k should visit, and this ant is in city i.

Ants have "vision" back proportional to rib length: .

Each ant is able to catch the pheromone track that define ant’s wish to pass that rib. The pheromone level in the t time moment on the rib is conformed to .

The probability of ant’s passing from i top to j top is determined by ratio:

(9.1)

where – are empirical coefficients.
This ratio has the effect of "roulette wheel".

The quantity of pheromone:

(9.2)

where – is a parameter, which has the value order of the optimal passage length, – is a length of route.

The evaporation of pheromone is defined by the formula:

(9.3)

where m – is a count of ants, p – is a coefficient of evaporation (p=[0..1]).

Example of work of ant algorithm

Will consider a case, rotined on a picture, when there is an obstacle on an optimum until now way. In this case necessary determination of new optimum way. Reaching to the obstacle, ants with even probability will walk around it on the right. That will take place and on the turn of obstacle. However, those ants which will take the shortest way by chance will be quick prokhoditi him, and for a few movements he will be anymore enriched a pheromon. As motion of ants is determined the concentration of feromona, that the followings will give advantage exactly to this way, continuing to enrich his pheromon until this way on some reason will not become inaccessible.

Figure 7.2 - Conception of ant algorithms
(animation: volume - 102 Kb; size 707х303; amount of repeated cycles – a continuous cycle of reiteration)

>> content

The operation scheduling work consists of:

     - the development of progressive calendar planned standards of manufacture moving;

     - the forming of operation plans and department, sectors, brigades and work places schedules and their reduction to executors;

     - the operation registration and manufacture control, the rejection prevention and revelation and ensuring of manufacture process stabilization.

>> content

During the process of this project development we found the problem solution in methods and models optimization analysis, program instruments and existing software products of operation scheduling in machine-building production.

We analyzed the existing systems and subsystems. In its results we grounded the actuality of operation scheduling system creation.

The results of the master’s work can be used for the operation scheduling optimization in machine-building production.

In this work we also analyzed the existing modeling methods, optimization models and algorithms. And we concluded that the most appropriate method is the combination of the genetic algorithm and ant algorithm on the different optimization levels.

>> content

1. Крушевский А.В. Справочник по экономико-математическим моделям и методам / А.В. Крушевский. – К. : Техника, 1982. – 208 с.

2. Первозванский А.А. Математические модели в управлении производством / А.А. Первозванский. - М.: Наука, 1975. – 616 с.

3. Загидуллин Р.Р. Комплексная математическая модель оперативно-календарного планирования в гибких комплексах механической обработки / P.P. Загидуллин // Автоматизация и современные технологии. - 1999. - № 9. - С. 32-24.

4. Введение в теорию графов [Electronic resource] / Уилсон Р. - Access mode: http://engenegr.ru/2007/05/10/vvedenie_v_teoriju_grafov.html

5. Імітаційне моделювання систем масового обслуговування [Electronic resource] / Ю.В. Жерновий. - Access mode: http://zyurvas.narod.ru/bibTMO.html

6. Объектно-ориентированное моделирование [Electronic resource] / С.С. Гайсарян. - Access mode: http://www.citforum.ru/programming/oop_rsis/glava2.shtml

7. Танаев В.С. Введение в теорию расписаний / В.С. Танаев, В.В. Шкурба. - М. : Наука, 1975.

8. Описание метода ветвей и границ [Electronic resource]. - Access mode: http://math.nsc.ru/AP/benchmarks/UFLP/uflp_bb.html

9. Гладков Л.А. Генетические алгоритмы / Л.А. Гладков, В.М. Курейчик, В.В.Курейчик. – Ростов-на-Дону : Ростиздат, 2004г.

10. Муравьиные алгоритмы [Electronic resource] / А.А. Кажаров, В.М.Курейчик. - Access mode: http://raai.org/cai-08/files/cai-08_paper_144.doc

>> content

During the writing this abstract the master's work wasn’t finished yet. The final ending is planning on December, 2009. The complete text of work and all the information about work you can receive from the author or him scientific adviser after the mentioned date.

>> content