Title
Benders decompositions for order acceptance and scheduling in additive manufacturing
Authors
[ 1 ] Instytut Informatyki, Wydział Informatyki i Telekomunikacji, Politechnika Poznańska | [ P ] employee
Scientific discipline (Law 2.0)
Year of publication
2025
Published in
Article type
scientific article
Publication language
english
Keywords
Abstract
EN We study an order acceptance and parallel machine scheduling problem appearing in additive manufacturing (AM) considering two-dimensional packing with part rotation. Three joint decisions, including order acceptance, build formation and schedule construction, are made to maximize the revenue of accepted orders minus a weighted makespan, thereby capturing the trade-off between profitability and production efficiency. First, two mixed integer programming models (MIP) are formulated to optimize the three mentioned decisions simultaneously. Then, due to the specific structure of the problem, we propose a general logic-based Benders decomposition (LBBD) approach and a nested logic-based Benders decomposition (NLBBD) approach with various Benders cuts and search strategies. Finally, we undertake a comprehensive computational study to validate the effectiveness of all the proposed approaches. The computational results show that NLBBD achieves 50% more optimal solutions than MIP models implemented in Gurobi and 35% more than LBBD for small-sized instances. For large-sized instances, NLBBD still achieves better solutions with smaller gaps compared to Gurobi and LBBD. Further, numerical experiments confirm the effectiveness of the designed additional cuts and search strategies applied in Benders decompositions.
Date of online publication
04.10.2025
Ministry points / journal
140
System created by Poznań University of Technology
and Poznan Supercomputing and Networking Center
Log in through eKonto to add to SIS