Analysis of irregular three-dimensional packing problems in additive manufacturing: a new taxonomy and dataset

References

• Achillas Charisios, Tzetzis Dimitrios, and Raimondo Maria Olga. 2017. “Alternative Production Strategies Based on the Comparison of Additive and Traditional Manufacturing Technologies.” International Journal of Production Research 55 (12): 3497–3509. doi: 10.1080/00207543.2017.1282645
   Web of Science ®Google Scholar
• Allen, Sam, Edmund K. Burke, Matthew Hyde, and Graham Kendall. 2009. “Evolving Reusable 3d Packing Heuristics with Genetic Programming.” Proceedings of the 11th Annual Conference on Genetic and Evolutionary Computation, Montreal, QC, Canada (931–938). ACM.
   Google Scholar
• Araújo, Luiz Jonatã Pires, Ender Özcan, Jason Atkin, Martin Baumers, Christopher Tuck, and Richard Hague. 2015. “Toward Better Build Volume Packing in Additive Manufacturing: Classification of Existing Problems and Benchmarks.” 26th Annual International Solid Freeform Fabrication Symposium, Austin, TX, USA (401).
   Google Scholar
• Araújo, Luiz Jonatã Pires, Ender Özcan, Jason A. D. Atkin, Martin Baumers, Chris Tuck, and Richard Hague. 2016. “A Part Complexity Measurement Method Supporting 3D Printing.” NIP & Digital Fabrication Conference, Manchester, UK, vol. 2016, no. 1, pp. 329–334. Society for Imaging Science and Technology, 2016.
   Google Scholar
• Araújo, Luiz Jonatã Pires, and Plácido Pinheiro. 2010. “Combining Heuristics Backtracking and Genetic Algorithm to Solve the Container Loading Problem with Weight Distribution.” In P. Novais, M. Calejo, and J. Sedano (Eds.), Soft Computing Models in Industrial and Environmental Applications (pp. 95–102). Guimarães, Portugal: Springer.
   Google Scholar
• Baumers, Martin, Luca Beltrametti, Angelo Gasparre, and Richard Hague. 2017. “Informing Additive Manufacturing Technology Adoption: Total Cost and the Impact of Capacity Utilisation.” International Journal of Production Research 55 (23): 6957–6970. doi: 10.1080/00207543.2017.1334978
   Web of Science ®Google Scholar
• Baumers, Martin, Chris Tuck, Ricky Wildman, Ian Ashcroft, and Richard Hague. 2016. “Shape Complexity and Process Energy Consumption in Electron Beam Melting: A Case of Something for Nothing in Additive Manufacturing?” Journal of Industrial Ecology S1: S157–S167.
   Google Scholar
• Baumers Martin, Tuck Chris, Wildman Ricky, Ashcroft Ian, Rosamond Emma, and Hague Richard. 2013. “Transparency Built-in.” Journal of Industrial Ecology 17 (3): 418–431. doi: 10.1111/j.1530-9290.2012.00512.x
   Web of Science ®Google Scholar
• Beasley John E. 1990. “OR-Library: Distributing Test Problems by Electronic Mail.” Journal of the operational research society 41 (11): 1069–1072. doi: 10.1057/jors.1990.166
   Web of Science ®Google Scholar
• Bischoff E. E. 2006. “Three-dimensional Packing of Items with Limited Load Bearing Strength.” European Journal of Operational Research 168 (3): 952–966. doi: 10.1016/j.ejor.2004.04.037
   Web of Science ®Google Scholar
• Boccia Maurizio, Di Muro Serena, Mosca Francesco, Sforza Antonio, and Sterle Claudio. 2011. “A Fast Heuristic for a Three-dimensional Non-convex Domain Loading Problem.” 4OR 9 (1): 83–101. doi: 10.1007/s10288-010-0133-9
   Web of Science ®Google Scholar
• Burke E. K., Gendreau M., Hyde M., Kendall G., Ochoa G., Özcan E., and Qu R. 2013. “Hyper-heuristics: A Survey of the State of the Art.” Journal of the Operational Research Society 64 (12): 1695–1724. doi: 10.1057/jors.2013.71
   Web of Science ®Google Scholar
