Approximation algorithms to solve real-life multicriteria cutting stock problems

Approximation algorithms to solve real-life multicriteria cutting stock problems

0.00 Avg rating0 Votes
Article ID: iaor2001761
Country: United States
Volume: 47
Issue: 4
Start Page Number: 495
End Page Number: 508
Publication Date: Jul 1999
Journal: Operations Research
Authors: ,
Keywords: programming: multiple criteria
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.