Strojniški vestnik - Journal of Mechanical Engineering 51(2005)1, 28-40 UDK - UDC 658.286.2:519.85 007.5 Izvirni znanstveni članek - Original scientific paper (1.01) Oblikovanje prilagodljivega obdelovalnega sistema z genetskimi algoritmi A Model for Forming a Flexible Manufacturing System Using Genetic Algorithms Mirko Ficko - Miran Brezočnik - Jože Balič Znano je, da je mogoče z dobro razmestitvijo naprav v prilagodljivem obdelovalnem sistemu zmanjšati spremenljive prenosne stroške in s tem skupne izdelovalne stroške in si tako zagotoviti konkurenčno prednost. Do sedaj so bile vpeljane različne metode razporejanja, vendar problem se ni zadovoljivo resen. V prispevku je opisana metoda za razporejanje strojev in naprav v prilagodljivem obdelovalnem sistemu z metodo genetskih algoritmov. Predpostavljena je črtna razporeditev enot prilagodljivega obdelovalnega sistema. S predlagano metodo je mogoče poiskati optimalno razporeditev glede na postavljeno ciljno funkcijo, ki zajema spremenljive stroške prenosa. © 2005 Strojniški vestnik. Vse pravice pridržane. (Ključne besede: sistemi obdelovalni prilagodljivi, algoritmi genetski, prenos notranji, razporeditve strojev) It is well-known that with a proper layout of devices in a flexible manufacturing system it is possible to reduce the variable transport costs and, consequently, the total manufacturing costs, and thus secure a competitive advantage. So far, a variety of methods of layout have been introduced, but the problem has not been satisfactorily solved. This paper describes a method of placing machines and devices in a FMS using a genetic algorithm method. The line layout of the units of the FMS system is assumed. With the proposed method it is possible to ensure optimum layout with respect to the set target function including variable transport costs. © 2005 Journal of Mechanical Engineering. All rights reserved. (Keywords: flexible manufacturing systems, genetic algorithms transport, placement methods placing machines) 0 UVOD Do danes so bili narejeni veliki koraki pri razvoju proizvodne tehnologije. V svetu so bili izvedeni mnogi prilagodljivi obdelovalni sistemi (POS). Le-ti so odgovor na zahteve trga po mnogih različicah izdelka in njegovi vedno krajši dobi trajanja. Prilagodljiv obdelovalni sistem je sestavljen iz podsistemov, ki so načrtovani in izvedeni tako, da delujejo kot celota [2]. Vse komponente prilagodljivega obdelovalnega sistema so med seboj povezane in delujejo s ciljno strategijo, da izdelajo izdelke v primernem času in ob primerni učinkovitosti [2]. POS-i imajo na račun visoke avtomatizacije sicer visoke stopnje izkoriščenosti, vendar moramo z njimi izdelati izdelke tudi ceneje kakor z nepovezanimi posameznimi stroji [8]. 0 INTRODUCTION Great steps forward have been made in the development of production technology. Many flexible manufacturing systems (FMSs) have been de-signed and made all around the world. These systems are an answer to the market requirements for many versions of a product and its ever-shorter service life. A FMS consists of subsystems designed and made in such a way that they operate as a single unit. [2]. All the components of the FMS are inter-connected and operate with the target strategy of producing products within a suitable time and with the proper efficiency [2]. Due to high levels of automation the FMSs are very occupied, and they are also expected to make products cheaper than non-connected individual machines [8]. 28 Strojniški vestnik - Journal of Mechanical Engineering 51(2005)1, 28-40 Eden izmed ključnih dejavnikov uspeha pri POS-ih je prenos med posameznimi deli sistema. Tako je razporejanje naprav, strojev in delovnih mest v zadnjih dveh desetletjih predmet živahnega proučevanja [4]. S smotrnim razmeščanjem delovnih naprav (strojev, tehnološke opreme) znotraj nekih meja (npr. tovarniške hale), poskušamo čim bolj zmanjšati stroške ravnanja z materialom, delovnimi sredstvi in s pomožnimi sredstvi [11]. Največkrat za ciljno funkcijo izberemo najmanjše skupne stroške ravnanja s predmeti dela. Ti stroški so v splošnem vsota stroškov prenosa (ti so sorazmerni z intenzivnostjo pretoka in z razdaljami) in preostalih stroškov. Za POS, ki ga načrtujemo na novo, moramo na najboljši mogoči način razmestiti naprave. Kot kolikostni kriterij razmeščanja naprav se uporabljajo skupni spremenljivi prenosni stroški med delovnimi napravami, v določenem časovnem obdobju prenesenih količin surovin, obdelovancev in polizdelkov. Tako je optimalna razporeditev naprav in strojev v obdelovalnem sistemu ena izmed temeljnih zahtev pri načrtovanju POS-a, saj so dobre rešitve pri načrtovanju takšnega sistema temelj za njegovo učinkovito delovanje in nizke stroške obratovanja. Ocenjeno je bilo, da do 50 odstotkov izdelovalnih stroškov izhaja iz ravnanja s predmeti dela, z dobro razmestitvijo naprav je mogoče omenjene stroške zmanjšati za 10 do 30 odstotkov [10]. Zato je že v zgodnji fazi načrtovanja sistema treba poznati razmestitev naprav. V tem prispevku predlagamo razporejanje naprav in strojev v POS-u z genetskimi algoritmi. V razdelku 1 je podano trenutno stanje raziskav na tem področju. V razdelku 2 je predstavljena glavna zamisel predlaganega postopka. Prikazuje tudi kodiranje organizma, funkcijo prilagojenosti in ovrednotenje organizmov. V razdelku 3 je podan primer razporejanja naprav v POS-u. V sklepu sledijo razprava in smernice za nadaljnje delo. 1 PREGLED STANJA RAZISKAV Večina običajnih postopkov pri razporejanju predmetov po površini temelji na predpostavki, da so lege določene vnaprej. Pri razporejanju se držijo vnaprej natančno določenega postopka. Heragu in Kusiak sta opozorila na dejstvo, da se POS-i razlikujejo od običajnih proizvodnih sistemov [5]. POS-i vključujejo stroje in naprave, ki po navadi niso One of the key factors in the successful operation of a FMS is the transport between the indi-vidual parts of the system; the layout of devices, machines and workplaces was extensively studied during the past two decades [4]. The proper placing of working devices (machines, technological equip-ment) within certain limits (e. g., a workshop) is ex-pected to reduce the costs of handling materials, work-ing means and auxiliary means [11]. In most cases the minimum cost of handling work pieces is selected as the target function. In general these costs are the sum of the transport costs (which are proportional to the flow intensity and distances) and other costs. For a newly designed FMS the devices must be placed in the best possible manner. The total variable transport costs of raw materials, workpieces and semi-finished products transported between the working devices within a certain time period are used as the quantitative criterion of placing of devices. The optimum layout of devices and machines in the manufacturing system is one of the basic requirements for the design of the FMS, since good solutions in designing such system are a pre-requisite for its efficient functioning and low cost of operation. It has been estimated that 20% to 50% of manufacturing costs are due to the handling of work pieces; the proper placing of devices can reduce these costs by 10% to 30% [10]. This means that the placing of devices must be known at an early stage of designing the system. This paper proposes that the machines and devices in the FMS are placed on the basis of ge-netic algorithms (GAs). Section 1 discusses the present state of research in this area. Section 2 presents the basic concept of the proposed ap-proach; it also presents the coding of the organ-isms, the fitness function and the evaluation of or-ganisms. Section 3 gives an example of placing the devices in a FMS. In the Conclusion are the discus-sion and the guidelines for further work. 1 A SURVEY OF THE STATE OF CURRENT RESEARCH Most conventional approaches to the plac-ing of objects on surface are based on the assumption that the positions are determined in advance. During placing they adhere to an exactly determined procedure. Heragu and Kusiak pointed out that FMSs differ from conventional production systems [5]. FMSs in-clude devices and machines that do not usually have Oblikovanje prilagodljivega obdelovalnega sistema - A Model for Forming a Flexible Manufacturing System 29 Strojniški vestnik - Journal of Mechanical Engineering 51(2005)1, 28-40 enakih mer, prav tako niso trdno določene razdalje med posameznimi napravami [5]. Tako ni mogoče vnaprej določiti položaje in nato po njih razporejati naprave. Zaradi teh dejstev je v POS-u praktično nemogoče razporejati delovne naprave in delovna mesta z metodami, ki delujejo po načelu eno mesto ena naprava. Zaradi tega so razvili številne hevristične postopke, ki pa ravno tako uporabljajo različne predpostavke in poenostavitve, zaradi česar je rešitev zgolj približna. Vse metode imajo za cilj najmanjše prenosne stroške, razlikujejo pa se po zahtevnosti, predvsem po dolžini postopka. Ni pa mogoče z gotovostjo reči, katera od poglavitnih metod oziroma metod za izboljšanje postavitve je najboljša [9]. Vendar je področje raziskovanja še vedno zanimivo za mnoge raziskovalce, saj se dandanes rešujejo problemi z novimi, sodobnejšimi metodami in z možnostjo uporabe mnogo večje računske moči sodobnih računalnikov. Danes to področje raziskav obsega različne metode in cilje. Glede na cilje, ki jih želimo z razporejanjem naprav doseči, se razlikuje tudi primernost metod razporejanja. Vsem metodam je skupno, da vzamejo prostor za nespremenljiv, spreminjati je mogoče le razdelitev prostora. Prostor lahko predstavimo glede na značilnosti predmetov, ki jih razporejamo [7]: - Prostor, razdeljen na ločene dele (v tem primeru poteka razporejanje po načelu: en predmet na eno mesto); - Prostor, predstavljen kot prosta površina (v tem primeru imamo prirejanje več predmetov na skupno površino); - Prostor, predstavljen kot površina in oblika. Računalniško podprto razporejanje naprav terja ovrednotenje razporeditve. Obstajajo trije glavni načini ovrednotenja razporeditve. Po prvem načinu se razporeditev ovrednoti z uporabo ene same stroškovne funkcije. Po navadi je to stroškovna funkcija, po kateri iščemo najmanjše stroške glede na stroške prenosa materiala med napravami. Čeprav v tej stroškovni funkciji niso zajeti mnogi drugi kriteriji razvrščanja, je ta način ovrednotenja najpogostejši. Pri drugem načinu se razporeditev ovrednoti glede na razmerja med sosednjimi napravami. Ta način temelji na teoriji grafov. Tretji način ovrednotenja optimira razporeditev glede na več kriterijev in pri tem upošteva medsebojne odvisnosti. Upoštevani so lahko lega, usmeritev, neposredna okolica, pot, oddaljenost itn. identical dimensions, and also the distances between the individual machines are not fixed [5]. As a result, it is not possible to determine in advance the locations and then to place the devices at these locations. For this reason it is practically impossible with an FMS to locate the working device and workplaces using meth-ods based on the principle of “one place one device”. Therefore, many heuristic procedures have been developed that also use different assumptions and simplifications, so the solution is only approxi-mate. The target of all the methods is a minimising of transport costs; however, they differ in terms of ex-actingness, particularly in terms of the length of the procedure. Despite this, it cannot be decided with certainty which basic method and/or method of im-provement of the layout is the best [9]. Never the less, this area remains of interest to many researchers, because these days the problems are solved by new methods and with the possi-bility of applying more powerful, modern computers. This area of research currently covers different meth-ods and objectives. With respect to the objectives to be reached by the placing of the devices the appro-priateness of the methods of layout tend differ to. All methods have in common the assump-tion that the space is unchangeable, only the division of the space can be changed. The space can be represented in terms of the characteristics of the objects placed [7]: - Space divided into separate parts (in this type of placing the principle is: one object on one place). - Space represented as a free surface (in this case several objects are accommodated onto the com-mon surface). - Space represented as surface and form. The computer-aided layout of devices requires an evaluation of the layout. There are three principal ways of evaluating the layout. According to the first, the layout is evaluated by means of one cost function only. Usually, this is a cost function according to which the minimum cost with respect to the cost of transporting the material between devices is searched for. Although this cost function does not include many other criteria of the layout, this method of evaluation is the most com-mon. According to the second, the layout is evaluated with respect to the relations between the neighbouring devices. This approach is based on the theory of graphs. The third method of evaluation optimizes the layout with respect to several criteria by taking mutual dependen-cies into account. The position, orientation, immediate vicinity, path, distance, etc., can be taken into account. 30 Ficko M. - Brezočnik M. - Balič J. Strojniški vestnik - Journal of Mechanical Engineering 51(2005)1, 28-40 Razporejanje naprav na podlagi načela »ena naprava na eno mesto« je primerna za večino običajnih proizvodnih sistemov. Te metode vsebujejo predpostavko, da obstaja za n delovnih naprav n možnih leg, tako da je mogoče na eno lego namestiti natanko eno napravo. Problem se obravnava kot kvadratični prireditveni problem [1]. Kvadratični prireditveni problem spada med nestacionarne odločitvene probleme. Zaradi tega so bile razvite različne strategije iskanja kakovostnih rešitev. Te strategije bi lahko v splošnem razdelili na tri vrste [7]: - konstrukcijske - začetne strategije, - izboljševalne strategije in - hibridne metode. Začetne strategije razmestijo naprave eno za drugo na mesta po vnaprej določenih korakih in tako izdelajo končno rešitev. Izboljševalne strategije, nasprotno izhajajo iz začetne rešitve in jo nato po korakih izboljšujejo, metode takšne vrste sta tudi metodi simuliranega ohlajanja in genetskih algoritmov. Hibridne metode združujejo konstrukcijske in izboljševalne strategije. Metode razporejanja za probleme, pri katerih je prostor razdeljen na enake ločene dele, prirejajo eni lokaciji eno napravo. Vendar je tak način omejen in primeren samo za reševanje nekaterih problemov. Tako tak način ni primeren za oblikovanje POS-a. Prostor, ki ga potrebujejo posamezne naprave v POS-u, je namreč različno velik. Zaradi tega so bili razviti za razporejanje naprav po prostoru, ki se obravnava kot celota, naslednji postopki: - modularna metoda, - metoda razporejanja pravokotnikov, - metoda z omejitvami, - metoda na temelju teorije grafov, - metoda z izvedeniškimi sistemi. Čeprav poteka razvoj računalniško podprtega razporejanja že dolgo, je na tržišču zelo malo uporabnih izdelkov. Resda imajo mnogi programi za računalniško podprto načrtovanje nekatere zmogljivosti razporejanja, vendar največkrat ne gredo dlje od grafičnega vmesnika za ročno risanje razporeditve. Skoraj noben tržno dosegljiv program ne omogoča uporabe informacij o problemu in optimizacijskih postopkov. Sodoben tržni program mora vsebovati algoritem za optimizacijo razporeditve in interaktivni uporabniški vmesnik, tako da ima lahko človek zmožnost vplivanja na potek optimizacije. Končna razporeditev in tehniška dokumentacija nastaneta torej s sodelovanjem človeka. The layout of devices on the basis of the principle “one device on one place” is suitable for most conventional production systems. These meth-ods include the assumption that there are n possible locations for n working devices, so that it is possible to place exactly one device onto one location. The problem is treated as a quadratic assignment problem [1]. The quadratic assignment problem belongs to problem of NP (non-polynomial) completeness. For that reason different strategies of searching for high-quality solutions have been developed. In general, these strategies can be divided into three types [7]: - Construction – opening strategies. - Improvement strategies. - Hybrid methods. The opening strategies place the devices one after another onto their places by steps determined in advance, and in this way they find the end solutions. In contrast, the improvement strategies start from the initial solutions and then they improve the solution, step by step; two of such methods are the method of simulated annealing and the genetic algorithm method. Hybrid meth-ods combine the structural and improvement strategies. For problems where the space is divided into equal, separate parts the methods of layout assign one device to one location. However, such an approach is limited to, and suitable only for, solving some problems. For example, such an approach is not suitable for forming a FMS. The spaces required by the individual devices in a FMS are of different size. Therefore, the following approaches have been developed for plac-ing the devices in the space treated as a unit: - Modular method. - Method of the arrangement of rectangles. - Method with limitations. - Method on the basis of the theory of graphs. - Method with expert systems. Although development of computer-aided placing has been around a long time, very few com-mercial products are available on the market. Though many CAD programmes have some capabilities for placing, in most cases they do not proceed beyond the graphical user interface for manual drawing of the layout. Almost no commercially available programme ensures the use of the problem information and of the optimization procedures. A modern commercial programme must contain a algorithms for the optimiza-tion of the layout and an interactive user interface, so that a human can influence the optimization process. The final layout and the technical documentation re-sult from cooperation with the human. Oblikovanje prilagodljivega obdelovalnega sistema - A Model for Forming a Flexible Manufacturing System 31 Strojniški vestnik - Journal of Mechanical Engineering 51(2005)1, 28-40 2 MODEL OBLIKOVANJA POS-A Z GENETSKIMI ALGORITMI Problem razporejanja naprav spada med tako imenovane nedeterministične odločitvene probleme, ki niso rešljivi v polinomskem času [3]. Problem razporejanja je kombinatorne narave in zaradi tega primeren za reševanje s hevrističnimi metodami. Problem je teoretično rešljiv tudi s preizkušanjem vseh možnosti (tj. s slepim iskanjem), vendar pa izkušnje iz prakse kažejo, da pri takšnem načinu reševanja hitro presežemo zmožnosti, bodisi človeka bodisi računalnika, zaradi prevelikega števila mogočih rešitev. Tako je poglavitni problem pri iskanju rešitev pri kombinatoričnih problemih, obvladovanje eksplozije kombinacij. V preteklih letih so se genetski algoritmi izkazali pri reševanju tovrstnih problemov na najrazličnejših področjih tehnike. Zaradi teh lastnosti smo jih uporabili tudi pri oblikovanju POS-a. 2.1 Osnutek Pri postavitvi modela smo upoštevali naslednje omejitve: - delovne naprave oziroma prostor, ki ga potrebujejo, je pravokotne oblike, - strežba stroja poteka v središču stroja, - usmeritev strojev je znana in enaka za vse stroje. Pri oblikovanju modela razporeditve smo se omejili zgolj na razporeditev strojev v eni vrsti in razporeditev strojev v več vrstah. Krožno in sklenjeno razporeditev lahko obravnavamo podobno kakor razporeditev strojev v eni vrsti. Med razporejanjem v dveh ali več vrstah ni bistvenih razlik [6]. Tako lahko ta model s spremembami uporabimo tudi za druge oblike razporeditve naprav. Oblikovanje POS-a smo razdelili na dva glavna koraka: - določanje razporeditve in - izračun koordinat naprav. Pri tem je določanje razporeditve in vrednotenje le-te prepuščeno genetskemu algoritmu. Tako se v prvem koraku ustvarja z genetskimi opravili zaporedje naprav, v drugem pa se glede na zaporedje in pravila ustvarja dejanska razporeditev z vsemi merami. Osnutek oblikovanja POS-a z genetskimi algoritmi prikazuje slika 1. 32 2 MODEL FOR FORMING THE FMS USING GE-NETIC ALGORITHMS The problem of layout of devices belongs to the decision problems that are not solvable within the polynomial time [3]. The problem of the layout is combinatory in nature and is, therefore, suitable for solving by heuristic methods. The problem is theo-retically solvable also by testing all possibilities (i.e., by blind searching), but practical experiences show that in the case of such a way of solving the capaci-ties of either the human or the computer are quickly extended due to the large a number of possible solutions. Thus, the principal problem in searching for the solution in the case of combinatory problems is controling the explosion of combinations. In recent years genetic algorithms have proved to be appro-priate for solving such problems in different areas of technology. Because of these properties, genetic al-gorithms have been used for forming FMSs. 2.1 Concept When making the model the following limi-tations were taken into account: - The working devices and/or the space required by them are of rectangular form. - The machine is operated in its center. - The orientation of machines is known and equal for all machines. For forming the model of the layout we limited ourselves only to the layout of machines in one row and to the layout of machines in multiple rows. The circular and closed layout can be treated simi-larly as the layout of machines in one row. There are no major differences between the layouts in two or multiple rows [6]. Thus, this model with modifica-tions can also be used for other forms of layout of devices. The forming of the FMS was divided into two main steps: - Determination of the layout. - Calculation of the coordinates of the devices. The determination of the layout and its evaluation is left to the genetic algorithm. Thus, in the first step the sequence of the machines is cre-ated by genetic operation, whereas in the second step the actual layout with all the dimensions is cre-ated with respect to the sequence and the rulers. The concept of forming the FMS with genetic algo-rithms is shown in Figure 1. Strojniški vestnik - Journal of Mechanical Engineering 51(2005)1, 28-40 podatkovna baza database vhodne informacije: input information: - matrika frekvenc - matrix of frequencies - matrika cen - matrix of costs - matrika najmanjših dovoljenih razdalj - matrix of minimum allowable distances - matrika izmer naprav - matrix of dimensions of devices shema razporeditve diagram of layout človek human ocenitev razporeditve evaluation of layout > genetski algoritem genetic algorithm določanje razporeditve determination of layout izračun koordinat calculation of coordinates " ovrednotenje ""¦ razporeditve evaluation of layout Sl. 1. Model reševanja problema oblikovanja prilagodljivega obdelovalnega sistema Fig. 1. Model of solving the problem of forming the FMS Za tak način reševanja problema je treba poznati matriko izmer naprav in matriko najmanjših dovoljenih razdalj med napravami. Nadalje je treba poznati matriko prenesenih količin med posameznimi napravami N v nekem časovnem obdobju. Znani morajo biti tudi spremenljivi prenosni stroški, ki so odvisni od uporabljenega prenosnega sredstva. Te informacije pridobimo iz baze podatkov, ki jo moramo predhodno izdelati. Ta baza podatkov se lahko uporabi večkrat pri izdelavi različnih POS-ov. Vsebuje podatke, ki so odvisni od posameznih gradnikov teh sistemov. To so podatki, kakor so cene gibov prenosnih naprav na enoto dolžine, najmanjše zahtevane razdalje med posameznimi stroji in gabaritne mere naprav. Frekvence hodov naprav so odvisne od izdelkov, ki se bodo izdelovali s tem POS-om. Genetski algoritem tako črpa podatke, ki jih potrebuje, iz te baze podatkov. Samo razporeditev določi samodejno z uporabo genetskih opravil in evolucije. Ko genetski algoritem več ne more izboljšati razporeditev, se evolucija ustavi in se izdela shema razporeditve, ki jo nato strokovnjak oceni še glede na kriterije, ki niso bili zajeti v stroškovni funkciji. V primeru, da ni zadovoljen z rešitvijo, se genetski algoritem požene ponovno, saj lahko dobimo po drugi evoluciji drugo razporeditev s podobno vrednostjo stroškovne funkcije. For such a method of solving the problem it is necessary to know the matrix of dimensions of the devices and the matrix of minimum allowable distances between the devices. Further, it is necessary to know the matrix of transport quantities between the indi-vidual devices during a certain time period. Also, the variable transport costs, depending on the means of transport used must be known. This information is gained from the database that is made previously. This database can be used several times for the con-struction of different FMSs. It contains the data that depend on the individual components of the FMS. These data are, for instance, the prices of motions for the transport devices per unit of length, the minimum required distances between the individual machines, and the overall dimensions of the devices. The fre-quencies of motions of the transport devices depend on the products to be made by this FMS. Thus, the genetic algorithm takes the data needed from that database. It automatically determines the layout itself by means of genetic operations and evolution. When the genetic algorithm can no longer improve the layout the evolution is stopped and a diagram of the layout is made. The diagram is then evaluated by the expert with respect to the criteria not included in the cost function. If the expert is not satisfied with the solution, it is started again, since after the second evolution another layout with a similar value of cost function can be obtained. Oblikovanje prilagodljivega obdelovalnega sistema - A Model for Forming a Flexible Manufacturing System 33 Strojniški vestnik - Journal of Mechanical Engineering 51(2005)1, 28-40 2.2 Stroškovna funkcija 2.2 Cost function Iščemo minimum stroškovne funkcije, ki zajema spremenljive prenosne stroške: The minimum cost function comprising variable transport costs is searched for: nn i=1 j=1 (1), kjer so: n število strojev, f ij frekvenca gibov prenosne naprave oziroma manipulatorja med napravama i in j, c spremenljivi prenosni stroški za količinsko enoto v denarni enoti, L pa je razdalja med napravama i in j. Prenosne stroške med dvema napravama lahko določimo, če poznamo njuno medsebojno oddaljenost. V primeru, da razvrščamo naprave v črti, je Lij enak: where n is the number of machines, fij is the frequency of motions of the transport device and/or the handling device between the devices i and j, cij are the variable transport costs for the quantity unit in the monetary unit and Lij is the distance between the devices i and j. The transport costs between the two devices can be determined if their mutual distance is known. In the case when the devices are placed in a line Lij is equal to: \xi-xj\ = -(li+lj) + dij i = 1, , n-1 j = i+1,..., n (2). V zgornjih izrazih so: fij frekvenca gibov med napravo i in napravo j, cij cena giba med napravo i in j na enoto dolžine, li dolžina stroja v smeri poteka vrste napravo, dij najmanjša potrebna razdalja med napravo i in j, xi razdalja med središčem naprave in izhodiščno točko (izhodiščem koordinatnega sistema). Parametre li, lj in di in spremenljivke x in x prikazuje slika 2. Izhodiščno črto predstavlja lv. Da ne dobimo negativnih vrednosti stroškovne funkcije, vzamemo razlike razdalj med strojema i in j ter izhodiščno črto lv v absolutni vrednosti. Smer, ki jo predstavlja predznak, v tem primeru ni pomembna. Z upoštevanjem enačbe (2) lahko stroškovno funkcijo 1 napišemo v obliki: nn i=1 j=1 In the above terms li is the length of the device i in the direction of the row of devices, dij is the minimum required distance between the device i and j, xi is the distance between the center of the device and the starting point (starting point of the coordinate system). The parameters li, lj and dij and the variables xi and xj are shown in Figure 2. The starting line is lv. In order not to obtain negative values for the cost function, the differences of the distances between the machines i and j and the starting line lv are taken in the absolute value. By taking equation 2 into account the cost function 1 can be written in the following form: fij-\xi (3). Ji______,J 3___________J Sl. 2. Prikaz parametrov in spremenljivk dolžine Fig. 2. Representation of parameters and length variables 34 Ficko M. - Brezočnik M. - Balič J. v Strojniški vestnik - Journal of Mechanical Engineering 51(2005)1, 28-40 2.3 Predstavitev organizma 2.3 Representation of the organism Uporabimo permutacijsko kodiranje. En organizem pomeni eno rešitev problema razporejanja. Zaporedje delovnih naprav je predstavljeno z zaporedjem genov v organizmu. Vsak gen enolično pomeni eno napravo. Če imamo npr. šest delovnih naprav, ki so postavljene v vrsto, je razpored lahko enak: For the representation of the organism, permutation coding is used. One organism represents one pos-sible solution of the problem of the layout. The sequence of working devices is presented with the sequence of genes in the organism. Each gene unambiguously rep-resents one device. If, for example, six working devices placed in a row are in question the layout is as follows: [s4,s1, s6,s3,s2,s5 kjer si pomeni stroj i, njegovo mesto v organizmu pa pomeni mesto v dejanskem razporedu. Torej je organizem lahko enak: where si represents the device i, and its place in the organism represents its actual arrangement. Thus, the organism can be equal to: ok = [4,1, 6,3, 2,5] kjer je ok organizem k v trenutni generaciji. 2.4 Ovrednotenje organizma Populacijo organizmov je treba po opravljenih genetskih opravilih ovrednotiti. V splošnem lahko organizem ok predstavimo kot: where ok is the organism k in the current generation. 2.4 Evaluation of the organisms After the completion of the genetic operations it is necessary to evaluate the population of the organisms. In general, the organism ok can be represented as: 1 ,s2,s3 ,s4,s5 ,s6 kjer pomeni sk delovno napravo, ki je na mestu i v organizmu k. Glede na zaporedje naprav, ki je podano v organizmu, lahko sedaj izračunamo koordinate delovnih naprav (mesta središča delovne naprave). where sik stands for the working device located at the place i in the organism k. With respect to the sequence of the devices given in the organism it is now possible to calculate the coordinates of the working devices. ok = |_s1 ,s2,s3,s4,s5 ,s6 J -> X = \_ x1x2x3x4x5x6 xk je razdalja od središča naprave, ki je na mestu i, do izhodiščne črte. X je matrika teh razdalj za vse naprave. Sedaj, ko imamo razdalje središča delovne naprave od izhodiščne Črte, lahko izračunamo skupne stroške prenosa oziroma manipulacije s stroškovno funkcijo 3. 2.5 Genetski operatorji Za takšno vrsto kodiranja obstaja mnogo različnih genetskih operatorjev. Uporabili smo delno mapirano križanje in obrnjeno ter recipročno mutacijo. xik is the distance from the center of the device lo-cated at the place i to the starting line. X is the matrix of these distances for all devices. Now that the distances of the center of the working device from the starting line are known, the total handling/transport costs can be calculated ac-cording to function 3. 2.5 Genetic operators There are many different genetic operators for such a type of coding. We used the partial mapped crossover and the inverse and reciprocal Oblikovanje prilagodljivega obdelovalnega sistema - A Model for Forming a Flexible Manufacturing System 35 Strojniški vestnik - Journal of Mechanical Engineering 51(2005)1, 28-40 1. Izberi naključni podniz starš 1 5 3 2 9 7 4 8 točki križanja T 6 1. Select random sub-row parent 1 point of crossover starš 2 146 37 5 8 2 9 parent 2 2. Izmenjava podnizov zametek potomca 1 532975 82 6 zametek potomca 2 14637 14 8 9 2. Exchange of sub-rows germ of offspring 1 germ of offspring 2 3. Določanje pravila preslikovanja 3. Determination of the rule for mapping 5 *—>¦ 1 *—> 8 «-> 4 4. Oblikovanje pravilnega potomca potomec 1 13497 5 8 2 6 4. Creation of the correct offspring offspring 1 potomec 2 5 2 637 14 8 9 offspring 2 Sl. 3. Delno preslikano križanje Fig. 3. Partial mapped crossover naključno izbrani mesti randomly selected places r^ prvotni organizem 24 7 53 6 198 podniz 53 6 1 obrnjeni podniz 16 3 5 organizem po mutaciji 24 7 16 3 5 98 original organism sub-row inverse sub-row organism after mutation Sl. 4. Obrnjena mutacija Fig. 4. Inverse mutation Delno preslikano križanje je podobno preprostemu dvotočkovnemu križanju (sl. 3). Vendar pa moramo organizem z ustreznim postopkom še popraviti, saj mora biti vsaka naprava v posamezni razporeditvi natanko enkrat. Pri obrnjeni mutaciji najprej izberemo dva gena v organizmu. Nato se podniz, ki ga omejujeta ta dva gena, izreze in vstavi nazaj na isto mesto v nasprotnem vrstnem redu (sl. 4). Pri mutaciji z recipročno zamenjavo izberemo dva mutations. The partial mapped crossover is similar to the simple two-point crossover (Figure 3). How-ever, the organism must still be corrected by a suit-able procedure, since each device must be located in the individual layout precisely once. In the case of an inverse mutation two genes in the organism are selected. Afterwards, the sub-row limited by those two genes is cut out and put onto the same place in the inverse sequence (Figure 4). In the case of the mutation two random genes are 2 36 Ficko M. - Brezočnik M. - Balič J. Strojniški vestnik - Journal of Mechanical Engineering 51(2005)1, 28-40 prvotni organizem naključno izbrani mesti randomly selected places zamenjava genov exchange of genes original organism organizem po mutaciji 49 637 1258 organism after mutation Sl. 5. Recipročna mutacija Fig. 5. Reciprocal mutation naključna gena, nato pa zamenjamo njuni mesti (sl. 5). 3 PRIMER Slika 6 prikazuje POS. Takšna vrhunsko avtomatizirana obdelovalna celica je zmožna obdelati določen spekter obdelovancev brez ustavitve in je primerna za manjša in srednja podjetja. Sestavljajo jo štirje proizvodni stroji, dve vpenjalni mesti, pralna postaja in sedem odlagalnih mest. Vsaka naprava ima ustrezno kodo, ki predstavlja posamezen gen v organizmu. Prikazana je le ena izmed mogočih razporeditev, ki pa zaradi velikih stroškov prenosa ni najboljša. Prenosni stroški so lahko v tem primeru tudi do 5-krat večji od najmanjših (optimalnih). Za optimiranje konfiguracije POS-a na sliki 6 potrebujemo preglednico imen strojev, matriko mer, matriko frekvenc gibov, matriko stroškov in matriko najmanjših dopustnih razdalj. Potem ko določimo matrike, lahko poženemo genetski algoritem. Za selected by reciprocal exchange, after which their locations are exchanged (Figure 5). 3 EXAMPLE Figure 6 shows a FMS. Such a highly automated manufacturing cell is capable of machining a cer-tain range of workpieces without interruption, and is suitable for small and medium-sized companies. It com-prises four production machines, two fixing points, a washing station and seven stacking points. Each device has its own code representing the relevant gene in the organism. Only one of the possible layouts is shown, which, however, is not the best, due to high transport costs. The transport cost in this case can be up to five times higher than the minimum (optimum) cost. In order to optimize the configuration of the FMS in Figure 6 the table of names of the machines, the matrix of dimensions, the matrix of frequencies of mo-tions, the matrix of costs and the matrix of minimum allowable distances are needed. When the matrices have been determined, the genetic algorithm can be - odlagalno mesto - stacking point vpenjalno vpenjalno mesto 1 mesto 2 fixing point 1 proizvodni stroj 1 fixing machine tool 1 point 2 proizvodni stroj 3 proizvodni machine tool 3 stroj 2 machine tool 2 ? proizvodni stroj 4 machine tool 4 ? (13) (6) (14) (8) (1) (9) (2) (10) (3) (11) (4) (12) (5) Sl. 6. Razporeditev delovnih naprav v prilagodljivem obdelovalnem sistemu Fig. 6. Layout of working devices in FMS pralna postaja washing station ? (7) Oblikovanje prilagodljivega obdelovalnega sistema - A Model for Forming a Flexible Manufacturing System 37 Strojniški vestnik - Journal of Mechanical Engineering 51(2005)1, 28-40 prilagojenost 90E-°5 fitness 8.0E-05 7.0E-05 najboljša prilagojenost best fitness ___ povprečna prilagojenost average fitness najslabša prilagojenost worst fitness 0 100 200 300 400 500 600 700 800 900 1000 število generacij number of generations Sl. 7. Prilagojenost najboljšega, najslabšega organizma in povprečna prilagojenost organizmov v posamezni populaciji Fig. 7. Fitness of the best and worst organism and average fitness of organisms in the individual population optimiranje razporeditve smo določili naslednje evolucijske parametre: - velikost populacije je 100 organizmov, - verjetnost reprodukcije je 30%, - verjetnost križanja je 40%, - verjetnost mutacije organizma je 30%, kar pomeni, da je verjetnost mutacije posameznega gena 2%, - število generacij, ki se izvedejo med evolucijo, je 1000. Ker je mogoče, da z vsako evolucijo ne pridemo do optimalne razporeditve, moramo evolucijo večkrat ponoviti. Razlog za to je, da rešitve včasih zaidejo v lokalni optimum, od koder, zaradi pomanjkanja ustreznega genetskega materiala, ni več mogoče napredovati. Zaradi tega določimo največje število generacij, do katere je evolucijo še smiselno izvajati. Na sliki 7 je prikazan potek evolucije pri enem izmed zagonov. Prikazana je prilagojenost najboljšega in najslabšega organizma ter povprečna prilagojenost organizmov v posamezni populaciji med evolucijo. Prilagojenost je enaka obrnjenim vrednostim stroškovne funkcije. Razvidno je, da so na začetku evolucije spremembe organizmov zelo velike in imajo velike vplive na vrednost stroškovne funkcije. Vrednost stroškovne funkcije se takrat najbolj zmanjša. Ko je rešitev že zelo blizu globalnega optimuma, se started. For the optimization of the layout the following evolutionary parameters have been determined: - The size of the population is 1000 organisms. - The probability of reproduction is 30%. - The probability of crossover is 40%. - The probability of the mutation of an organism is 30%, i.e., the probability of mutation of an indi-vidual gene is 2%. - The number of generations during the evolution is 1000. Since it is possible that the evolution does not result in the optimum layout, the evolution must be repeated several times. The optimum solution is not always reached because sometimes the evolution goes astray into a local minimum, from where the genetic algorithm can no longer progress due to a lack of proper genetic material. Therefore, the great-est number of generations is determined, up to which it is appropriate to carry out evolution. Figure 7 shows the process of the evolution in one of the runs. The fitness of the best and the worst organisms and the average fitness of the organisms in the individual population during the evolution are indicated. The fitness is equal to the inverse values of the cost function. It is evident that in the beginning of the evolution the changes in the organisms are very great and have great influences on the value of the cost function. The value of the cost function then falls the most. When, however, 38 Ficko M. - Brezočnik M. - Balič J. Strojniški vestnik - Journal of Mechanical Engineering 51(2005)1, 28-40 Preglednica 1. Rešitve pridobljene v posameznih zagonih evolucije Table 1. Solution obtained in the individual runs of the evolution evolucija št. genotip fenotip evolution No. genotype fenotype 1 5 12 4 11 2 9 14 7 8 1 10 3 13 6 12025 2 4 11 2 9 7 14 1 8 10 3 12 5 13 6 13020 3 6 13 4 11 3 10 14 7 9 2 8 1 12 5 13075 4 6 13 3 10 1 8 14 7 9 2 11 4 12 5 12040 5 5 12 4 11 2 9 14 7 8 1 10 3 13 6 12025 6 6 13 3 10 1 8 14 7 9 2 11 4 12 5 12040 7 6 13 4 11 3 10 1 8 14 7 9 2 12 5 13170 8 6 13 3 10 1 8 14 7 9 2 11 4 12 5 12040 vrednost stroškovne funkcije le še malenkostno the solution is very near the global optimum, the spreminja. value of the cost function changes only very slightly. Ko smo opravili osem zagonov evolucije, When the eight runs of evolution were ef- smo dobili rezultate, prikazane v preglednici 1. fected, the result shown in Table 1 was obtained. Najboljšo rešitev smo dobili že v prvem in nato še v The best solution was reached in the first and fifth petem zagonu. Stroji in naprave so si v tej najboljši runs. The sequence of the individual machines and rešitvi sledili takole: proizvodni stroj 3 (5), odlagalno devices is as follows: machine tool 3 (5), stacking mesto (12), proizvodni stroj 2 (4), odlagalno mesto point (12), machine tool 2 (4), stacking point (11), (11), vpenjalno mesto 2 (2), odlagalno mesto (9), fixing point 2 (2), stacking point (9), stacking point odlagalno mesto (14), pralna postaja (7), odlagalno (14), washing station (7), stacking point (8), fixing mesto (8), vpenjalno mesto 1 (1), odlagalno mesto point 1 (1), stacking point (10), machine tool 1 (3), (10), proizvodni stroj 1 (3), odlagalno mesto (13), stacking point (13), machine tool 4 (6). proizvodni stroj 4 (6). From the results it can be concluded that Iz rezultatov lahko sklepamo, da je metoda the method is suitable for searching for good lay- primerna za iskanje dobrih razporeditev. Iz outs. The table shows that even the less-favourable preglednice je razvidno, da so tudi slabše solutions are appropriate, since the value of their razporeditve povsem uporabne, saj se razlikujejo za cost function differs by less than 10% from the value manj ko 10 odstotkov od optimalne. of the cost function of the optimal solution. 4 SKLEP 4 CONCLUSION Raziskava je pokazala, da z uporabo As shown by the results, we have reached genetskih algoritmov pri razporejanju naprav v POS good solutions by using genetic algorithms for plac- pridemo do dobrih rešitev. Pri tem ne potrebujemo ing the devices in the FMS. No rules for forming nobenih pravil oblikovanja takšnega sistema, ampak such a system are needed, it is only necessary to moramo samo zbrati podatke, ki so specifični za collect the data specific to the transport in the FMS. prenos v POS-u. Z uporabo genetskih algoritmov By using genetic algorithms good solutions, which lahko nato v nekaj minutah dobimo dobre rešitve may even be optimal, can be obtained within a few problema, ki so lahko tudi optimalne. minutes. V nadaljnjem delu je mogoče metodo In future work the methods might be com- dopolniti v duhu oblikovanja ciljne funkcije, ki bo pleted in terms of forming a target function that will zajemala več ekonomsko tehničnih parametrov in include more economical and technical criteria, and ne samo spremenljive prenosne stroške. Tako bi z not only variable transport costs. Thus, by intro- vključitvijo dodatnih kriterijev ovrednotenja ducing additional criteria with an evaluation a more ustvarili realnejšo ciljno funkcijo in s tem izločili real target function would be needed and the need navzočnost strokovnjaka, ki na koncu oceni rešitev. for the expert finally evaluating the solution would S spremembo modula za izračun dolžin poti med be eliminated. By modifying the module for the cal- Oblikovanje prilagodljivega obdelovalnega sistema - A Model for Forming a Flexible Manufacturing System 39 Strojniški vestnik - Journal of Mechanical Engineering 51(2005)1, 28-40 posameznimi napravami lahko model nadalje culation of the length of the paths between the indi- razširimo tudi na področje oblikovanja POS-ov v vidual devices the model can be further expanded to več vrstah. the area of forming the FMS in multiple rows. 5 LITERATURA 5 REFERENCES [I] Armour, G. C, E. S. Buffa (1963) A heuristic algorithm and simulation approach to relative allocation of facilities. Management Science. Vol. 9, 294-309. [2] Balič, J. (2000) Flexible manufacturing systems. Faculty of mechanical engineering. Maribor. [3] Garey, M. R., D.S. Johnson (1979) Computers and intractability: A guide to the theory of NP-completeness. Freeman. New York. [4] Gen, M., R. Cheng (1997) Genetic algorithms and engineering design. J. Wiley & Sons, Inc.. New York. [5] Heragu, S., A. Kusiak (1988) Machine layout problem in flexible manufacturing systems. Operations Resarch. Vol. 36, 258-268. [6] Kusiak, A. (1990) Intelligent manufacturing systems. Prentice-Hall, Inc.. New Jersey [7] Liggett, R. S. (2000) Automated facilities layout: past, present and future. Automation in Construction. Vol. 9, 197-215. [8] Pahole, I. (1997) Planiranje, vodenje in optimiranje inteligentnih fleksibilnih obdelovalnih sistemov z uporabo koncepta pretočne matrike, doktorska disertacija. Fakulteta za strojništvo. Maribor. [9] Polajnar, A. (1997) Proizvodni management. Fakulteta za strojništvo. Maribor. [10] Tompkins, J. A. and JA. White, YA. Bozer, E.H. Frazelle, J.M. Tanchoco & J. Trevino (1996) Facilities planning. John Wiley & Sons. New York. [II] Tratnik, M. (2000) Razmeščanje delovnih naprav pri delavniškem proizvodnem načinu. Rešitve proizvodnih problemov. 179-187. Naslov avtorjev: mag. Mirko Ficko Author’s Address: Mag. Mirko Ficko profdr. Miran Brezočnik Prof.Dr. Miran Brezočnik profdr. Jože Balič Prof.Dr. Jože Balič Univerza v Mariboru University of Maribor Fakulteta za strojništvo Faculty of Mechanical Eng. Smetanova 17 Smetanova 17 2000 Maribor SI-2000 Maribor, Slovenia mirko.ficko@uni-mb.si mirko.ficko@uni-mb.si mbrezocnik@uni-mb.si mbrezocnik@uni-mb.si joze.balic@uni-mb.si joze.balic@uni-mb.si Prejeto: Sprejeto: Odprto za diskusijo: 1 leto 24.3.2003 2.12.2004 Received: Accepted: Open for discussion: 1 year 40 Ficko M. - Brezočnik M. - Balič J.