• Byun Hong-Seok, and Lee Kwan H. 2005. “Determination of the Optimal Part Orientation in Layered Manufacturing using a Genetic Algorithm.” International Journal of Production Research 43 (13): 2709–2724. doi: 10.1080/00207540500031857
   Web of Science ®Google Scholar
• Canellidis Vassilios, Dedoussis Vassilis, Mantzouratos N., and Sofianopoulou S. 2006. “Pre-processing Methodology for Optimizing Stereolithography Apparatus Build Performance.” Computers in Industry57 (5): 424–436. doi: 10.1016/j.compind.2006.02.004
   Web of Science ®Google Scholar
• Canellidis V., Giannatsis J., and Dedoussis V. 2009. “Genetic-algorithm-based Multi-objective Optimization of the Build Orientation in Stereolithography.” The International Journal of Advanced Manufacturing Technology 45 (7–8): 714–730. doi: 10.1007/s00170-009-2006-y
   Web of Science ®Google Scholar
• Canellidis, V., J. Giannatsis, and V. Dedoussis. 2010. “Effective Nesting of Layer Manufacturing Fabricated Parts using a Genetic Algorithm and a Bottom-left Ray Casting Procedure.” 2010 IEEE International Conference on Industrial Engineering and Engineering Management (IEEM), Macau (pp. 547–551). IEEE.
   Google Scholar
• Canellidis Vassilios, Giannatsis John, and Dedoussis Vassilis. 2013. “Efficient Parts Nesting Schemes for Improving Stereolithography Utilization.” Computer-Aided Design 45 (5): 875–886. doi: 10.1016/j.cad.2012.12.002
   Web of Science ®Google Scholar
• Chernov N, Stoyan Yu, and Romanova Tatiana. 2010. “Mathematical Model and Efficient Algorithms for Object Packing Problem.” Computational Geometry 43 (5): 535–553. doi: 10.1016/j.comgeo.2009.12.003
   Web of Science ®Google Scholar
• Davies A. Paul, and Bischoff Eberhard E. 1999. “Weight Distribution Considerations in Container Loading.” European Journal of Operational Research 114 (3): 509–527. doi: 10.1016/S0377-2217(98)00139-8
   Web of Science ®Google Scholar
• de Mul, Jos. 2016. “Possible Printings: On 3D Printing, Database Ontology, and Open (Meta) Design.” In B. van den Berg, S. van der Hof, and E. Kosta (Eds.), 3D Printing: Legal, Philosophical and Economic Dimensions (pp. 87–98). Springer.
   Google Scholar
• Denyer David, Tranfield David, and Van Aken Joan Ernst. 2008. “Developing Design Propositions through Research Synthesis.” Organization Studies 29 (3): 393–413. doi: 10.1177/0170840607088020
   Web of Science ®Google Scholar
• Dyckhoff Harald. 1990. “A Typology of Cutting and Packing Problems.” European Journal of Operational Research 44 (2): 145–159. doi: 10.1016/0377-2217(90)90350-K
   Web of Science ®Google Scholar
• Egeblad Jens. 2009. “Placement of Two-and Three-dimensional Irregular Shapes for Inertia Moment and Balance.” International Transactions in Operational Research 16 (6): 789–807. doi: 10.1111/j.1475-3995.2009.00703.x
   Web of Science ®Google Scholar
• Egeblad Jens, Nielsen Benny K., and Brazil Marcus. 2009. “Translational Packing of Arbitrary Polytopes.” Computational Geometry 42 (4): 269–288. doi: 10.1016/j.comgeo.2008.06.003
   Web of Science ®Google Scholar
• Egeblad Jens, Nielsen Benny K., and Odgaard Allan. 2007. “Fast Neighborhood Search for Two-and Three-dimensional Nesting Problems.” European Journal of Operational Research 183 (3): 1249–1266. doi: 10.1016/j.ejor.2005.11.063
   Web of Science ®Google Scholar
• Egeblad Jens, and Pisinger David. 2009. “Heuristic Approaches for the Two-and Three-dimensional Knapsack Packing Problem.” Computers & Operations Research 36 (4): 1026–1049. doi: 10.1016/j.cor.2007.12.004
   Web of Science ®Google Scholar
