### 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.

Original language | English |
---|---|

Pages (from-to) | 1297 - 1311 |

Journal | Journal of the Operational Research Society |

Volume | 66 |

Issue number | 8 |

Early online date | 29 Oct 2014 |

DOIs | |

Publication status | Published - 31 Aug 2015 |

### Keywords

- minimum score separation problem
- paper industry
- production pattern
- alternating Hamiltonian paths
- threshold graph
- cutting stock problem
- bin packing
- heuristics
- networks and graphs
- Travelling Salesman Problem

## Fingerprint Dive into the research topics of 'A heuristic for the minimum score separation problem, a combinatorial problem associated with the cutting stock problem'. Together they form a unique fingerprint.

## Cite this

Becker, K. H., & Appa, G. (2015). A heuristic for the minimum score separation problem, a combinatorial problem associated with the cutting stock problem.

*Journal of the Operational Research Society*,*66*(8), 1297 - 1311 . https://doi.org/10.1057/jors.2014.87