© Strojni{ki vestnik 49(2003)10,499-508           © Journal of Mechanical Engineering 49(2003)10,499-508
ISSN 0039-2480                                                                                                                           ISSN 0039-2480
UDK 658.52.011.56:519.85                                                                      UDC 658.52.011.56:519.85
004.8                                                                                                                       004.8
Izvirni znanstveni ~lanek (1.01)                                                                             Original scientific paper (1.01)
Optimiranje  pretoka  naro~il  v  prilagodljivih obdelovalnih  sistemih  z  genetskimi  algoritmi
Optimisation of the Flow of Orders in a Flexible Manufacturing System
Ivo Pahole - Mirko Ficko - Igor Drstven{ek - Jo`e Bali~
Optimiranje pretoka naročil v prilagodljivih obdelovalnih sistemih je vedno znova zelo pereče. Poleg znanih običajnih metod optimiranja pretoka se uveljavljajo tudi nedeterministične metode. Metode optimiranja pretokov z genetskimi algoritmi spadajo med omenjene metode. V prispevku sta definirani dve prilagoditveni funkciji, ki opišeta problem optimiranja časov in stroškov izvedbe naročila. Z metodo genetskih algoritmov je nato izvedeno iskanje takšnega pretoka, da je vrednost prilagoditveni funkcij čim manjša. © 2003 Strojniški vestnik. Vse pravice pridržane. (Ključne besede: sistemi obdelovalni prilagodljivi, pretok naročil, optimiranje, algoritmi genetski)
In this paper we propose a method of searching for the optimum order flow through a flexible manufacturing system, with respect to transport times, preparation/completion times, manufacturing times and relevant costs. The paper defines two fitness functions describing the problem of the optimisation of times and costs of the execution of order. Then, using the genetic-algorithm method, a flow is found, such that the values of the fitness functions are as small as possible. © 2003 Journal of Mechanical Engineering. All rights reserved. (Keywords: flexible manufacturing systems, order flow, optimization, genetic algorithms)
0 UVOD
Pri optimiranju z znanimi običajnimi metodami je problem optimiranja pretoka naročil v prilagodljivih obdelovalnih sistemih (POS) težko obvladljiva naloga. Tako smo velikokrat prisiljeni optimirati le na eno veličino (čas izdelave, cena itn.). Poleg tega večina metod optimiranja pretoka temelji na hevrističnih metodah oblikovanja rešitve in na ekspertnem znanju izvedencev. Razlog je ta, da se pojavlja veliko različnih veličin, ki vplivajo na optimalno rešitev. Velikokrat smo prisiljeni postaviti omejitve sistema. V prispevku je opisan eden od postopkov iskanja optimalnega pretoka naročila skozi POS glede na čase prenosa, pripravno končnih časov, čase izdelave in pripadajoče stroške. Uporabljene so predpostavke, da pripravno končne čase in izdelavne čase poznamo (dobimo jih iz modulov CAPP - računalniško podprto načrtovanje postopkov). Zaradi svojih lastnosti se pri optimizacijskih problemih, kakršen je ta, izkažejo genetski algoritmi, saj lahko iščejo rešitve problemov, ki so sestavljeni iz zapletenih medsebojno odvisnih delov in bi jih bilo zelo težko modelirati [6].
0 INTRODUCTION
In addition to the well-known, conventional meth-ods for the optimisation of order flow, also the nondeterministic methods have also become widespread. In the case of optimising with the conventional methods, the problem of optimising the orderflow in a flexible manu-facturing system is a hardly controllable task. Thus, we are often restricted to optimising only one variable (the manu-facturing time, the price etc). In addition, most methods for optimising the flow are based on heuristic methods of con-ceiving the solution and making use of the knowledge of experts. This is because there are a lot of different variables influencing the optimum solution, and we are frequently forced to set the limitations of the system. This paper de-scribes one approach to searching for the optimum order flow through a flexible manufacturing system with respect to transport times, preparation/completion times, manufac-turing times and relevant costs. The assumption is made that the preparation/completion times and the manufactur-ing times are known (they are obtained from CAPP - computer aided process planning, modules). Because of their properties, genetic algorithms have proved to be useful in optimisation problems like this one, since they can reach for the solutions of problems that consist of complex, mu-tually dependent parts, and so would be hard to model [6].
gfin^OtJJIMISCSD
03-10
stran 499         |^BSSITIMIGC
Pahole I., Ficko M., Drstven{ek I., Bali~ J.: Optimiranje pretoka - Optimisation of teh Flow
1 OPTIMIRANJE PRETOKA Z GENETSKIMI ALGORITMI
Genetske algoritme je razvil John Holland v 60. in zgodnjih 70. letih [4]. So prilagodni hevristični iskalni algoritmi, ki jih uporabljamo za reševanje zahtevnih iskalnih in optimizacijskih problemov. Ta metoda simulira razvojne postopke oziroma »preživetje najprilagojenejšega« [4].
Najprej ustvarimo začetno generacijo organizmov, ki se nato z reprodukcijo, mutacijo in križanjem iz generacije v generacijo izboljšujejo. Tako dobimo postopoma vedno kakovostnejše pripadnike (organizme), ki so pravzaprav rešitve zastavljenega problema. Glavni koraki metode so:
-     ustvaritev začetne generacije organizmov,
-     ovrednotenje     organizmov     z     uporabo prilagoditvene funkcije,
-     izbira organizmov, ki najbolje rešijo zastavljeni problem, in
-     ustvarjanje nove generacije  s križanjem, reprodukcijo in mutacijo.
1.1 Prilagoditvena funkcija
Pri optimizaciji z genetskimi algoritmi moramo najprej določiti prilagoditveno funkcijo, s katero lahko ocenimo kakovost rešitev. V našem primeru je kakovostnejša tista rešitev, ki ima nižjo vrednost prilagoditvene funkcije. Uporabimo lahko tudi več prilagoditvenih funkcij naenkrat. Izbrali smo dve prilagoditveni funkciji: funkcijo spremenljivih izdelovalnih stroškov in funkcijo porabljenega časa. Glede na trenutne zahteve izbira uporabnik med tema dvema funkcijama. V proizvodnih sistemih namreč prihaja do različnih stanj. Včasih so namreč ključnega pomena stroški, včasih pa porabljen čas.
1.1.1 Iskanje najmanjših stroškov
Stroškovna funkcija je sestavljena iz treh delov. Sestavljajo jo prenosni stroški naročila, pripravljalno končni stroški na posameznih strojih in čisti stroški obdelave. Tako zberemo večino spremenljivih stroškov pri izvajanju naročila:
nn
min Z = XE<VV^
;=1 7=1
pri tem so:
n - število strojev v prilagodljivem obdelovalnem sistemu, dij - razdalja med strojema i in j, x - prisotnost giba med strojema i in j pri naročilu (obstaja, ne obstaja) - vrednost je 0 ali 1, c ij - stroški prenosa med strojem i in j na enoto dolžine, tpzi - pripravljalno zaključni čas na stroju i, yi - uporaba stroja i pri naročilu -
0 snna(a)eJl[FiJDŽ[rSD |
^UliSfinMlliC |        stran   500
1 OPTIMISING THE FLOW BY USING GENETIC ALGORITHMS
Genetic algorithms were developed by John Holland in the 1960s and early 1970s [4]. They are adaptive, heuristic searching algorithms used for solving demanding search and optimisation problems. The genetic-allgorithm method simulates evolutionary processes, or the “survival of the fittest” [4].
First, we create the initial generation of organisms, which then improve by reproduction, mutation and crossover from generation to generation. Thus, we gradually obtain members (organisms) of ever higher quality which, in fact, are the solutions to the set problem. The principal steps of the method are:
-     creation of the initial generation of organisms,
-     evaluation of the organisms by means of the fitness function,
-     selection of the organisms that best solve the set problem,
-     creation of a new generation by crossover, mutation and reproduction.
1.1 Fitness functions
In the case of optimisation by using genetic algorithms, it is necessary to first determine the fitness function, enabling the calculation of the quality of the solutions. In our case, the solution, which has a lower value of the fitness function, is of higher quality. It is also possible to use several fitness functions at one time. We selected two fitness functions: the function of the variable manufacturing costs and the function of the time spent. Taking the current requirements into account, the user selects between these two functions, because in production systems, different situations occur. Sometimes the costs are of key importance and sometimes it is the spent time.
1.1.1 Searching for the minimum costs
The cost function consists of three parts: the transport costs for the order, the preparation/completion costs on the individual machines and the net cost of the machining. In this way, the majority of the variable costs for the execution of the order are covered. The cost function is:
n                                       n      k
;=1                                    ;=1 y=1
where:
n - number of machines in the flexible manufacturing system, dj - distance between the machine tools i and j x -indicates the presence of a connection between machines i and j for the order (exists, does not exist) - the value is 0 or 1, c - transport cost between the machines i and j per unit length, tpzi - preparation/completion time on machine tool i, yi - utilization of machine tool i for the order - the value
Pahole I., Ficko M., Drstven{ek I., Bali~ J.: Optimiranje pretoka - Optimisation of teh Flow
vrednost je 0 ali 1, k - število opravil naročila, t - tehnološki čas obdelave za stroj i in opravilo j, c  - cena strojne ure za stroj i.
dij dobimo iz matrike razdalj med posameznimi stroji. Ta matrika je nespremenljiva. x pove ali gib med strojema i in j obstaja ali ne. Dobimo ga iz genotipa organizma. cij dobimo iz matrike stroškov za povezave med strojema i in j. tpzi dobimo iz CAPP modula glede na uporabljeni stroj i in naročilo. yi dobimo iz genotipa organizma. ttij dobimo iz številsko krmiljenega (ŠK - NC) programa in je odvisen od uporabljenega stroja i in operacije j.
is 0 or 1, k – number of operations for the order, ttij – techno-logical time of machining for machine tool i and operation j, csi – price of a machine tool hour for machine tool i.
dij is obtained from the matrix of distances be-tween the individual machine tools. This matrix is con-stant. xij tells whether a connection between the machine tools i and j exists or not. It is obtained from the genotype of the organism. ctij is obtained from the matrix of costs for interconnections between machine tool i and j. tpzi is ob-tained from the CAPP module with respect to the used machine tool i and the order. yi is obtained from the geno-type of the organism. ttij is obtained from the NC program and depends on the used machine tool i and the operation j.
1.1.2 Iskanje najmanjših časov
1.1.2 Searching for the minimum times
Tudi časovna funkcija je sestavljena iz treh delov in izhaja iz stroškovne funkcije.
The time function also consists of three parts and isbased on the cost functions.
n      n                          1            »                              »      *
i=1 ]=1
vij je hitrost prenosa med strojema i in j, vij dobimo iz matrike hitrosti posameznih prenosnih naprav.
1.2 Kodiranje
i=1 ]=1
(2),
vij is the speed of the transport between machines i and j, vij is obtained from the matrix of speeds of the individual transport devices.
1.2 Coding
Na podlagi razčlenitve delovnega poteka na posamezna opravila in določitve strojev, na katerih se bodo posamezna opravila izvajala, določimo zaporedje pretoka (primer zaporedja pretoka prikazuje slika 1).
vpenjalno
mesto 1
fixing point 1

]D

D
The sequence of the flow is determined in accordance with the breakdown of the work progress into the individual operations and on the basis of a determination of the machine tools on which the individual operations will be performed (Fig. 1). izdelovalni
stroj 3
machine
tool 3
?

izdelovalni
stroj 2
machine
tool 2


C
:


?
]D

pralna postaja
washing station

izdelovalni
stroj 1
machine
tool 1

?

?

?
vpenjalno    i mesto 2 fixing point 2


?
D
?


izdelovalni stroj 4
machine tool 4
Sl. 1. Primer zaporedja pretoka za izpolnitev naročila Fig. 1. Example of the sequence of flow for the execution of order
4
3
1
5
2
6
Pahole I., Ficko M., Drstven{ek I., Bali~ J.: Optimiranje pretoka - Optimisation of teh Flow
Organizem mora nositi informacije o tem, katera opravila se morajo izvesti, da bo naročilo izpolnjeno in na katerih strojih se morajo omenjena opravila izvesti. Organizem je tako dvorazsežna matrika, ena razsežnost matrike je enaka 2 in druga razsežnost matrike je enaka številu opravil naročila. En gen obsega eno opravilo in stroj, na katerem se opravilo izvaja. Za določanje izvedljivosti množice opravil na določenem stroju je uporabljena metoda standardnih opravil po standardu DIN.
1.2.1 Način iskanja obdelovalnega stroja pri znanem tehnološkem postopku
Pri načrtovanju tehnologije določimo tehnološki postopek. Določimo delovna opravila, ki jih zahteva oblika in geometrijska oblika izdelka. Opravila se v glavnem opisujejo z opisnim načinom (čelno poravnati, frezati do globine itn.). Tak način opisovanja pa otežuje obdelavo s poznanimi programskimi orodji na računalnikih. V znanih standardih lahko zasledimo, da je področje opisovanja delovnih opravil zelo natančno obdelano (pregl. 1).
Takšen način označevanja delovnih opravil omogoči bistveno lažje opisovanje opravil. Tehnolog mora torej uporabiti standardni zapis. V veliko olajšanje so mu lahko grafični pripomočki na računalniku. Tako lahko kot rezultat iz modula CAPP, dobimo naslednje podatke:
-     oznaka (zaporedna številka naročila) naročila za določeno obdobje načrtovanja,
-     enolična oznaka naročila,
-     šifra ali ime obdelovanca ali obdelovancev v naročilu,
The organisms must carry the information about which operations have to be performed for the order to be fulfilled and on which machine tools these operations must be carried out. Thus, the organism is a two-dimensional matrix: one dimension of the matrix is equal to 2 and the other dimension of the matrix is equal to the number of operations for the order. One gene com-prises one operation and the machine tool on which the operation is performed. The method of standard opera-tions according to the DIN standard is used for verifying the feasibility of the group of operations on a machine.
1.2.1 How to search for a machine tool in the case of a known technological process
During the planning of technology the tech-nological process is determined, as are the work op-erations required by the shape and geometry of the product. The operations are mainly defined by a de-scribing (to be face milled, to be milled up to a depth, etc.). Such a description, however, makes it difficult to process using known programme tools on computers. From the known standards it is possible to conclude that the area of describing the work opera-tions has been studied very precisely (Table 1).
Designating the work operations in this way makes describing the operations considerably easier. Thus, the technologist must use the standard designations. However, graphic devices on a computer can be of great assistance to the technologist. We can obtain the following data from the CAPP module:
-    designation (serial number) of the order for a cer-tain period of planning,
-    unambiguous designation of order,
-    code or description of workpiece(s) in order,
-    number of workpiece(s),
Preglednica 1. Primer pregleda izvedljivih delovnih opravil za obdelovalni stroj Table 1. Example of a survey of feasible work operations for a machine tool
Pregled možnosti izvedljivih delovnih opravil za večopravilni obdelovalni stroj za vrtanje in frezanje (primer) Survey of possibilities for the   execution of standard operations on a multiple-operation drilling and milling machine (example)		
Zap. St. Ser.No.	Šifra opravila po DIN 8589 Code of operation according to DIN 8589	Opis opravila za lažje razumevanje Description of operation for easier understanding
1	3.2.2.1.	skupina opravil čelnega grezenja group of operations for face sinking
2.	3.2.2.2.	skupina opravil vrtanja group of drilling operations
3.	3.2.2.3.	skupina opravil izdelave navojev v izvrtinah group of thread-cutting operations (is drilled holer)
4.	.....	......
4.	.....	......
7.	3.2.3.1.	plano frezanje plans milling
8.	3.2.3.2.	frezanje okroglih oblik milling of round shapes
0 BnnBjfokJ][p)l]Olf|ifrSO | | ^SsFÜWEIK |          stran   502
Pahole I., Ficko M., Drstven{ek I., Bali~ J.: Optimiranje pretoka - Optimisation of teh Flow
-     število obdelovancev,
-     potrebni programi ŠK za določena opravila na določenih enotah,
-     opis standardnih opravil po standardu DIN,
-     predvideni časovni termin začetka,
-     predvideni vnaprej določeni normativni čas za naročilo.
1.2.2  Določitev spektra   izvedljivih opravil na obdelovalnem stroju
Za znani obdelovalni stroj lahko določimo standardna opravila, ki jih je mogoče izvesti na obdelovalnem stroju. Pod standardna opravila so mišljena opravila iz standarda DIN [3] (sl. 2). Preglednica 1 prikazuje vidno obliko datoteke za opis izvedljivih standardnih delovnih opravil na določenem obdelovalnem stroju.
V primeru, ko pa že imamo naročilo uvedeno v proizvodnjo, je velikokrat treba iskati alternativni obdelovalni stroj za določeno opravilo oziroma skupino opravil. Aktualni primeri so:
-     če pride do zastoja, okvare na načrtovanem obdelovalnem stroju,
-     če imamo, iz določenih drugih razlogov, proste delovne zmogljivosti na podobnih obdelovalnih strojih in želimo zmanjšati ali celo odpraviti ozko grlo;
-     če se iz kakršnih koli razlogov spremeni prednost naročil (nujna naročila);
-     če ni na voljo ustreznih delovnih pripomočkov ali orodij, ki so namensko vezana na določen obdelovalni stroj.
1.2.3 Izvršitev in rešitve
Želja uporabnika je gotovo avtomatizirano iskanje alternativnega obdelovalnega stroja pri izvajanju vodenja proizvodnje. Kaj hitro lahko pridemo do sklepa, popolna avtomatizacija ni
required NC-programmes for certain operations
on certain units,
description of standard operations according to
the DIN standard,
anticipated start time,
anticipated calculated time for order, defined in
advance.
1.2.2 Determination of the spectrum of feasible op-erations on a machine tool
For a known machine tool it is possible to determine the standard operations that can be ef-fected on the machine tool. The standard operations are meant to be operations defined in the DIN standard [3], (Fig. 2). Table 1 shows the visible shape of the data file for describing the feasible, standard work operations on a machine tool.
When an order has already been introduced into production, it is often necessary to search for an alternative machine tool for a certain operation or group of operations. Typical examples are:
-    if stoppage, defect occurs on the planned machine tool,
-    if for some other reasons there are free working capacities on similar machine tools, and a reduc-tion or even the removal of a bottle-neck are de-sired,
-    if for any reasons the priority of orders (urgent order) is changed,
-    if proper working devices or tools, specifically connected with a certain machine tool, are not available.
1.2.3 Realisation and solutions
Automated searching for an alternative machine tool during the performance of production management is certainly the user’s wish. We can come quickly to the conclusion that complete automation is
Sl. 2. Primer standardnega opravila frezanja DIN 8589, opravilo št. 3.2.3.5.1. Fig. 2. Example of standard milling operation DIN 8589, operation No. 3.2.3.5.1.
stran   503
-
-
Pahole I., Ficko M., Drstven{ek I., Bali~ J.: Optimiranje pretoka - Optimisation of teh Flow
mogoča, saj skoraj ni mogoče obdelovanca enolično opisati z ustrezno metodo ([5], [7] in [8]).
Pri iskanju rešitev prikazanega problema naletimo na več dejavnikov, od katerih je odvisna končna rešitev, če ta sploh obstaja. V sami fazi načrtovanja je mogoče izdelati več alternativnih delovnih postopkov, ki jih optimiramo glede na:
-     časovno najugodnejšo ali
-     ekonomsko najugodnejšo različico.
Če se poveča število teh različic delovnih postopkov postane običajno tak način načrtovanja ekonomsko vprašljiv. Lahko pa se tudi zgodi, da takega načina časovno ne zmoremo. Število mogočih različic se namreč zelo hitro povečuje [1].
Hkrati moramo pripraviti pogoje za izvajanje določenega naročila na več enotah prilagodljivega obdelovalnega sistema [8]. Še posebej velja to za tista naročila, ki imajo veliko prednost.
Za določanje oziroma izbiro alternativnega obdelovalnega stroja je lahko tehnologu operaterju velik pripomoček programska oprema »ALTER«. Izdelana programska oprema omogoča poiskati ustrezen obdelovalni stroj. Programski modul deluje tako, da primerja opravila, potrebna za izvedbo naročila, s spektrom opravil, ki jih zmorejo obdelovalni stroji. V primeru ugodne rešitve je na koncu še predviden poseg človeka, izvedenca, ki da dokončno rešitev. Slika 3 prikazuje diagram poteka programskega modula.
1.2.4 Izvedljivost naročil glede na orodja in delovne pripomočke
Izhodni podatki iz take izbire so:
-     izbrano naročilo,
-     obdelovalni stroj, na katerem je izbrano naročilo izvedljivo,
-     delovni   pripomočki,   ki   morajo   biti   na obdelovalnem stroju za izbrano naročilo,
-     orodja, ki morajo biti na obdelovalnem stroju za izbrano naročilo,
-     časovni čas začetka opremljanja stroja [9].
1.3 Nastanek začetne generacije
Organizem bi lahko bil sestavljen samo iz zaporedja strojev, tako da bi bil posamezni stroj zapisan tolikokrat, kolikor bi bilo na njem izvedenih opravil. Vendar pa je izvedljivost opravila neposredno vezana na stroj. Kodiran organizem:
not possible, since it is almost impossible to describe a workpiece by a suitable method ([5], [7] and [8]).
When searching for solutions to the problem presented across several factors by which the final solution – if it exist at all – is conditioned. During the planning stage it is possible to work out several alternative working procedures, which we optimise with regard to:
-    the most favourable version with respect to time,
-    the most economically favourable version.
If the number of these versions of working processes increases, such a way of planning usually becomes economically questionable. It can also happen that such a method cannot be applied because it is time-consuming [1].
In parallel, it is necessary to prepare the conditions for the execution of a certain order on several units of the flexible manufacturing system [8]. This applies particularly for orders of high prior-ity.
The programme equipment can be of great assistance to the technologist/operator for the determination and/or selection of the alternative machine tool. The “ALTER” programme ensures that a suit-able machine tool can be found. The programme module functions so that it compares the operations required for the execution of the order with the spectrum of operations that the machine tools can perform. Figure 3 shows a diagram of the flow of the programme module.
1.2.4 Feasibility of orders with respect to tools and working devices
Output data from such a selection are:
-    order selected,
-    machine tool on which the selected order is fea-sible,
-    working devices that must be provided on the machine tool for the selected order,
-    tools that must be available on the machine tool for the selected order,
-    start time of the equipped machine [9].
1.3 Creation of the initial generation
The organism may only consist of the se-quence of machines, such that the individual machine would be mentioned so many times as the number of operations directly connected to the machine. Coded organism:
o1 o2 o3 o4 o5 o6 o7 o8 o9H
L s1        s3        s8       s8       s2       s4       s4       s4        s1 J
Ugotovimo, da je število pravilnih genov omejeno. Vsako opravilo lahko opravi le omejeno število strojev. To pomeni, da je število genov
Each operation can be performed only by a limited number of machines, which means that the number of genes is limited. Therefore, first, all pos-
0 S3"in3(šul[M]!
ms
stran 504
Pahole I., Ficko M., Drstven{ek I., Bali~ J.: Optimiranje pretoka - Optimisation of teh Flow
[ START ] \
Primerjava / Comparision
Mere obdelovanca < Obdelovalnega volumna stroja
Workpieces dimensions < Dimensions of machining volume of machine
NE / NOy\ -----------\IF/
|   DA / YES
Primerjava / Comparision
Operacija iz CAPP = DIN Operaciji stroja
Operation from CAPP = DIN Operation of machine
NE / NO
IF
Nadomestni stroj ne obstaja
Replacement machine tool
does no exists
DA / YES
Nadomestni stroj obstaja
Replacement machine
tool exists
ALTER. DAT
j
Ocena izvedenca Checking expert
Nadomestni stroj ne obstaja
Replacement machine tool
does no exists
NE / NO
<—
O IF
DA / YES
Nadomestni stroj obstaja Replacement machine tool exists
[ stop")
Sl. 3. Diagram poteka programskega modula »ALTER« za določanje nadomestnega obdelovalnega stroja Fig. 3. Diagram of flow of programme module for the determination of the replacement machine tool
omejeno. Zato najprej ustvarimo vse možne gene in tako ustvarimo množico genov (sl. 4).
Iz te množice nato izbiramo posamezne gene in jih zlepimo skupaj v pravilne organizme (sl. 5). Pravilni organizmi so tisti, ki predstavljajo takšno zaporedje pretoka, da dobimo za rezultat izpolnjeno naročilo. Množico genov uporabimo tudi pri opravilu mutacije.
sible genes are generated and thus a group of genes is created (Fig. 4).
Out of the group, we then select the indi-vidual genes and assemble them together in correct organisms (Fig. 5). The appropriate organisms are those that represent such a sequence of the flow which results in the fulfilled order. The group of genes is also used in the operation of mutation.
Pahole I., Ficko M., Drstven{ek I., Bali~ J.: Optimiranje pretoka - Optimisation of teh Flow
..••'""     (m)       "'•••..
množica strojev ''•• s~\ group of machine (m 2) V-T     /TN tools
./'     o 2     o 1 \
m 1
m          m
preverjanje izvedljivosti opravila na strojih
verification of feasability of operations on machines
gen = opravilo + stroj gene = operation + machine
o 1)
množica opravil group of operations
o
o      (o)       o•¦•'
o 6
množica genov group of genes
o1
m 2 to1
/^-n lm1J   ^^
o2  I ^N Io3  I m2 (o2 | l m 1
lm3)fo6] V   ma
mJ
Sl. 4. Prikaz nastanka genov Fig. 4. Representation of the coding of solutions
množica genov group of genes
organizem organism
Sl. 5. Oblikovanje organizma iz množice genov Fig. 5. Forming the organism from a group of genes
1.4 Razvojna in genetska opravila
Zaradi samega načina kodiranja in ustvarjanja začetne generacije lahko uporabimo najpreprostejše enotočkovno ali večtočkovno križanje (sl. 6).
organizem 1 organism 1
1.4 Evolutionary and genetic operations
Due to the method of coding and the generation of the initial operation, we can use the simplest single-point or multiple-point crossover (Fig. 6).
potomec 1 offspring 1
1 Y o 2 Y o 31   4 y 05 y C6 yo7 Y Og Y Og m 1 1 m 3k m 3A m 4K m4A    8 m5V m5A m7j
organizem 2 organism 2

potomec2 offspring2
točka križanja crossover point"
i
Sl. 6. Križanje organizmov Fig. 6. Crossover of organisms
03-10
grüT^dfcflMieKn
| ^BSfiTTMlliC |          stran 506
o
i
Pahole I., Ficko M., Drstven{ek I., Bali~ J.: Optimiranje pretoka - Optimisation of teh Flow
organizem organism
o 1 Y o2 Y o 3 Y o4Yo 5Yo6\ o7 Y o 8 Yo9 m11 m21 m51 m51 m61 m31 m31 m 7 I m7

mutiran organizem mutated organism
o 1 Y o2 y'o 3Yo 4 o 5Yo 6Yo 7^Y o 8 Y o9
m11 m21 m51 m51 m6
m,
m61 m71
m-
7)
točka mutacije mutation point
i
Sl. 7. Mutiranje organizmov Fig. 7. Mutation of organisms
Prav tako kakor križanje je tudi mutacija pri tej vrsti kodiranja zelo preprosta (slika 7). Edini pogoj, ki se mora pri mutaciji upoštevati, je, da se zamenjani geni v organizmu nadomestijo s takšnim genom, ki vsebuje enako opravilo. Nadomestni gen izberemo iz množice genov.
1.5 Ovrednotenje
Vsak organizem ovrednotimo z dvema stroškovnima funkcijama. Pri tem ima večji pomen tista stroškovna funkcija, ki je v danem trenutku za uporabnika pomembnejša. Zaporedje pretoka lahko namreč optimiramo glede na najkrajši potreben čas za izpolnitev naročila ali glede na najmanjše stroške. V primeru, da dobimo več enako dobrih rešitev glede na prvo stroškovno funkcijo, poiščemo med temi rešitvami tisto rešitev, ki najbolje reši drugo stroškovno funkcijo.
Glede na organizem se ustvarita matriki [X] in [Y], ki vsebujeta vrednosti xij in yi in matrike tehnoloških časov [tt ] in pripravljalno končnih časov [t ], ki jih izdelajo moduli CAPP Na podlagi teh matrik, ki so odvisne od samega organizma in preostalih matrik, ki so nespremenjene za postavljeno izdelavo, se izvede računanje vrednosti stroškovnih funkcij.
2 SKLEP
V nasprotju z drugimi metodami optimizacije pretoka v prilagodljivih obdelovalnih sistemih imajo genetski algoritmi nekaj neizpodbitnih prednosti. V nasprotju z večino drugih metod z genetskimi algoritmi izdelujemo rešitve po načelu naključnosti z genetskimi in evolucijskimi operacijami in ne uporabljamo nobenih pravil oblikovanja rešitve. Edina omejitev je ta, da mora biti izdelana rešitev mogoča. Kakovost izdelanih rešitev ovrednotimo s prilagoditvenima funkcijama. Pri reševanju s to metodo sicer ni nujno, da bomo dobili najboljšo rešitev, vendar bo prav gotovo med boljšimi. Prednost te metode je tudi v tem, da lahko dobimo po več zagonih genetskega algoritma več različnih rešitev, ki imajo podobno vrednost stroškovnih funkcij.
Like the crossover, the mutation is also very simple, in terms of the type of coding (Fig. 7). The sole condition to be considered in the mutation is that the genes in the organism are to be replaced by the genes containing the identical operation. The replacement gene is selected from the group of genes.
1.5 Evaluation
Each organism is evaluated by two cost func-tions. The cost function that is more important for the user at a given moment is of greater weight. The se-quence of flow can be optimised with respect to the minimum time required for the fulfilment of the order, or with respect to the minimum cost. In the event that sev-eral solutions are equally good with respect to the first cost function obtained, from these solutions we pick the solution which best solves the other cost function.
With respect to the organism, the matrices [X] and [Y] containing the values xij and yi are generated. The matrices of the technological times [tt] and the preparation/completion times [tpz], made by CAPP modules, are also generated with respect to the organism. On the basis of those matrices, de-pending on the organism itself and on other matri-ces, which are constant for the existing manufactur-ing, the values of the cost functions are calculated.
2 CONCLUSION
In contrast to other methods for optimising the flow in a flexible manufacturing system, genetic algorithms have a number of advantages. Unlike most other methods, with genetic algorithms we obtain solutions according to the random principle, by ge-netic and evolutionary operations, and we do not use any rules when conceiving the solution. The sole limitation is that the solution must be feasible. The quality of the solutions is evaluated by the two fitness functions. When solving with this method, it is not certain that the optimum solution will be ob-tained, but it will certainly be a better one. Another advantage of this method is that after several runs of the genetic algorithm we can obtain several differ-ent solutions with similar values for the cost func-tions.
stran 507
Pahole I., Ficko M., Drstven{ek I., Bali~ J.: Optimiranje pretoka - Optimisation of teh Flow
3 LITERATURA 3 REFERENCES
[1] Balič, J., Z. Živec, F. Čuš (1995) Model of a universal manufacturing interface in CIM for small-and medium sized companies. Journal Material Processing Technology, 52, 103-114.
[2] Burns, R. (1997) Intelligent manufacturing. Aircraft Engineering and Aerospace technology, 69, 440-446.
[3] Deutsche Normen (1981) DIN 8589 - Fertigungsverfahren Spanen, Beuth Verlag, Berlin.
[4] Holland, J. (1975) Adaptation in natural and artificial systems. University of Michigan Press, Ann Arbor.
[5] Katalinic, B. (1990) Industrieroboter und flexible Fertigungssysteme für Drehteile. VDI Verlag, Düsseldorf.
[6] Mitchell, T M. (1997) Machine learning. The McGraw-Hill Companies, Inc, New York.
[7] Pahole, I. (1996) Using data flow matrix for small and medium-sized enterprises. Proceedings of DAAAM - 95, Vienna.
[8] Pahole, I. (1997) Planiranje vodenje in optimiranje inteligentnih fleksibilnih obdelovalnih sistemov z uporabo koncepta pretočne matrike. Ph.D. thesis, Faculty for mechanical engineering, Maribor.
[9] Pahole I., and J. Balič (1998) Optimization of intelligent FMS using data flow matrix method. Proceedings of the 7th International Scientific Conference Achievements in Mechanical & Materials Engineering AMME’98, Gliwice-Zakopane.
Naslov a	vtorjev: doc.dr. Ivo Pahole		Authors’ Address: Doc.Dr. Ivo Pahole	
	mag. Mirko Ficko dr. Igor Drstvenšek profdr. Jože Balič Univerza v Mariboru Fakulteta za strojništvo Smetanova 17 2000 Maribor ivo.pahole@uni-mb.si mirko.ficko@uni-mb.si drsti@uni-mb.si joze.balic@uni-mb.si			Mag. Mirko Ficko Dr. Igor Drstvenšek Prof.Dr. Jože Balič University of Maribor Faculty of Mechanical Eng. Smetanova 17 2000 Maribor, Slovenia ivo.pahole@uni-mb.si mirko.ficko@uni-mb.si drsti@uni-mb.si joze.balic@uni-mb.si
Prejeto:		Sprejeto:		Odprto za diskusijo: 1 leto
Received:	28.4.2003	Accepted:	18.12.2003	Open for discussion: 1 year
0 S3"in3(šul[M]!
ma
stran 508