• Eisenbrand, Friedrich, Stefan Funke, Andreas Karrenbauer, Joachim Reichel, and Elmar Schömer. 2005. “Packing a Trunk: Now with a Twist!” Proceedings of the 2005 ACM Symposium on Solid and Physical Modeling, Boston, MA, USA (pp. 197–206): ACM.
   Google Scholar
• Gardan Julien. 2016. “Additive Manufacturing Technologies: State of the Art and Trends.” International Journal of Production Research 54 (10): 3118–3132. doi: 10.1080/00207543.2015.1115909
   Web of Science ®Google Scholar
• Garey Michael R., and Johnson David S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York, NY, USA: W. H. Freeman & Co.
   Google Scholar
• Gell-Mann, Murray. 2002. “What is Complexity?” In A. Quadrio Curzio and M. Fortis (Eds.), Complexity and Industrial Clusters: Dynamics and Models in Theory and Practice, Heidelberg, Germany (pp. 13–24): Springer.
   Google Scholar
• Gibson, Ian, David Rosen, and Brent Stucker. 2014. Additive Manufacturing Technologies: 3D Printing, Rapid Prototyping, and Direct Digital Manufacturing. New York: Springer.
   Google Scholar
• Glaser Barney, and Strauss Anselm. 1967. “Grounded Theory: The Discovery of Grounded Theory.” Sociology The Journal Of The British Sociological Association 12: 27–49.
   Google Scholar
• Gogate A. S., and Pande S. S. 2008. “Intelligent Layout Planning for Rapid Prototyping.” International Journal of Production Research 46 (20): 5607–5631. doi: 10.1080/00207540701277002
   Web of Science ®Google Scholar
• Hague Richard, Campbell I., and Dickens Phill. 2003. “Implications on Design of Rapid Manufacturing.” Proceedings of the Institution of Mechanical Engineers, Part C: Journal of Mechanical Engineering Science 217 (1): 25–30.
   Web of Science ®Google Scholar
• Hague Richard, Mansour Saeed, and Saleh Naguib. 2004. “Material and Design Considerations for Rapid Manufacturing.” International Journal of Production Research 42 (22): 4691–4708. doi: 10.1080/00207840410001733940
   Web of Science ®Google Scholar
• Hemminki J., Leipala T., and Nevalainen O. 1998. “On-line Packing with Boxes of Different Sizes.” International Journal of Production Research 36 (8): 2225–2245. doi: 10.1080/002075498192869
   Web of Science ®Google Scholar
• Hur Sung-Min, Choi Kyung-Hyun, Lee Seok-Hee, and Chang Pok-Keun. 2001. “Determination of Fabricating Orientation and Packing in SLS Process.” Journal of Materials Processing Technology 112 (2): 236–243. doi: 10.1016/S0924-0136(01)00581-7
   Web of Science ®Google Scholar
• Ikonen, Ilkka, William E. Biles, Anup Kumar, John C. Wissel, and Rammohan K. Ragade. 1997. “A Genetic Algorithm for Packing Three-dimensional Non-convex Objects Having Cavities and Holes.” Proceedings of the 7th International Conference on Genetic Algorithms, East Lansing, MI, USA (pp. 591–598): Citeseer.
   Google Scholar
• Iori Manuel, and Martello Silvano. 2010. “Routing Problems with Loading Constraints.” Top 18 (1): 4–27. doi: 10.1007/s11750-010-0144-x
   Web of Science ®Google Scholar
• Jacobs, Paul Francis. 1992. Rapid Prototyping & Manufacturing: Fundamentals of Stereolithography. Dearborn, MI, USA: Society of Manufacturing Engineers.
   Google Scholar
• Joseph, Jiby, Omar Sharif, Ajit Kumar, Saurabh Gadkari, and Aditya Mohan. 2014. “Using Big Data for Machine Learning Analytics in Manufacturing.” Technical report, Tata Consultancy services.
   Google Scholar
• Kagermann Henning, Lukas Wolf-Dieter, and Wahlster Wolfgang. 2011. “Industrie 4.0: Mit dem Internet der Dinge auf dem Weg zur 4. Industriellen Revolution.” VDI nachrichten 13: 11.
   Google Scholar
