Progressive Selection Method for the Coupled Lot-Sizing and Cutting-Stock Problem

Tao Wu (), Kerem Akartunal? (), Raf Jans () and Zhe Liang ()
Additional contact information
Tao Wu: Advanced Analytics Department, Dow Chemical, Midland, Michigan 48642
Kerem Akartunal?: Department of Management Science, University of Strathclyde, Glasgow G4 0GE, United Kingdom
Raf Jans: Department of Logistics and Operations Management, HEC Montréal, H3T 2A7 Montréal (Québec), Canada
Zhe Liang: School of Economics and Management, Tongji University, Shanghai, 200092, China

INFORMS Journal on Computing, 2017, vol. 29, issue 3, 523-543

Abstract: The coupled lot-sizing and cutting-stock problem has been a challenging and significant problem for industry, and has therefore received sustained research attention. The quality of the solution is a major determinant of cost performance in related production and inventory management systems, and therefore there is intense pressure to develop effective practical solutions. In the literature, a number of heuristics have been proposed for solving the problem. However, the heuristics are limited in obtaining high solution qualities. This paper proposes a new progressive selection algorithm that hybridizes heuristic search and extended reformulation into a single framework. The method has the advantage of generating a strong bound using the extended reformulation, which can provide good guidelines on partitioning and sampling in the heuristic search procedure to ensure an efficient solution process. We also analyze per-item and per-period Dantzig–Wolfe decompositions of the problem and present theoretical comparisons. The master problem of the per period Dantzig–Wolfe decomposition is often degenerate, which results in a tailing-off effect for column generation. We apply a hybridization of Lagrangian relaxation and stabilization techniques to improve the convergence. The discussion is followed by extensive computational tests, where we also perform detailed statistical analyses on various parameters. Comparisons with other methods indicate that our approach is computationally tractable and is able to obtain improved results.

Keywords: integer programming; cutting stock; lot sizing; heuristics; column generation; Dantzig–Wolfe decomposition (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2017.0746 (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:orijoc:v:29:y:2017:i:3:p:523-543

Access Statistics for this article

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