Two-dimensional skiving and cutting stock problem with setup cost based on column-and-row generation

Danni Wang, Fan Xiao, Lei Zhou and Zhe Liang

European Journal of Operational Research, 2020, vol. 286, issue 2, 547-563

Abstract: In this paper, we address a new variant of the cutting stock problem, in which skiving is allowed and setup costs are considered. Specifically, the output sheets are generally longer but narrower than the input coils. To satisfy the demand of each sheet, combining two or more coils is allowed. Moreover, because changing from one pattern to another involves considerable time and cost, minimizing the number of different patterns or setups is vital. Thus, the objective of our study is to minimize the material cost and the number of setups. We propose an integer programming (IP) formulation for the problem that contains an exponential number of binary variables and column-dependent constraints. The linear programming (LP) relaxation is solved using a column-and-row generation framework that involves a knapsack subproblem and a nonlinear IP subproblem. For the latter, we propose a decomposition-based exact solution method with pseudo-polynomial time. To obtain IP solutions, we develop a diving heuristic based on matching level. The computational experiments show that these algorithms are efficient and of high quality.

Keywords: Production; Skiving and cutting stock problem; Setup cost; Column-and-row generation; Diving heuristic (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221720302903
Full text for ScienceDirect subscribers only

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:eee:ejores:v:286:y:2020:i:2:p:547-563

DOI: 10.1016/j.ejor.2020.03.060

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().