Simulated annealing for order spread minimization in sequencing cutting patterns

The Order Spread Minimization Problem (OSMP) is a sequencing problem that arises in the process of planning industrial cutting operations. As it can be looked upon as a generalization of the Travelling-Salesman Problem (TSP), it has to be classified as NP-complete. Thus heuristic algorithms are required in order to solve large problem instances. In this paper the authors suggest to apply Simulated Annealing (SA) to the OSMP. A specific version of SA is developed and compared to both an approach previously introduced into the literature by Madsen and a traditional 3-opt-procedure. The performance of these methods is compared on a set of 2400 randomly generated problem instances. SA appears to provide solutions which - in terms of solution quality - are equivalent to those generated by the 3-opt-procedure. However, computing times of the latter for solving large instances are prohibitive. In relation to Madsen's approach SA provides significantly improved solutions at the expense of a moderate increase in computing times. (C) 1998 Elsevier Science B.V. All rights reserved.