A heuristic for the Minimum Score Separation Problem, a combinatorial problem associated with the cutting stock problem

Kai Helge Becker and Gautam Appa
Additional contact information
Kai Helge Becker: Queensland University of Technology (QUT), Brisbane, Australia
Gautam Appa: London School of Economics and Political Science, London, UK

Journal of the Operational Research Society, 2015, vol. 66, issue 8, 1297-1311

Abstract: The Minimum Score Separation Problem (MSSP) is a combinatorial problem that was introduced in JORS 55 as an open problem in the paper industry arising in conjunction with the cutting stock problem. During the process of producing boxes, flat papers are prepared for folding by being scored with knives. The problem is to determine whether and how a given production pattern of boxes can be arranged such that a certain minimum distance between the knives can be kept. Introducing the concept of matching-based alternating Hamiltonian paths, this paper models the MSSP as the problem of finding an alternating Hamiltonian path on a graph that is the union of a matching and a type of graph known as a ‘threshold graph’. On this basis, we find a heuristic that can quickly recognize a large percentage of feasible and infeasible instances of the MSSP. Detailed computational experiments demonstrate the efficiency of our approach.

Date: 2015
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.palgrave-journals.com/jors/journal/v66/n8/pdf/jors201487a.pdf Link to full text PDF (application/pdf)
http://www.palgrave-journals.com/jors/journal/v66/n8/full/jors201487a.html Link to full text HTML (text/html)
Access to full text is restricted to subscribers.

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:pal:jorsoc:v:66:y:2015:i:8:p:1297-1311

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/41274

Access Statistics for this article

Journal of the Operational Research Society is currently edited by Tom Archibald and Jonathan Crook

More articles in Journal of the Operational Research Society from Palgrave Macmillan, The OR Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().