Paper received: 11.05.2009 Paper accepted: 16.09.2009
Emergent Synthesis Based Multi-Objective Design of the Manufacturing System Shop-Floor
Zlatan Car1' - Branimir Barisic1 - Miroslaw Rucki2 1 University of Rijeka, Faculty of Engineering, Croatia 2 Poznan University of Technology, Institute of Mechanical Technology, Poland
This article presents a new approach for multi-objective design of the manufacturing system shop-floor. The proposed model for multi-objective design is based on the Emergent Synthesis approach. Emergent Synthesis related approaches use both, bottom-up and top-down features, unlike traditional analytical, deterministic approaches based on top-down problem decomposing. Based on the proposed approach a simulation model has been built and analysed. The Genetic Algorithm (GA) has been implemented in the proposed model for in final optimization process. From the obtained results of the simulation it can be concluded that with the utilization of the proposed approach for adaptable design the model has a high level of multi-objective adaptation in the design of the manufacturing system shop-floor. One of the major characteristics of the here proposed approach for multi-objective design of the manufacturing system is that the model has the ability for a simultaneous influence on the design and adaptation of the shop-floor layout and that it adapts to scheduling rules. © 2009 Journal of Mechanical Engineering. All rights reserved. Keywords: multi-objective design, Emergent Synthesis, BMS, genetic algorithm
0 INTRODUCTION
The main problem in today's global and rapidly changing dynamical manufacturing environment is how to design, build and control a manufacturing system with a sufficiently long life-time. The life-time of the manufacturing system needs to be sufficiently long to pay off the initial capital invested in the system and to produce profit. This is because globalisation has caused an increase in uncertainty and complexity in a manufacturing environment. In this environment, a kind of products increase and the product life cycle time decreases drastically. Such market behaviour also requires less manufacturing system leading time, which means the design and development/reconfiguration time of manufacturing systems [1] to [3]. We can say that the lead time for reconfiguration and development of manufacturing systems today has become a bottleneck. Those are the basic and classical problems of today's manufacturing systems based companies.
1 MODEL AND METHODOLOGY
For the solution to the above mentioned problems the following solutions which do not only use classical approaches for production planning and control have been proposed: re-
configure Flexible Manufacturing Cells (FMC), Reconfigurable Manufacturing Systems (RMS), Biological Manufacturing Systems (BMS), etc [1] and [4] to [5].
According to the above defined preambles a model of non-existing production system in a discreet simulation environment was developed and the production schedule method was defined. This was done for the following reasons; firstly it will be possible to test and analyze system behaviour (its components) before actually building the system and secondly, it will be possible to analyze the proposed production schedule methodology and to adjust it for the expected manufacturing environment [5] to [8].
1.1 Emergent Synthesis Approach
Emergent Synthesis approaches can be literally defined by its name. The literal definition (Oxford Dictionary) of a synthesis is "combined elements into a whole". Here the term 'synthesis' is closely related to human activities for the creation of artificial things. However, in this case synthesis is also closely related to analysis because in order for all the elements of the system to be able to utilise a pragmatic structure, a "new whole", the elements need to be analysed before. This is needed to defined there functional
Corr. Author's Address: Faculty of Engineering, Rijeka University, Vukovarska 58, Rijeka, Croatia, zlatan.car@riteh.hr
interrelationship, nature, inside proposed pragmatic structure [7].
In order to be more specific about the emergence of the applied terms, what is really meant by the use of the term in other fields first needs to be defined. The term 'emergence' can be defined from a linguistic, evolutionary, physical, mathematical, or some other point of view. The Oxford Dictionary defined 'emergence' as something that becomes known or revealed. Morgan defines emergence like of stable order [10]. The term emergence has, in recent years, been used in many fields to describe qualitatively different observations. According to Cariani [11], various definitions of emergence can be broken down into three broad categories: computational (mathematically based concept), thermodynamic (physically based materialism) and relative to a model (functionally based hylomorphism). A new direction in Artificial Life was introduced by Langton [12]. He defines emergence in terms of a feedback relation between the levels in a dynamical system; local micro-dynamics cause global macro-dynamics while global macro-dynamics constrain local micro-dynamics. This definition implies that implicit global complexity emerges from explicit local simplicity.
According to the above definitions we can say that Emergent Synthesis related approaches use both, bottom-up and top-down features, unlike traditional analytical, deterministic approaches based on top-down problem decomposing; such as operational research, symbolic artificial intelligence, etc. Those approaches include evolutionary computation, self-organisation, behaviour-based methods, multi-agent systems, and are capable of offering efficient, robust and adaptive solutions to the problem of synthesis [7] and [9].
Emergent Synthesis was introduced in the proposed model for design within two separate levels. At the first level the concept of the BMS (lineless manufacturing) was applied and at the second level a characteristic structure of the model within the implementation of the layered based architecture was proposed. With this approach it is possible to achieve synthesis between the simulation of lineless manufacturing systems and the real ones through layered architecture with the introduction of constraints, behaviour and flow of information.
1.2 Layered Architecture
By introducing multi-objective design and adaptable reconfiguration based on layered architecture and BMS concept (lineless manufacturing systems) we trade between high adaptability of lineless production and reducing technical difficulties of the implementation of the lineless production in a real manufacturing environment with the introduction of constraints for the movement of the elements of the manufacturing system and the number of different products on shop-floor. With the implementation of this approach emergence of the candidate structure is obtained. The proposed model has the following characteristics. The model consists of three interdependent layers (Figure 2): virtual Biological Manufacturing Systems, Control and Reconfiguration, and the Real Manufacturing System. Through layered architecture a synthesis between the simulation of lineless manufacturing systems and the real ones by introducing the constraints is achieved. Virtual Biological Manufacturing System is an extension of the real manufacturing system based on the concept of BMS. In this layer the simulation of the lineless manufacturing system for simulation of the production of the new order is used. Here, highly adaptable features of the BMS in the dynamic manufacturing environment, floor level are used. The control of the production in the lineless manufacturing system is too complex to be controlled with traditional methods, because of a large degree of freedom of the system. To overcome this problem it has been proposed by Ueda self-organisation model of the control [13]. In the presented model the two phases' segregated self-organisation for control of the lineless manufacturing system in production [14] are proposed. Through this type of self-organisation interaction between the elements of the manufacturing system on the local and global level is obtained. A layer of control and reconfiguration is used for introduction and analysis of the new proposed structure, configuration of the manufacturing system, in the reconfiguration mode, and control of the real manufacturing system in work mode. A layer analysis of the proposed structure is performed in order to recognise function within manufacturing environment. This layer is the key layer in the presented approach for adaptable reconfiguration.
purpose/^
undetermined system o o
function / direct problem
purpose/^
inverse problem
eS
environment	structures
Fig. 1. Methodology of Emergent Synthesis (by Prof. Kanji Ueda) [6]
Virtual
Biological Manufacturing System
Layer of Control and Reconfiguration
Layer of Real Manufacturing System
Fig. 2. The layered architecture of the BMS [12]
With the introduction of layered architecture and in particular this layer gives ability to the model to breach the gap between simulation and the real manufacturing system. This layer has two very important characteristics. Firstly, through this layer reality in the simulation by introducing position constraints for the movements of the elements of the manufacturing system are indirectly introduced. Secondly, through this layer noise from surrounding manufacturing system environment is introduced. The level of reality, complexity and uncertainty which will be introduced in the simulation is filtrated through the layer of the real manufacturing system.
1.3 The Genetic Algorithm (GA)
Studies have shown that with GA good solutions in short time processing can be obtained [15] and [16]. Genetic algorithms were formally
introduced in the 1970s by John Holland at University of Michigan. The continuing price/performance	improvements	of
computational systems have made them attractive for some types of optimization. In particular, genetic algorithms work very well on mixed (continuous and discrete), combinatorial problems. They are less susceptible to getting 'stuck' at local optima than gradient search methods. But they tend to be computationally expensive. To use a genetic algorithm, a solution to the problem must be represented as a genome (or chromosome). The genetic algorithm then creates a population of solutions and applies genetic operators such as mutation and crossover to evolve the solutions in order to find the best one(s). This presentation outlines some of the basics of genetic algorithms. The three most important aspects of using genetic algorithms are: (1) the definition of the objective function, (2) the definition and implementation of the genetic
representation, and (3) the definition and implementation of the genetic operators. Once these have been defined, the generic genetic algorithm should work fairly well. Besides that many different variations to improve performance can be tried, multiple optima (species - if they exist) can be found, or the algorithms can be parallelized [17] and [18].
1.4 The Description of the Manufacturing System
The model for the simulation of the design of the production system was developed in a discreet simulation environment (eM-Plant from Siemens PLM). This model was developed by using main sketch analyses for the technologically defined production. The model was divided in three man sub layers, Figure 3. The first layer is the main production group. In this area the main components production is performed. In the initial setup 24 machined was proposed for this layer. In the second layer assembly is performed, in total 42 machines were used divided in 3 groups. This layer does not not only have interconnections with two other layers but also with the manufacturing environment. This is necessity for additional components that are needed to assemble the main products. In the third layer packing, sorting and preparation for transport is performed. The most demanding and complex problems occurred in the first two layers. Therefore, during the model development only the first two layers were modelled in details, and the third layer was modelled just in few points.
1.4.1 Product topology
The topology will be described giving only the necessary details. This is because the product for which the production system is developed is under patent rights, so a deeper discussion would be limited. The one product (final assembly) consists from three main subassemblies. The first subassembly consists from 120 parts, where 105 parts are produced in the proposed production system. The second subassembly consists from 15 parts, all produced in the production system, and the third subassembly consist from 20 parts (12 produced in the production system).
As it can be understood from the above description, most parts for the final assembly are produced in the same production system. However, this does not reduce the problem of the influence of the external environment on the system. To reduce the complexity of the simulation model during the initial development it was decided that all the necessary parts which would be imported outside of the main production system be available on time.
1.5 Methods and Heuristics
Emergent Synthesis was introduced in the proposed model for design within two separate levels. At the first level the concept of the BMS (lineless manufacturing) was applied and at the second level a characteristic structure of the model within the implementation of the layered based architecture was proposed,. With this approach it was possible to achieve synthesis between the simulation of lineless manufacturing systems and the real ones through layered architecture with the introduction of the constraints, behaviour and flow of information.
The emerging behaviour, two phases' self-organisation, in the Virtual Biological Manufacturing System is based on the scheduling rule and topological position of machines on the shop-floor. In the layer of the Virtual BMS there are two types of scheduling problems: scheduling for dispatching of a new order for reconfiguration and production scheduling, production in the lineless simulation. In the layer of the control and reconfiguration (and real manufacturing system) there are also two scheduling problems scheduling for dispatching of a new order for production and production scheduling. However, the production scheduling is obtained from the predefined machine sequence which emerges in the Virtual BMS.
The scheduling for dispatching products on the manufacturing system shop-floor (for reconfiguration and production process) is purely of a production nature, and a very important problem. This is because in case there is a large number of orders which coexist on the same shop-floor the influence of the dispatch rule on the overall production time of the order can be crucial. Due to this reason we have used ATC heuristic as technical solution.
Fig. 3. Schematic description of the technologically defined production
The Apparent Tardiness Cost (ATC) heuristic is presented in the equation(1) [19] and [20].
^ max (dj - pj -1' 0 ) ^
I. = — exp
j Pj
k p
(1)
where are wj weight of job j, priority factor, pj [s] processing time on the of job j, dj [s] due date of job j, t [s] time, k scaling factor and p average of the processing time of the remaining jobs.
ATC heuristic gives us the ability of the dynamic adaptation through time scale. ATC combines Weighted Shortest Processing Time first (WSTP) and Minimum Slack first (MS) [20] and [21]. These characteristics are given as a possibility for the adaptation of scheduling rules. WSTP is a static rule, a function of the job and/or machine. MS is a dynamic rule; a function of job j and time t (2) and job with minimum slack is scheduled.
max (dj - pj -1, 0)	(2)
where are pj [s], processing time on the of job j, dj [s] due date of job j, t [s] time.
If parameter k is very large, the ATC rule is reduces to the WSTP rule. If k is very small, the ATC rule is reduces to the MS rule when there are no overdue jobs and to the WSTP rule for the overdue jobs otherwise. In our model a scaling factor k for tuning the schedule rules in a dynamic environment was used.
To use the information which will later be used in the process of a global interaction a production-topology factor (Pt) has been introduced. The Pt factor (3) was used to define the scheduling rule in the lineless simulation.
Through Pt factor the relationship between the production factors and the topology of the shop-floor is expressed. The production-topology factor is adapted for the use in scheduling for different objectives. Factor ad which defines the influence of the topology of the manufacturing shop-floor was defined iteratively.
pt = adlj + (1 - ad )Dj
(3)
where are ad a distance influence coefficient, Ij expression of the production factors, ATC heuristic, Dj a distance influence factor where Dj is defined as:
d - d
D = smax s
j _ dsmax -100
(4)
where are dsmax a maximum distance from the based object to the other production entities and ds a distance from the based object and a possible production entity.
As noted above, a distance influence coefficient (ad) is defined iteratively.
After the global definition of the production schedule (rules) the local fine tuning optimization of the production schedule is performed. For this optimization the GA was proposed. In the proposed GA, the multidimensional search scheme of GA to look for candidate replenishment was taken advantage of. The basic GA setup is as follows:
•	population size: 20 individuals,
•	coding was performed with real numbers,
•	stochastic uniform selection (SUS) was applied,
•	the number of elite children was 2; genetic operators: Those individuals that survive the selection step, undergo the alternation by two
genetic operators, namely, crossover and mutation, uniform crossover was employed,
•	probability for crossover rate was defined as 0.85 and mutation rate as 0.1,
•	termination conditions: we use two rules to stop our GA: firstly, GA terminates after a fixed number of generations (200 generations), and secondly, it stops the evolutionary process when the best-on-hand solution shows no improvement during the last 40 generations.
The GA needed to minimize the objective function which consists of two main objectives. Firstly, to minimize deviation from the due date (5), and secondly, to utilize machine ratio (6).
Ad = - cj| / (oj-100)	(5)
where are cj [s] completion time for order j, d1 [s] due date for order j.
u = ha/hm	(6)
where are ha [s] actual working hours of machine, hm [s] maximal working hours that the machine could do.
2 SIMULATION AND RESULTS
In this paper a novel approach for the design and optimization of the manufacturing system shop floor is presented. For the evaluation of the proposed model two types of the model setup were performed. In the first case it the model was evaluated by simulating production based only on the emergent synthesis method. In this phase behavior was analyzed, within corresponding results, of the proposed model for multi-objective design and adaptable reconfiguration of the manufacturing system shop-floor. In the second phase the proposed model based on the simulation was evaluated by adding one more component (GA) that adds additional robustness in the optimization in manufacturing system design and definition of the scheduling rules. The results obtained from two types of the simulations are presented in the Figs 4 and 5.
In the first simulation setup emergent synthesis was introduced by implementing the so called layered based BMS concept. Scheduling is defined as rule based, introduced by implementation of the ATC heuristic. From the obtained results it can be concluded that: by
utilization of the layered based BMS concept it was possible to obtain relatively stable and robust production shop-floor design which is presented with a production schedule and adaptability of the system to the changes in environment, low deviation from the due date was 18% on average. It can be seen that the system has shown time delay until it has reached an equilibrium. Moreover, it can be observed that the system is sensitive to the changes in the product mix demand. When these kind of changes occur, like in the period from 45th to the 55th day of the simulation time, bottlenecks which cause reduce machine utilization appear in the system. However, after a short period of time the system again falls in the equilibrium.
Due to this behavior of the modeled system genetic algorithms have been introduced as the solution for fine tuning optimization. The GA optimization was introduced in the last stage of the optimization process. After obtaining the initial design and schedule procedure GA was introduced for balancing deviation from the due date. The results presented in Figure 5 show that with the introduction of the GA the modeled system reaches the near optimal result (design and schedule procedure) faster in comparison with the simulation model without the GA. As an after effect it can be noted that machine utilization ratio is higher than in previous simulation.
The main objective for GA fine optimization was defined the deviation from the due date. Therefore, it can be observed that on average 12% was obtained in absolute time deviation from the due date. This is less than the model without GA for 6%. In overall it can be concluded that by introducing GA in the simulation model it produced that modeled system reached the equilibrium state earlier, deviation from the due date (as one of the goals of the optimization) reduced and the utilization of the machines and overall system increased. Taking the utilization of the machines into consideration, it is noticeable that this characteristic was sacrifice for obtaining a lower deviation than the due date. Because the deviation from the due date was defined as the primary objective in multi-objective optimization by the GA.
100	3
1=1 deviation from due date — machine utilization
Fig. 4. The results obtained from simulation model without implantation of GA
3 CONCLUSION
In this paper a new approach for multi-objective design of the manufacturing system shop-floor was presented. The presented approach is based on the Emergent Synthesis methodology, by the introduction of the layered based BMS system as a fundament for system and simulation model design. By the introduction of layered architecture in the simulation model the ability of synthesis between simulation and real manufacturing system is obtained, in other words layered architecture gives us the ability to use highly adaptable features of Biological Manufacturing System. Using the concept of the BMS the emergence in the simulation was provided. To increase the optimization ability the GA was introduced for fine optimization. The simulation model was built in the eM-Plant discreet simulation environment.
The non-existing production system was developed and was analysed to obtain the shop-floor design, layout and scheduling procedure. Finally, it can be concluded that the main advantage of the proposed approach is that the model has the possibility of simultaneously influencing the design and adaptation of the shop-floor layout as well as scheduling rules. These are significant characteristics of the presented approach, because in classical reconfiguration and process planning approaches it is not possible to obtain similar behavior.
4 ACKNOWLEDGEMENTS
The authors would like to acknowledge the support provided by the National CEEPUS Office
100
u
0-0
1 11 21 31 41 51 61 71 81 91 u
days
1=1 deviation from due date ~ — machine utilization
Fig. 5. The results obtained from simulation model with implantation of GA
Croatia and National CEEPUS Office Poland which helped in the research over mobility's in the scope of the CEEPUS project. Also, the research presented in this paper was realized within the project 069-1201787-1754 "Numerical modelling, simulation and optimization in sheet metal forming," financially supported by the Ministry of Science, Education, and Sport of the Republic of Croatia.
5 REFERENCES
[1]	Koren, Y., et al. (1999) Reconfigurable manufacturing systems, Annals of the CIRP, vol. 48, no. 2, p. 527-540.
[2]	Simao, J.M., Stadzisz, P.C., Morel, G.(2006) Manufacturing execution systems for customized production, Journal of Materials Processing Technology, vol. 179, no. 1-3, p. 268-275.
[3]	Car, Z., Mikac, T. (2006) Evolutional approach for solving cell-formation problem in cell manufacturing, Advanced Engineering Informatics, vol. 20, no. 3, p. 227-232.
[4]	Ueda, K. (1994) Biological Manufacturing Systems. Kogyochosakai Pub. Comp. Tokyo. Tokyo, ISBN 1848002661.
[5]	Chena, J.H., Hob, S.Y.A (2005), Novel approach to production planning of flexible manufacturing systems using an efficient multi-objective genetic algorithm, International Journal of Machine Tools & Manufacture, June vol. 45, no. 7-8, p. 949957.
[6]	Govekar, E., Grum, J., Potocnik, P., Starbek, M. (2008), Predicting Order Lead Times,
Strojniški vestnik - Journal of Mechanical Engineering, vol. 54, no. 5, p. 308-321.
[7]	Ueda, K., Markus, A., Monostori, L., Kals, H.J.J., Arai, T. (2001), Emergent Synthesis Methodologies for Manufacturing, Annals of the CIRP, vol. 50, no. 2, p. 535-551.
[8]	Barisic, B., Pepelnjak, T., Math, D.M. (2008), Predicting of the Luders' bands in the processing of TH material in computer environment by means of stochastic modelling. Journal of Materials Processing Technology, vol. 203, no. 1-3, p. 154-165.
[9]	Ueda, K. (2000) Emergent Synthesis, Artificial Intelligence in Engineering, vol. 15, no. 4, p. 319-320.
[10]	Lloyd C M. (1923) Emergent Evolution. London: Williams and Norgate.
[11]	Cariani P. (1991) Emergence and Artificial Life. In: Langton CG, Taylor C, Farmer JD, Rasmussen S, editors, Artificial Life II, Addison-Wesley, p. 767-775.
[12]	Lengton C. Artificial Life. In: Lengton CG, editor. Artificial Life, Addison-Wesley, 1989. p. 1-48.
[13]	Ueda K, et al. (2001) Line-Less Production System Using Self-Organization: A Case Study for BMS, Annals of the CIRP, vol. 50, no. 1, p. 319-322.
[14]	Car, Z., Hatono, I., Ueda, K. (2002) Reconfiguration of manufacturing systems based on virtual BMS, The 35th CIRP International Seminar on Manufacturing Systems, Seoul, May 2002, p. 15.24.
[15]	Dusevic, H., Car, Z., Barišic, B.(2007) Machining center efficiency optimization using artificial intelligence, Annals of DAAAM for 2007 & Proceedings of the 18th International DAAAM Symposium Vienna.
[16]	Marimuthu, S., Ponnambalam, S.G., Jawahar, N. (2008) Evolutionary algorithms for scheduling m-machine flow shop with lot streaming, Robotics and Computer-Integrated Manufacturing, vol. 24, no.1, p. 125-139.
[17]	Kremljak, Z., Polajnar, A., Buchmeister, B. (2005) A Heuristic Model for the Development of Production Capabilities,
Strojniški vestnik - Journal of Mechanical Engineering, vol. 51, no. 11, p. 674-691.
[18]	Holland, J.H. (1992) Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence, The MIT Press.
[19]	Brucker, P, (1998) Scheduling algorithms. Springer, Berlin, ISBN 978-3-540-69515-8.
[20]	Tasic, T., Buchmeister, B., Acko, B. (2007) The Development of Advanced Methods for Scheduling Production Processes, Strojniški vestnik - Journal of Mechanical Engineering, vol. 53, no. 12, p. 844-857.
[21]	Pinedo, M. (2008) Scheduling: Theory, Algorithms and Systems, Prentice Hall, New Jersey, ISBN 954-9526-32-1.