Logic-based Benders decomposition combined with column generation for mobile 3D printer scheduling problem

The principles of sharing become increasingly important for boosting business profitability. In the realm of the sharing economy, 3D printers possess the potential to meet the printing demands of an expanded customer base. This paper investigates a class of mobile 3D printer scheduling problems that consider various aspects such as printer allocation, transportation, and production. 3D printers can be transported using truck between customer locations to efficiently fulfill customer orders and achieve optimal resource allocation. A mixed-integer linear programming model is proposed to describe this problem. After analyzing the characteristics and structure of the model, a logic-based Benders decomposition algorithm framework is designed for solving this problem. To address the specific characteristics of the Benders sub-problem, we define a novel tandem sequence structure and develop a tandem-sequence-based column generation for solving the Benders sub-problem. Three strategies, namely dominance rules, effective upper bounds, and tandem sequence deduplication, are constructed to accelerate the algorithm’s convergence. To evaluate the performance of the proposed algorithm framework and acceleration strategies, a comprehensive set of 320 instances and a real-world set of 14 instances are generated for rigorous testing. The experimental results affirm the effectiveness of these approaches and algorithm. • A Mobile 3D Printer Scheduling Problem with Setup times is proposed. • A three-index model is formulated, and the logic-based Benders decomposition is applied. • A tandem-sequence-based column generation and 3 strategies are developed to solve the sub-problem. • Four instance sets were generated to evaluate the algorithm’s efficiency.