A Two-Stage Bin Packing Algorithm for Minimizing Machines and Operators in Cyclic Production Systems

This study presents a novel, two-stage algorithm that minimizes the number of machines and operators required to produce multiple product types repeatedly in cyclic scheduling. Our algorithm treats the problem of minimum machines as a bin packing problem (BPP), and the problem of determining the number of operators required is also modeled as the BPP, but with constraints. The BPP is NP-hard, but with suitable heuristic algorithms, the proposed model allocates multiple product types to machines and multiple machines to operators without overlapping setup times (machine interference). The production schedule on each machine is represented as a circle (donut). By using lower bounds, it is possible to assess whether the number of machines required by our model is optimal; if not, the optimality gap can be quantified. The algorithm has been validated using real-world data from an industrial facility producing 17 types of products. The results of our algorithm led to significant cost savings and improved scheduling performance. The outcomes demonstrate the effectiveness of the proposed algorithm in optimizing resource utilization by reducing the number of machines and operators required. Although this study focuses on a manufacturing system, the model can also be applied to other contexts.