• Karabulut, Korhan, and Mustafa Murat İnceoğlu. 2004. “A Hybrid Genetic Algorithm for Packing in 3d with Deepest Bottom Left with Fill Method.” International Conference on Advances in Information Systems, Berlin, Heidelberg (pp. 441–450). Springer.
   Google Scholar
• Kotthoff Lars. 2014. “Algorithm Selection for Combinatorial Search Problems: A Survey.” Ai Magazine35 (3): 48–60. doi: 10.1609/aimag.v35i3.2460
   Web of Science ®Google Scholar
• Lawler Eugene L., Lenstra Jan Karel, Kan Alexander H. G. Rinnooy, and Shmoys David B. 1993. “Sequencing and Scheduling: Algorithms and Complexity.” Handbooks in Operations Research and Management Science 4: 445–522. doi: 10.1016/S0927-0507(05)80189-6
   Google Scholar
• Lee Yusin, Fang Chung, Tsou You-Ren, Lu Li-Sin, and Yang Cheng-Tao. 2009. “A Packing Algorithm for Three-dimensional Convex Particles.” Granular Matter 11 (5): 307–315. doi: 10.1007/s10035-009-0133-7
   Web of Science ®Google Scholar
• Liu Xiao, Liu Jia-min, and Cao An-xi, et al. 2015. “HAPE3D-a New Constructive Algorithm for the 3D Irregular Packing Problem.” Frontiers of Information Technology & Electronic Engineering 16 (5): 380–390. doi: 10.1631/FITEE.1400421
   Web of Science ®Google Scholar
• Lutters E., ten Dam D., and Faneker T. 2012. “3D Nesting of Complex Shapes.” Procedia CIRP 3: 26–31. doi: 10.1016/j.procir.2012.07.006
   Google Scholar
• Mani Mahesh, Lane Brandon M., Donmez M. Alkan, Feng Shaw C., and Moylan Shawn P. 2017. “A Review on Measurement Science Needs for Real-time Control of Additive Manufacturing Metal Powder Bed Fusion Processes.” International Journal of Production Research 55 (5): 1400–1418. doi: 10.1080/00207543.2016.1223378
   Web of Science ®Google Scholar
• Nyaluke Adriano, Nasser Bahaa, Leep Herman R., and Parsaei Hamid R. 1996. “Rapid Prototyping Work Space Optimization.” Computers & Industrial Engineering 31 (1–2): 103–106. doi: 10.1016/0360-8352(96)00202-1
   Web of Science ®Google Scholar
• Pisinger David. 2002. “Heuristics for the Container Loading Problem.” European Journal of Operational Research 141 (2): 382–392. doi: 10.1016/S0377-2217(02)00132-7
   Web of Science ®Google Scholar
• Psarra, Sophia, and Tadeusz Grajewski. 2001. “Describing Shape and Shape Complexity using Local Properties.” In J. Peponis and J. Wineman (Eds.), Proceedings 3RD International Space Syntax Symposium, Atlanta, USA (28-1). Citeseer.
   Google Scholar
• Ravindran Ashwin. 2003. “An Octree Based Genetic Algorithm for Three-dimensional Packing of Irregular Parts.” PhD diss., University of Cincinnati.
   Google Scholar
• Ross, Peter. 2005. “Hyper-heuristics.” In E. K. Burke and G. Kendall (Eds.), Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques (pp. 529–556). Kluwer, Boston, MA: Springer.
   Google Scholar
• Ruffo M, and Hague Richard. 2007. “Cost Estimation for Rapid Manufacturing - Simultaneous Production of Mixed Components using Laser Sintering.” Proceedings of the Institution of Mechanical Engineers, Part B: Journal of Engineering Manufacture 221 (11): 1585–1591. doi: 10.1243/09544054JEM894
   Web of Science ®Google Scholar
• Scheithauer G., Stoyan Yu. G., and Romanova T. Ye. 2005. “Mathematical Modeling of Interactions of Primary Geometric 3D Objects.” Cybernetics and Systems Analysis 41 (3): 332–342. doi: 10.1007/s10559-005-0067-y
   Google Scholar
• Schmenner Roger W., and Swink Morgan L. 1998. “On Theory in Operations Management.” Journal of Operations Management 17 (1): 97–113. doi: 10.1016/S0272-6963(98)00028-X
   Google Scholar
