PME I J http://polipapers.upv.es/index.php/IJPME International Journal of Production Management and Engineering https://doi.org/10.4995/ijpme.2020.12173 Received: 2019-08-02 Accepted: 2020-03-26 Genetic Algorithms for the Scheduling in Additive Manufacturing Castillo-Rivera, S.a1, De Antón, J.a2, Del Olmo, R.b, Pajares, J.a3, López-Paredes, A.a4 a INSISOC Research Group (UIC086), University of Valladolid, Paseo del Cauce 59, 47011 Valladolid, Spain. b INSISOC Research Group (UIC086), University of Burgos, C/ Villadiego s/n. 09001, Burgos, Spain. a1 salvador.castillo@uva.es, a2 juan.anton@uva.es b rdelolmo@ubu.es, a3 pajares@insisoc.org, a4 adolfo@insisoc.org Abstract: Genetic Algorithms (GAs) are introduced to tackle the packing problem. The scheduling in Additive Manufacturing (AM) is also dealt with to set up a managed market, called “Lonja3D”. This will enable to determine an alternative tool through the combinatorial auctions, wherein the customers will be able to purchase the products at the best prices from the manufacturers. Moreover, the manufacturers will be able to optimize the production capacity and to decrease the operating costs in each case. Key words: Scheduling, Packing Problem, Genetic Algorithm. 1. Introduction Nowadays, AM has become a relevant technology in some manufacturing environment, due to it can be used in application such as customized production, (Zhang et al., 2014). The fast development is proof that it is a suitable technology for manufacturing components and final products, (Pour et al., 2016). The process that covers, from the model preparation phase to the prototype manufacturing, is complex and this is because of different departments may be involved. The performance of the 3D printing procedure can be summarized in Figure 1. As shown, the first step is to carry out digital modelling, and it consists of building up a 3D model according to customer order. A software package often called CAD (Computer-Aided Design) is used to achieve this (Ikonen et al., 1997). A file should be generated in the adequate format, it is usually taken as “STL” (Standard Triangle Language) and the whole geometrical information should be included to set up the digital model, it is called the exportation. In the slice, the digital model must be converted into a list of 3D print out commands to execute the corresponding code (g-code), the connection allows to provide a list of the printer instructions through the USB port or copying the file in a memory card, which could be directly read by the printer. Once this step is done, the placement of pieces on the build platform and the printing must be carried out; finally, the object/objects should be removed from the printing platform. To cite this article: Castillo-Rivera, S., De Antón, J., Del Olmo, R., Pajares, J., López-Paredes, A. (2020). Genetic Algorithms for the Scheduling in Additive Manufacturing. International Journal of Production Management and Engineering, 8(2), 59-63. https://doi.org/10.4995/ijpme.2020.12173 Figure 1. 3D printing procedure flow chart. Int. J. Prod. Manag. Eng. (2020) 8(2), 59-63Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International 59 mailto:salvador.castillo@uva.es http://creativecommons.org/licenses/by-nc-nd/4.0/ This procedure impacts a company on planning and scheduling as well as the manufacturing process, (Ahsan et al., 2015). Otherwise, the current methods have not shown their suitability to address the requirement for a paradigm shift. Consequently, it is necessary to obtain performances that are done through the implementation of AM, (Pour et al., 2016). AM is being focussed on the manufacturing of many pieces production environment, the planning and scheduling of the corresponding items to be processed on the AM machines. The arrangement of pieces on the build platform is another problem in the AM scheduling, an adequate approach will allow to optimize the build jobs as well as the machine utilization. Highly uncertain demand can cause a revision of production planning, being one of the main cost drivers because of adverse effects on inventory and labour levels (Demirel et at. 2018). Scheduling of 3D printers presents new problems linked to its production capability and it must cope to packing problem, which is presented as the numbers of pieces are put on the corresponding build platform surfaces. The planning of parts to be processed on 3D printers performs a fundamental role in reducing operational costs; this should provide a less price and increase the profitability of the companies. As a consequence, LONJA3D is designed to purchase products made with 3D printing, which facilitates the organization and coordination of collaborative between the customers that will receive the bids from the manufacturers of 3D printing services. This market will allow customers to get better prices from the manufacturers. On the other hand, these last ones can optimize their installed production capacity and they can decrease operating costs in each case according to the technology. Modern manufacturing environment has been featured by customer demands, raised product variety, demand for limited production cycles, etc. All of them highlight the relevance of adopting new technologies and systems to deal with this. Different algorithms have been mainly used for planning and scheduling in AM. Another feature that presents an impact on scheduling is the packing problem. One of the first challenges that “Lonja 3D” has to face, is to figure out a suitable arrangement of multiple items in different build platforms, minimizing the empty area. This presents a relevant interest due to it entails the reduction of the production costs. The complexity of the problem must be dealt with, taking into account the geometry of the objects and using a successful method of resolution. GAs are one of the most known algorithms based on the principles of artificial intelligence that have found out its use in different branches of science. GAs can be used to solve the two or three-dimensional packing problems. This work presents the preliminary results of an ongoing study. A theoretical framework of AM and GA has been done, to shed light on the challenging that the 3D printing industry must face. It has been carried out because the authors are currently working in the design of a managed market called “Lonja3D”. It should be used to purchase products made using 3D printing. In this market, the coordination and organization of offers will be eased between the customers that will receive the bids from the providers of 3D printing services. This “Lonja3D” or market will allow customers to obtain better prices from the manufacturers. In addition to this, the manufacturers can optimize their installed production capacity and they can decrease operating costs in each case according to the technology. The work is organized as follows: Section 2 presents the theoretical framework. Section 3 deals with additive manufacturing and genetic algorithms. Section 4 summarizes the results and conclusions. 2. Theoretical Framework Process planning and scheduling are two of the most important functions in manufacturing systems that have shown a large influence on product design along with the considerations of timing aspects and technological. These are taken into account as two different functions in a manufacturing environment. However, a critical problem has been raised with the potential action of alternative machines, setups and processes for producing a specific part in a manufacturing shop has got. If scheduling and process planning are implemented independently, the schedule that is derived lacks flexibility and adaptability. Consequently, for obtaining realistic and effective timetables both functions should be considered, (Kim and Egbelu, 1999). Alternative plans allow allocation of tasks to other machines with further flexibility and it decreased the possibility of conflict between a job and a machine. Int. J. Prod. Manag. Eng. (2020) 8(2), 59-63 Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International Castillo-Rivera et al. 60 http://creativecommons.org/licenses/by-nc-nd/4.0/ The integration of the process planning and scheduling come from the class of most tricky combinatorial problems and it needs high efficient approaches for finding optimal solutions. Therefore, its integration should be enhanced the efficiency as well as the performance of manufacturing systems (Milošević et al., 2016). The integrating process planning and scheduling functions is a change of model in most AM organizations. The alternative operations for a specific job explained that determined arrangements lead to an advantage in a manufacturing environment (Wilhelm and Shin, 1985; Xirouchakis et al., 1998). Alternative layouts are able to be used for: a) to determine disruption problems such as machine overloads and machine breakdowns, among others. b) Reduction of process inventory. c) Rising equipment utilization. Li et al. (2017) presented a mathematical model to formulate the production planning in AM problem. To figure out the optimum allocation of several pieces on a set of machines with different specifications such as unit time cost and processing speed, among others. The average production cost per volume of material was minimized. Only one material was taken into account, nesting problems, and the due dates for fulfilling orders were not considered. Two heuristic procedures were established called “best- fit” and “adapted best-fit” rules. A computational study was done to assess the performance of the heuristics. Furthermore, the necessity of developing specific planning and scheduling was proven for AM processes. Chergui et al. (2018) presented the planning, nesting and scheduling problem in AM to achieve the orders got from different customers by due dates. A mathematical formulation of the problem was proposed and a heuristic approach was also derived using Python to work out it. Experimental assessments were carried out, these showed the need for developing suitable AM planning and scheduling methods for satisfying the technical and the organizational requirements of AM. The scheduling and freedom of design are often limited due to the printing complex geometries are presented in AM. The packing problem is also presented in mechanical design and manufacture, among others. Araújo et al. (2015) introduced a classification of AM build as well as a summary of existing benchmarks for the study of these problems. Furthermore, it is discussed benchmarks to encourage research toward effective and efficient AM to build volume packing, which should be integrated into AM manufacturing planning methodologies. Canellidis et al. (2006) described a pre-processing methodology that makes automatic the procedure of finding suitable fabrication orientations and packing arrangements. The methodology consisted of two separate stages as the orientation and the packing stage. In the beginning, each part was adequately oriented to obtain better surface quality and minimal projection area, lower build time, etc. The second stage took into account the projections of the parts on the fabrication platform. A GA along with a new improved placement rule was used to lead the associated 2D bin-packing problem. Two sets of studies were employed to prove the performance of the approach, which involved simple nearly orthogonal-shaped parts as well as objects/parts. Modern GAs have shown to be trustworthy for finding optimal process schedules. Lawrynowicz (2011) provided a survey of developments in building GA for advanced scheduling. A new approach was proposed to the distributed scheduling in industrial clusters using a modified GA. Milošević et al. (2016) presented the state of the art review of GAs for optimization of process planning, scheduling and their corresponding integration. Hybrid approaches and different modifications were briefly studied. Genetic components and strategies were also presented with some sample parts, which are frequently taken into account as testing GA performances. The capability of producing pieces with different geometries at the same time is a challenge that is presented in scheduling. As a consequence, Fera et al. (2018) provided a mathematical model for an AM/SLM (Selective Laser Melting) machine scheduling. The complexity of the model was NP- hard and the likely solutions should be figured out by metaheuristic algorithms such as GAs. These solve sequential optimization problems by handling vectors. The proposed algorithms were assessed on a case composed of a thirty part number production plan with an elevated variability and complexity. 3. Additive Manufacturing and Genetic Algorithms Most of the packing problems found in the specialist literature are two dimensional. According to the items to be placed, two main groups can be distinguished, those which present regular or irregular shapes. Regular figures have shapes that are established by a few parameters such as rectangles, circles. On the other hand, the term irregular is applied to Int. J. Prod. Manag. Eng. (2020) 8(2), 59-63Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International Genetic Algorithms for the Scheduling in Additive Manufacturing 61 http://creativecommons.org/licenses/by-nc-nd/4.0/ asymmetrical concave and convex shapes. It must be optimized the production capacity and the reduction of operating costs, establishing a production rate with the least space on the build platform, (Hopper and Turton, 1997). A first approach can be done through a layout space which the size could be determined i.e., rectangle packing problem. This scenario presents common features with a standard problem of how it can be the knapsack. The rectangles must be located into the layout of space and required to satisfy the constraints to derive certain optimal standards. A GA can be implemented according to the requirements established by the authors to derive suitable outcomes for “Lonja 3D”. Hence, it is considered a set of objects {1,...,n} each one j is characterized by a weight function pj and a value vj, being these positive integer numbers. The surface of the build platform should contain sets of objects which surface should not exceed p0 units, and besides the total number of them should be maximum. It should be assumed that pj ≤ p0 ∀j and ∑ n j=1pj > p0. The mathematical model should be set up as a variable xj associated with each set of objects j. xj = 1 if the set of objects j should be inserted or xj = 0, otherwise. As a result, an integer linear programming can be derived to implement the GA: ax xm ∑ n j=1 vj j (1) Subject: x ≤p∑ n j=1 pj j 0 (2) 0 ≤ xj ≤ 1; ∀j ∈ 1, …, n xj ∈ Z; ∀j ∈ 1, …, n The evolution process starts with the generation of an initial random population. The fitness of each member of the population is computed and probabilities are assigned to each individual. The reproducing population is formed (selection) by drawing with replacement to sample where each individual has a probability of surviving. A new population is generated from the reproducing population using crossover and mutation operators. After this, the algorithm returns to the fitness evaluation step. When convergence criteria are met the evolution stops, see Figure 2. 4. Results and Conclusions 3D printing shows characteristics that other industries have not displayed. 3-D printing allows small quantities of customized lots to be produced at relatively low costs, which will significantly decrease the advantages of producing small good sizes in low-wage countries, through reduced need for workers (Berman, 2012). Based on the costs supplied by the different manufacturers for the printing of parts, “LONJA3D” will develop at each moment the best feasible offers with the demands of the users. Allowing to focus the order to the most efficient manufacturer for every technology. 3D printing manufacturing presents some restrictions as the reduced surface of the build platform and printing time, among others. This can be traceable throughout the several approaches as GAs that enables to study for example the packaging problem. The geometry and the dimensions of the items implicated in the arrangement method enable to classify these problems. A GA has been presented to establish an adequate stage for setting up “LONJA 3D”. The work provides suitable information for 3D printing industry scheduling. To expand the work, combinatorial auctions will be used to optimize the advantageous participation of the productive capacity of the manufacturers to the proper demand at each moment, also raising the competition between all the producers and improving the profits for the customers. These types of auctions have been successfully employed in fields as Federal Communications Commission’s radio spectrum licenses. Figure 2. Flow chart of the genetic algorithm. Int. J. Prod. Manag. Eng. (2020) 8(2), 59-63 Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International Castillo-Rivera et al. 62 http://creativecommons.org/licenses/by-nc-nd/4.0/ Acknowledgements This research has been partially financed by the project: “Lonja de Impresión 3D para la Industria 4.0 y la Empresa Digital (LONJA3D)” funded by the Regional Government of Castile and Leon and the European Regional Development Fund (ERDF, FEDER) with grant VA049P17. 5 References Ahsan, A., Habib, A., Khoda, B. (2015). Resource based process planning for additive manufacturing. Computer-Aided Design, 69, 112- 125. https://doi.org/10.1016/j.cad.2015.03.006 Araújo, L., Özcan, E., Atkin, J., Baumers, M., Tuck, C., Hague, R. (2015). Toward better build volume packing in additive manufacturing: classification of existing problems and benchmarks. 26th Annual International Solid Freeform Fabrication Symposium - an Additive Manufacturing Conference, 401-410. Berman, B. (2012). 3-D printing: The new industrial revolution. Business Horizons, 55: 155-162. https://doi.org/10.1016/j.bushor.2011.11.003 Canellidis, V., Dedoussis, V., Mantzouratos, N., Sofianopoulou, S. (2006). Preprocessing methodology for optimizing stereolithography apparatus build performance. Computers in Industry, 57, 424-436. https://doi.org/10.1016/j.compind.2006.02.004 Chergui, A., Hadj-Hamoub, K., Vignata, F. (2018). Production scheduling and nesting in additive manufacturing. Computers & Industrial Engineering, 126, 292-301. https://doi.org/10.1016/j.cie.2018.09.048 Demirel, E., Özelkan, E.C., Lim, C. (2018). Aggregate planning with flexibility requirements profile. International Journal of Production Economics, 202, 45-58. https://doi.org/10.1016/j.ijpe.2018.05.001 Fera, M., Fruggiero, F., Lambiase, A., Macchiaroli, R., Todisco, V. (2018). A modified genetic algorithm for time and cost optimization of an additive manufacturing single-machine scheduling. International Journal of Industrial Engineering Computations, 9, 423-438. https://doi.org/10.5267/j.ijiec.2018.1.001 Hopper, E., Turton, B. (1997). Application of genetic algorithms to packing problems - A Review. Proceedings of the 2nd On- line World Conference on Soft Computing in Engineering Design and Manufacturing, Springer Verlag, London, 279-288. https://doi.org/10.1007/978-1-4471-0427-8_30 Ikonen, I., Biles, W.E., Kumar, A., Wissel, J.C., Ragade, R.K. (1997). A genetic algorithm for packing three-dimensional non-convex objects having cavities and holes. ICGA, 591-598. Kim, K.H., Egbelu, P.J. (1999). Scheduling in a production environment with multiple process plans per job. International Journal of Production Research, 37, 2725-2753. https://doi.org/10.1080/002075499190491 Lawrynowicz, A. (2011). Genetic algorithms for solving scheduling problems in manufacturing systems. Foundations of Management, 3(2), 7-26. https://doi.org/10.2478/v10238-012-0039-2 Li, Q., Kucukkoc, I., Zhang, D. (2017). Production planning in additive manufacturing and 3D printing. Computers and Operations Research, 83, 157-172. https://doi.org/10.1016/j.cor.2017.01.013 Milošević, M., Lukić, D., Đurđev, M., Vukman, J., Antić, A. (2016). Genetic Algorithms in Integrated Process Planning and Scheduling–A State of The Art Review. Proceedings in Manufacturing Systems, 11(2), 83-88. Pour, M.A., Zanardini, M., Bacchetti, A., Zanoni, S. (2016). Additive manufacturing impacts on productions and logistics systems. IFAC, 49(12), 1679-1684. https://doi.org/10.1016/j.ifacol.2016.07.822 Wilhelm, W.E., Shin, H.M. (1985). Effectiveness of Alternate Operations in a Flexible Manufacturing System. International Journal of Production Research, 23(1), 65-79. https://doi.org/10.1080/00207548508904691 Xirouchakis, P., Kiritsis, D., Persson, J.G. (1998). A Petri net Technique for Process Planning Cost Estimation. Annals of the CIRP, 47(1), 427-430. https://doi.org/10.1016/S0007-8506(07)62867-4 Zhang, Y., Bernard, A., Gupta, R.K., Harik, R. (2014). Evaluating the design for additive manufacturing: a process planning perspective. Procedia CIRP, 21, 144-150. https://doi.org/10.1016/j.procir.2014.03.179 Int. J. Prod. Manag. Eng. (2020) 8(2), 59-63Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International Genetic Algorithms for the Scheduling in Additive Manufacturing 63 https://doi.org/10.1016/j.cad.2015.03.006 https://doi.org/10.1016/j.bushor.2011.11.003 https://doi.org/10.1016/j.compind.2006.02.004 https://doi.org/10.1016/j.cie.2018.09.048 https://doi.org/10.1016/j.ijpe.2018.05.001 https://doi.org/10.5267/j.ijiec.2018.1.001 https://doi.org/10.1007/978-1-4471-0427-8_30 https://doi.org/10.1080/002075499190491 https://doi.org/10.2478/v10238-012-0039-2 https://doi.org/10.1016/j.cor.2017.01.013 https://doi.org/10.1016/j.ifacol.2016.07.822 https://doi.org/10.1080/00207548508904691 https://doi.org/10.1016/S0007-8506(07)62867-4 https://doi.org/10.1016/j.procir.2014.03.179 http://creativecommons.org/licenses/by-nc-nd/4.0/