Ανάπτυξη υπολογιστικών εργαλείων για την βελτιστοποίηση των διαδικασιών στρωματικής κατασκευής

Abstract

Additive Fabrication (AF) or Additive Manufacturing is a relatively new group of manufacturing technologies, methods and processes that produce parts through material addition. Some of the most widely used AF technologies are Stereolithography (SL), Fused Deposition Modelling (FDM), Selective Laser Sintering (SLS), 3D printing (3DP), Multi-jet Modelling (MJM) and Laminated Object Manufacturing (LOM). Depending on the technology, several materials (photopolymers, metals, ceramics, paper etc.) in various forms (liquid, powder, filaments or sheets) are processed usually in the form of thin layers that are added consecutively, usually in the ‘bottom-top’ direction, hence the term ‘building’ is very often used instead of ‘fabricating’. The geometry of the layers is computed directly from the 3D digital part model, which is an essential prerequisite for the process. The AF process usually consists of three distinct phases, the pre-fabrication (pre-processing) phase, the fabrication (‘building’) phase and the post-fabrication (post-processing) phase. In the pre-fabrication phase the AF machine operator selects the appropriate fabrication (build) parameters and performs several data-preparation tasks, such as the computation of the layers geometry (slicing). The actual fabrication of the part by the AF system takes place during the second phase, the ‘building’ phase, and it is performed automatically by the AF machine. Finally in the post-fabrication phase, several usually necessary post-processing tasks such as post-curing of materials, part infiltration, cleaning and surface polishing are performed. Compared to the established manufacturing methods (cutting, casting and forming processes), no special tooling or fixtures are required in AF and the required process planning is relatively simpler; hence manufacturing time and cost are significantly lower, especially for parts of complex or freeform geometry. The majority of AF technologies is currently employed in the production of models and prototypes for concept evaluation and functional testing of new products, thus they are often referred to as Rapid Prototyping technologies. However, as AF technologies continuously improve in terms of accuracy and range of raw materials they are increasingly employed in the actual manufacturing process. Thus, the field of Rapid Manufacturing, i.e. the application of AF technologies for the direct fabrication of final products instead of simple models/prototypes, is a technological field that is continuously gaining the attention from both researchers and professionals in the industrial and manufacturing sector. However, this shift of focus in the application of AF technologies puts also a new emphasis on the study of some of the process planning problems and issues that are related with the cost efficient use of AF systems and the quality of their products. Among the most crucial process planning problems are: (i) the selection of fabrication orientation and parameters, and (ii) the batch selection/planning or “packing” problem, at which the selection and placement of various different parts inside the machine workspace is considered. These two problems are quite interrelated since the selection of a specific orientation for a given part directly affects the set of possible solutions for the packing problem. As such, the primary research goals of the present thesis is to develop and investigate alternative optimization procedures for the AF process planning, as well as to develop robust computational tools for automating the decisions need to be taken during the phases of building parameters selection and batch planning. The computational tools developed are applicable for supporting Stereolithography, as it represent a large percentage of AF installed worldwide, while the methodologies used are also applicable in every AF technology that due to technical or quality reasons exclude the fabrication of a part on top of another. The present thesis may be divided in three interrelated sections. In the first section an attempt is made to analyze the the fabrication procedure of a Stereolithography apparatus as well as to identify the main decision criteria that can be utilized later during the building parameters selection phase. As a result two building parameters have been identified to affect the cost and the quality of a product being fabricated by Stereolithography the most, that is (i) fabrication orientation and (ii) layer thickness. Thus, a analytical framework has been developed in order to be utilized in the assessment of the quality and the cost of a product for any given fabrication orientation and layer thickness. More specifically the cost of a part may be expressed as a equation of the time spend, primary during the actually building phase and secondary during the pre and post processing phase. For the assessment of a product fabrication time an analytical model is being utilized based only on the multi-facet CAD representation of the product known as STL file. In order to define the quality of a Stereolithography product the process induced errors that cause loss of part quality with respect to the original CAD model have to be identified and measured. Thus, the relation between six different process induced errors and the quality of the final product is investigated. As a final point to the first section of this thesis a thorough description of the two major optimization meta-heuristic methods, i.e. Genetic Algorithms & Simulated Annealing, utilized later has been attempted. Genetic Algorithms (GA) are a particular class of Evolutionary Computation algorithms based on the principles of natural selection and survival of the fittest. GA are considered to be suitable for large scale optimization problems, especially those where the sought global extremum is hidden among many, poor, local extrema. In GA methodology a population composed of many individuals, represented by their chromosomes, is allowed to evolve under appropriately specified selection rules to a state that maximizes the overall “fitness”. Simulated Annealing algorithm is a generalization of the Monte Carlo method that it was motivated by an analogy to the thermodynamics of annealing in solids. In an annealing process, material is being heated to a temperature that permits many molecules to move freely with respect to each other. Then it is cooled in a slow manner, until the material freezes into a crystal, which is completely ordered, and thus the system is at the state of minimum energy. Noting that the target in a combinatorial optimization problem is to find a near optimal solution or else the “minimum energy state of the problem”, simulated annealing technique use an analogous cooling operation for transforming a poor, unordered solution into an ordered, desirable solution, so as to optimize the objective function. The second section of this thesis focuses on the optimization of the decisions need to be taken during the selection of the build orientation for a given product. In AF the part is fabricated through the successive formation and addition of layers usually in the “bottom-top” direction. Due to the layering character of the various AF processes the direction of the layer addition, as defined by the selection of the orientation of the part with respect to the platform of machine, influences significantly the part fabrication cost, time and quality. Since the orientation selection is by definition a multi-criteria optimization problem, the optimum orientation is usually the one that gives the best compromise between the often conflicting objectives of minimizing cost/time on one hand and maximizing quality on the other. In the context of orientation selection, fabrication time and cost are quite interrelated since the basic orientation dependent cost factor is build time. The problem of finding the optimum fabrication orientation entails the identification of all the parameters affecting the optimality of a given orientation as well as the development of robust optimization procedures that will be able to evolve towards solutions that reflect the “fabrication preferences” of the decision maker. According to the proposed model the evaluation of the fabrication orientation optimality depends on four critical orientation dependent factors, namely, the build time (cost factor), the support removal time (cost factor), the stairstepping effect (quality factor) and the support structure (quality factor). In order to evaluate the intensity of the effect that those two quality factors have on the final product the average surface roughness is being utilized as a “quality measure”. The importance of surface roughness as a means of evaluating the quality of a part is, perhaps, highlighted in the case of casting patterns for secondary processes, as it affects not only the appearance and functionality of the part but also the life and the associated moulds and tools and, consequently, the cost of the casting process. Finally, for the evaluation of the average surface roughness of a part built in a given orientation, an analytic prediction model is employed. The prediction model entails profiles of surface roughness that have been measured on specifically prepared SL test parts of geometry. As the orientation problem is of multiobjective nature, it is characterized by the fact that no unique solution exists but a set of mathematically equally good solutions can be identified. These solutions are known as nondominated, efficient, noninferior or Pareto optimal solutions. Thus, the optimization methods selected in this section are able to cope with the multicriteria nature of the problem providing solutions that are Pareto optimal. Moreover, in order to provide flexibility to the end user of the tools developed, two different approaches concerning the involvement of the decision maker in the form of specifying preference information have been followed. The first method entail the utilization of a Weighted Fitness Function driven by a Genetic Algorithm. This approach is considered “a priori” optimization method, where the decision maker first articulates its preference information and aspirations and then the solution process tries to find a Pareto optimal solution satisfying them as well as possible. This “a priori” method has the advantage that it provides only one final solution, however, assumes that the chosen criteria weight values accurately capture the operator’s preferences, an assumption that is not easily met in reality without significant experience and attention in the weight selection. The second method utilize the Non-dominated Sorting Genetic Algorithm (NSGA II) which is considered to be “a posteriori” method, where a representation of the set of Pareto optimal solutions is first generated and then the decision maker is supposed to select the most preferred one among them. For the implementation of the above described GAs the commercial package Matlab R2008a has been used and several test cases were computed in order to investigate the performance and check the operational characteristics of the system/computer code developed. The results of the test cases revealed that both methodologies performed quite satisfying. In particular the Weighted method seemed to favor solutions that lies to the convex part of the Pareto front, an effect that is known to appeared when this method is applied to non-convex problems. On the other hand, the NSGA II has been able to create a satisfying estimation of the Pareto front in relatively short time. The third section of this thesis focuses on the batch selection/planning problem, at which the optimal selection and placement of various different parts inside the machine workspace is considered so as to maximize the utilization of the machine workspace and operational time. Specifically, at the pre-processing phase the parts to be fabricated must be placed (packed) digitally on the fabrication platform as densely as possible so to achieve the maximum possible space utilization. The size and shape variety of the parts that can be fabricated by AF technologies makes the task of nesting them optimally on the fabrication platform extremely challenging. Moreover, the complexity of the nesting task increases considering the infinite feasible placement positions for each part. As a result, all the computational tools developed entail procedures, e.g. a heuristic algorithms, to guide effectively the search in the solution space as well as procedures to ensure the feasibility of the solution proposed. The later is the most computational intensive part and it usually consists of a geometry data handling procedure and a placement rule. The geometrical interaction between the parts being packed is limited to the x-y plane only, since packing solutions - fabrication layouts where some parts are build on top of others are not allowed. Thus, the original 3-D packing problem is simplified by one dimension, by projecting each one of the parts on the build platform (x-y plane) and packing their projections instead of the actual parts themselves. The parts are being projected on the build platform after they have been appropriately oriented as stated earlier. The solution space, even in the case of 2D nesting, is large. Moreover, the projections of the parts may be freely rotated along the building direction (i.e. the z-axis) under any angle, as this kind of rotation does not affect the original fabrication orientation of the 3D models, which has been already adopted. Thus, appropriate care must be taken in every step of the packing procedures to alleviate the computational effort needed. The first action to be taken is to reduce the number of points needed to describe the geometry of a part projection. Thus, each projection is being offset by a suitable threshold and then the number of points of the projection curve are reduced utilizing the Douglas–Peucker algorithm. Then, efficient placement rules are needed to be established in order to perform the actual packing. Three different placement rules were established in order to identify the one that is more suitable for the current problem. The first placement rule is a two stage procedure that utilize Direct Trigonometry methods which deal with the geometry complexity directly utilizing a vector representation for each part. Unlike other placement methods, the feasibility of a placement is implied by direct trigonometric techniques, which are able for collision detection. These techniques efficiently deal with the irregular nature of shapes in order to produce high quality solutions but they are very computational expensive. The second placement rule utilize the No-Fit polygon technique that has become an increasingly popular option for conducting intersection tests between pairs of polygons. It can represent all the arrangements that two arbitrary polygons may take so that they not only touch but also so that they cannot be moved closer together without intersecting one another. Although the no-fit polygon is an excellent tool for making intersection tests between pairs of polygons, it has not been widely applied due to the difficulties in developing a robust approach capable of dealing with the large number of degenerated cases, which is a direct consequence of the generality of the shapes considered. Though, a robust method has been developed that can deal with any geometrical complexity conforming with the shape freedom requirements of the current problem. The third placement rule is a two stage stage hybrid procedure utilizing both Direct Trigonometry methods and the No-Fit polygon technique in order to exploit the advantages of both the approaches. The nesting problem is NP complete problem which makes it intractable, as far as computational time for obtaining the global optimum is concerned, simply because the associated solution tree grows exponentially with the size of the problem. The classical (exact) optimization algorithms are, therefore, inefficient for such problems and one has to resort to heuristic approaches. Thus, heuristic approaches have been selected to guide the placement rules developed which are capable of giving ‘acceptably good’, solutions, i.e. solutions close to the global optimum, with very low computational effort. The stochastic optimization heuristics selected are Simulated Annealing and GA. The implementation of the above described packing procedures has also been conducted with the commercial package Matlab and several packing benchmarks as well as test cases concerning real-world’ objects/parts that have been fabricated in the context of various projects undertaken by the Center for Product Development and Rapid Prototyping of the University of Piraeus, during the past years were computed in order to investigate the performance and check the operational characteristics of the procedures developed. The results of the test cases revealed that the methodology that is most suitable for the current problem is the hybrid method as it provides the denser packing arrangements within the sorter period of time disregarding the optimization heuristic used.