An algorithm for a cutting problem in window frame production

Abstract

This research discusses the cutting problem encountered by a real-life window frame manufacturer. In the problem, four types of bars (upper, bottom, left and right) should be cut from raw material aluminium profiles for each window frame order. These bars must be cut such that trim loss is minimised. Moreover, the bars should be assigned to the same raw material profile if possible to increase productivity; otherwise, they should be assigned to neighbouring raw material profiles. Furthermore, the numbers of bar types as derived from a raw material profile should not be unbalanced because this scenario induces subsequent machine load imbalance. In this study, we develop a mixed integer programming model and a knapsack-based heuristic approach that minimises the weighted sum of trim loss, bar type imbalance and the degree of order spreading. The results of computational experiments demonstrate the effectiveness of the proposed algorithm, and the proposed approach outperforms the legacy system of the company. Thus, this method is currently being used by the firm in question.