• Schwab, Klaus. 2017. The Fourth Industrial Revolution. New York: Crown Business.
   Google Scholar
• Slansky Dick. 2008. “Integrating PLM with the Shop Floor: Validating As-Built to As-Designed.” ARC Advisory Group.
   Google Scholar
• Spies Klaus. 1957. “Die Zwischenformen beim Gesenkschmieden und ihre Herstellung durch Formwalzen.” PhD diss., Springer-Verlag; Düsseldorf.
   Google Scholar
• Stafford D. Shane, and Jackson Thomas L. 2010. “Using Level Sets for Creating Virtual Random Packs of Non-spherical Convex Shapes.” Journal of Computational Physics 229 (9): 3295–3315. doi: 10.1016/j.jcp.2010.01.003
   Web of Science ®Google Scholar
• Stoyan Y. G., Gil M., Pankratov A. V., and Scheithauer G. 2004. “Packing Non-convex Polytopes into a Parallelepiped.” Preprint MATH-NM-06-2004: Technische Universität of Dresden.
   Google Scholar
• Stoyan Y. G., Gil N. I., Scheithauer G., Pankratov A., and Magdalina I. 2005. “Packing of Convex Polytopes into a Parallelepiped.” Optimization 54 (2): 215–235. doi: 10.1080/02331930500050681
   Web of Science ®Google Scholar
• Tavakkoli-Moghaddam Reza, Moslehi G., Vasei M., and Azaron Amir. 2005. “Optimal Scheduling for a Single Machine to Minimize the Sum of Maximum Earliness and Tardiness Considering Idle Insert.” Applied Mathematics and Computation 167 (2): 1430–1450. doi: 10.1016/j.amc.2004.08.022
   Web of Science ®Google Scholar
• Tuck Christopher John, Hague Richard J. M., Ruffo Massimiliano, Ransley Michelle, and Adams P. 2008. “Rapid Manufacturing Facilitated Customization.” International Journal of Computer Integrated Manufacturing 21 (3): 245–258. doi: 10.1080/09511920701216238
   Web of Science ®Google Scholar
• van Aken Joan, Chandrasekaran Aravind, and Halman Joop. 2016. “Conducting and Publishing Design Science Research: Inaugural Essay of the Design Science Department of the Journal of Operations Management.” Journal of Operations Management 47: 1–8. doi: 10.1016/j.jom.2016.06.004
   Web of Science ®Google Scholar
• Verkhoturov Mikhail, Petunin Alexander, Verkhoturova Galina, Danilov Konstantin, and Kurennov Dmitry. 2016. “The 3D Object Packing Problem into a Parallelepiped Container Based on Discrete-Logical Representation.” IFAC-PapersOnLine 49 (12): 1–5. doi: 10.1016/j.ifacol.2016.07.540
   Google Scholar
• Vokurka Robert J., and O'Leary-Kelly Scott W. 2000. “A Review of Empirical Research on Manufacturing Flexibility.” Journal of Operations Management 18 (4): 485–501. doi: 10.1016/S0272-6963(00)00031-0
   Web of Science ®Google Scholar
• Wäscher Gerhard, Haußner Heike, and Schumann Holger. 2007. “An Improved Typology of Cutting and Packing Problems.” European Journal of Operational Research 183 (3): 1109–1130. doi: 10.1016/j.ejor.2005.12.047
   Web of Science ®Google Scholar
• Weller Christian, Kleer Robin, and Piller Frank T. 2015. “Economic Implications of 3D Printing: Market Structure Models in Light of Additive Manufacturing Revisited.” International Journal of Production Economics 164: 43–56. doi: 10.1016/j.ijpe.2015.02.020
   Web of Science ®Google Scholar
• Whetten David A. 1989. “What Constitutes a Theoretical Contribution?.” Academy of Management Review 14 (4): 490–495. doi: 10.5465/amr.1989.4308371
   Web of Science ®Google Scholar
• Wu, Shuohao, Michael Kay, Russell King, Anita Vila-Parrish, and Donald Warsing. 2014. “Multi-objective Optimization of 3D Packing Problem in Additive Manufacturing.” In IIE Annual Conference. Proceedings, (p. 1485). Institute of Industrial and Systems Engineers (IISE).
   Google Scholar