Portfolio of Solving Strategies in CEGAR-based Object Packing and Scheduling for Sequential 3D Printing

3D printing technology has rapidly evolved in recent years, becoming an integral part of manufacturing. Traditional manufacturing processes often rely on subtractive manufacturing, whereas 3D printing constructs objects by adding material layer by layer. This additive manufacturing approach not only enhances production efficiency but also reduces material waste. However, 3D printing faces challenges, particularly in object packing and scheduling. To improve printing efficiency, researchers have proposed various algorithms and strategies, with the CEGAR-SEQ algorithm being a commonly used method. CEGAR-SEQ translates the object packing problem into a linear arithmetic formula and solves it using counterexample guided abstraction refinement. However, the traditional CEGAR-SEQ algorithm is inefficient when handling large object sets and fails to fully utilize the computational power of modern multi-core CPUs.

The object packing and scheduling problem in 3D printing is a complex combinatorial optimization problem. The core challenge is to efficiently pack and schedule multiple objects within the limited space of a printing plate to maximize resource utilization and minimize printing time. Traditional object arrangement strategies often place objects towards the center of the printing plate to take advantage of uniform heating. However, this strategy can lead to resource waste when dealing with complex object sets. Moreover, as 3D printing technology advances, modern printers' heated bed designs have eliminated heating irregularities, necessitating the exploration of new object arrangement strategies.

The core innovation of the Porfolio-CEGAR-SEQ algorithm lies in its parallelization design with multi-strategy combinations. First, the algorithm significantly enhances solving efficiency by introducing various object arrangement strategy combinations. Second, Porfolio-CEGAR-SEQ leverages the computational power of modern multi-core CPUs by executing different strategy combinations in parallel to quickly find the optimal solution. Additionally, the algorithm introduces new strategies for object scheduling, such as scheduling based on object height, further improving resource utilization. Compared to the traditional CEGAR-SEQ algorithm, Porfolio-CEGAR-SEQ shows significant improvements in solving efficiency and resource utilization.

The implementation of the Porfolio-CEGAR-SEQ algorithm includes several key steps:

• �� First, the object packing and scheduling problem is translated into a linear arithmetic formula and solved using counterexample guided abstraction refinement (CEGAR).

• �� Then, various object arrangement strategy combinations are introduced, including arranging objects towards the center, corners, or scheduling based on object height.

• �� Next, the computational power of modern multi-core CPUs is leveraged by executing different strategy combinations in parallel to quickly find the optimal solution.

• �� Finally, the effectiveness of the algorithm is validated through experiments, comparing solving efficiency and resource utilization under different strategy combinations.

The experimental design includes testing the performance of the Porfolio-CEGAR-SEQ algorithm under different 3D printing tasks. The object set used in the experiments includes complex 3D printable objects with up to 64 items, testing solving efficiency and resource utilization under different strategy combinations. The experiments also compare the performance of Porfolio-CEGAR-SEQ with the traditional CEGAR-SEQ algorithm in multi-printing plate scheduling, focusing on the number of printing plates used and solving time. Additionally, performance comparisons under different object arrangement strategy combinations are conducted to verify the algorithm's flexibility and adaptability.

The experimental results indicate that Porfolio-CEGAR-SEQ often uses fewer printing plates when scheduling objects for multiple plates, demonstrating a significant improvement in resource utilization. Additionally, Porfolio-CEGAR-SEQ can quickly find better solutions when handling complex 3D printing tasks with up to 64 objects. Under different object arrangement strategy combinations, Porfolio-CEGAR-SEQ demonstrates flexibility and adaptability, selecting the optimal solution based on the chosen strategy.

The Porfolio-CEGAR-SEQ algorithm has broad applications in the field of 3D printing. First, the algorithm can be used to improve printing efficiency in large-scale production, reducing resource waste. Second, in the printing of complex objects, Porfolio-CEGAR-SEQ can optimize object packing and scheduling, reducing the number of printing plates used. Additionally, the algorithm can be applied to other types of 3D printers, such as stereolithography (SLA) and selective laser sintering (SLS) printers, to enhance printing efficiency and resource utilization.

Despite the significant improvements in solving efficiency and resource utilization demonstrated by the Porfolio-CEGAR-SEQ algorithm, it may face computational resource limitations when handling extremely large object sets, especially with an excessive number of strategy combinations. Additionally, the algorithm may fail to find optimal solutions under certain specific object arrangement strategies, particularly when there are significant differences in object height. On systems with lower hardware configurations, the parallelization advantage of the algorithm may not be fully realized. Future research directions include further optimizing the strategy combination selection algorithm to improve adaptability to different printing tasks.