×

Simulated annealing for order spread minimization in sequencing cutting patterns. (English) Zbl 0948.90066

Summary: 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.

MSC:

90B35 Deterministic scheduling theory in operations research
90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming

Software:

CUTGEN1
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Chvátal, V., Linear Programming (1983), Freeman: Freeman New York · Zbl 0318.05002
[2] Eglese, R. W., Simulated annealing: A tool for operational research, European Journal of Operational Research, 46, 271-281 (1990) · Zbl 0699.90080
[3] Gau, T.; Wäscher, G., CUTGEN1: A problem generator for the one-dimensional cutting stock problem, European Journal of Operational Research, 84, 572-579 (1995) · Zbl 0918.90117
[4] Gilmore, P. C.; Gomory, R. E., A linear programming approach to the cutting stock problem, Operations Research, 9, 849-859 (1961) · Zbl 0096.35501
[5] Johnston, R. E., Cutting patterns and cutter schedules, ASOR Bulletin, 4, 3-13 (1984)
[6] Madsen, O. B.G., An application of travelling-salesman routines to solve pattern-allocation problems in the glass industry, Journal of the Operational Research Society, 39, 249-256 (1988) · Zbl 0638.90047
[7] Stadtler, H., A one-dimensional cutting stock problem in the aluminium industry and its solution, European Journal of Operational Research, 44, 209-223 (1990) · Zbl 0684.90049
[8] Wäscher, G.; Gau, T., Heuristics for the integer one-dimensional cutting stock problem — A computational study, Operations Research-Spektrum, 18, 131-144 (1996) · Zbl 0853.90099
[9] Yuen, B. J., Heuristics for sequencing cutting patterns, European Journal of Operational Research, 55, 183-190 (1991) · Zbl 0729.90997
[10] Yuen, B. J., Improved heuristics for sequencing cutting patterns, European Journal of Operational Research, 87, 57-64 (1995) · Zbl 0914.90230
[11] Yuen, B. J.; Richardson, K. V., Establishing the optimality of sequencing heuristics for cutting stock problems, European Journal of Operational Research, 84, 590-598 (1995) · Zbl 0918.90125
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.