Additive Manufacturing (AM), the technology of rapid prototyping directly from 3D digital models, has made a significant impact on both academia and industry. When facing the growing demand of AM services, AM production planning (AMPP) plays a vital role in reducing makespan and costs for AM service companies. This research focuses on the AMPP problem under the unrelated machine environment and two-dimensional irregular packing constraints such that the makespan can be minimized. Since the two-dimensional irregular packing sub-problems are hard to solve, the efficiency of checking the packing feasibility of batches is the bottleneck of algorithms of AMPP. Therefore, we propose an efficient pixel-based AM packing algorithm (PAMPA) which can tackle irregular packing sub-problems that allow hole filling and free rotation. In PAMPA, parts are placed one by one in a Bottom-Left (BL) way and the rotation angle is determined by a novel angle selection heuristic. Two acceleration techniques are proposed to accelerate separating overlap. The placement sequence is optimized by a biased random-key genetic algorithm (BRKGA). Furthermore, by adopting PAMPA, we introduce a variable neighborhood search (VNS) framework to solve the AMPP. Finally, new instances are generated to conduct experiments. Based on the new instances and instances from ESICUP website, the efficiency of PAMPA is analyzed and verified. The VNS framework shows good performance when solving instances, which illustrates that our PAMPA is beneficial for AMPP. Some interesting insights are also revealed and discussed.
View An Efficient Pixel-based Packing Algorithm for Additive Manufacturing Production Planning