Don’t let your breaks go to waste: The waste-performance-tradeoff-problem

In e-commerce warehouses, automated packaging machines are utilized in the final processing stages to efficiently pack customer orders. In this context, decision-makers in planning and procurement must balance conflicting objectives: optimizing carton sizes to reduce packaging waste while simultaneously managing the increased operational complexity and performance losses associated with a more diverse range of packaging options. In this paper, we examine so-called blocking machines, where multiple packaging devices are arranged in sequence, each equipped with a specific carton size. Incoming customer orders are transferred to the devices via a conveyor belt and can only be processed by devices with appropriately sized cartons. We introduce the resulting optimization problem, which involves selecting a set of carton sizes, assigning customer orders to these devices, and sequencing the orders. We settle the computational complexity of all variants of the problem where one part of the decision is fixed or all parts are open. For the latter case, we present an exact dynamic programming algorithm that runs in polynomial time. Our method allows to analyze the tradeoff between waste generation and packaging speed. We demonstrate that our approach efficiently finds optimal solutions for real-world instances and provide further insights into the impact of different carton selection strategies.