An algorithm for a cutting problem in window frame production
针对窗框制造中铝型材切割的优化问题，提出混合整数规划模型和基于背包的启发式算法，最小化废料、型材类型不平衡和订单分散程度，实验证明优于公司原有系统。
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.