Approximation algorithms to solve real-life multicriteria cutting stock problems

This paper addresses a real-life unidimensional cutting stock problem. The objective is not only to minimize trim loss, as in traditional cutting stoc k problems, but also to minimize cutting time. A variety of technical const raints are taken into account. These constraints often arise in the iron an d steel cutting industry. Since cutting stock problems are well known to be NP-hard, it is prohibitive to obtain optimal solutions. We develop approxi mation algorithms for different purposes: quick response algorithms for ind ividual customer requirement planning to build a quotation, and elaborate a lgorithms to provide a production plan for the next day. These latter algor ithms are submitted to less strict computation time limitations. Computatio nal results show that our algorithms improve by 8% the performance of our p artner company where the cutting plan had been carried out manually by very experienced people. Numerical comparison for small sized problems shows th at these algorithms provide solutions very close to optimal. These algorith ms have been implemented in the company.