Approximation algorithms to solve real-life multicriteria cutting stock problems

作     者：Chu, CB Antonio, J 

作者机构：Univ Technol Troyes Dept GSI F-10010 Troyes France CESCOM Technopole Metz INRIA Lorraine F-57070 Metz France 

出 版 物：《OPERATIONS RESEARCH》 (运筹学)

年 卷 期：1999年第47卷第4期

页      面：495-508页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主　　题：Dynamic programming Optimal solutions Cost functions Approximation algorithms Variable costs Total costs Consumer goods industries Business structures Linear programming 

摘      要：This paper addresses a real-life unidimensional cutting stock problem. The objective is not only to minimize trim loss, as in traditional cutting stock problems, but also to minimize cutting time. A variety of technical constraints are taken into account. These constraints often arise in the iron and steel cutting industry. Since cutting stock problems are well known to be NP-hard, it is prohibitive to obtain optimal solutions. We develop approximation algorithms for different purposes: quick response algorithms for individual customer requirement planning to build a quotation, and elaborate algorithms to provide a production plan for the next day. These latter algorithms are submitted to less strict computation time limitations. Computational results show that our algorithms improve by 8% the performance of our partner company where the cutting plan had been carried out manually by very experienced people. Numerical comparison for small sized problems shows that these algorithms provide solutions very close to optimal. These algorithms have been implemented in the company.