Portfolio of Solving Strategies in CEGAR-based Object Packing and Scheduling for Sequential 3D Printing
2026-03-12 • Artificial Intelligence
Artificial Intelligence
AI summaryⓘ
The authors show how to use the powerful CPUs found in everyday computers and phones to solve a tricky problem of arranging and scheduling objects for 3D printing in sequence. They improved an existing method called CEGAR-SEQ by running it in parallel with different ways of placing objects on the printing plate. This new approach, called Portfolio-CEGAR-SEQ, tries multiple strategies at once and picks the best results, often using fewer printing plates. Their tests demonstrate that this new method works better than the original one.
Sequential 3D printingObject arrangementSchedulingCEGAR (Counterexample Guided Abstraction Refinement)Parallel computingMulti-core CPULinear arithmetic formulaPortfolio algorithmCombinatorial optimization
Authors
Pavel Surynek
Abstract
Computing power that used to be available only in supercomputers decades ago especially their parallelism is currently available in standard personal computer CPUs even in CPUs for mobile telephones. We show how to effectively utilize the computing power of modern multi-core personal computer CPU to solve the complex combinatorial problem of object arrangement and scheduling for sequential 3D printing. We achieved this by parallelizing the existing CEGAR-SEQ algorithm that solves the sequential object arrangement and scheduling by expressing it as a linear arithmetic formula which is then solved by a technique inspired by counterexample guided abstraction refinement (CEGAR). The original CEGAR-SEQ algorithm uses an object arrangement strategy that places objects towards the center of the printing plate. We propose alternative object arrangement strategies such as placing objects towards a corner of the printing plate and scheduling objects according to their height. Our parallelization is done at the high-level where we execute the CEGAR-SEQ algorithm in parallel with a portfolio of object arrangement strategies, an algorithm is called Porfolio-CEGAR-SEQ. Our experimental evaluation indicates that Porfolio-CEGAR-SEQ outperforms the original CEGAR-SEQ. When a batch of objects for multiple printing plates is scheduled, Portfolio-CEGAR-SEQ often uses fewer printing plates than CEGAR-SEQ.