Approximation Algorithms to Solve Real-Life Multicriteria Cutting Stock Problems

Chengbin Chu and Julien Antonio
Additional contact information
Chengbin Chu: Département GSI, Université de Technologie de Troyes, 12 rue Marie Curie-BP 2060, 10010 Troyes Cedex, France
Julien Antonio: INRIA-Lorraine, CESCOM Technopôle Metz 2 000, 4 rue Marconi, 57070 Metz, France

Operations Research, 1999, vol. 47, issue 4, 495-508

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.

Keywords: cutting stock/trim; approximation algorithms to solve cutting stock problems; approximations; heuristic (search for similar items in EconPapers)
Date: 1999
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (10)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.47.4.495 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:47:y:1999:i:4:p:495-508

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().