Hybridising Tabu Search with Optimisation Techniques for Irregular Stock Cutting
Authors:
- 1 August 2001
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Management Science
- Vol. 47 (8) , 1160-1172
Abstract
Sequential meta-heuristic implementations for the irregular stock-cutting problem have highlighted a number of common problems. The literature suggests a consensus that it is more efficient to allow configurations with overlapping pieces in the solution space and to penalise these in the evaluation function. However, depending on the severity of the penalty this relaxation results in a tendency to converge toward infeasible solutions or to seek out feasible solutions at the expense of overall quality. A further problem is encountered in defining a neighbourhood search strategy that can deal with the infinite solution space inherent in the irregular stock-cutting problem. The implementation in this paper adopts a hybrid tabu search approach that incorporates two very different optimisation routines that utilise alternative neighbourhoods to address the described problems.Keywords
This publication has 10 references indexed in Scilit:
- Simulated annealing approach for solving stock cutting problem2002
- The irregular cutting-stock problem — a new procedure for deriving the no-fit polygonComputers & Operations Research, 2001
- A tabu thresholding implementation for the irregular stock cutting problemInternational Journal of Production Research, 1999
- Jostling for position: local improvement for irregular cutting patternsJournal of the Operational Research Society, 1998
- Tabu Search1997
- A simulated annealing approach to the nesting problem in the textile manufacturing industryAnnals of Operations Research, 1995
- Compaction and separation algorithms for non-convex polygons and their applicationsEuropean Journal of Operational Research, 1995
- Using a tabu search approach for solving the two-dimensional irregular cutting problemAnnals of Operations Research, 1993
- Algorithms for Nesting Problems1993
- An algebra of polygons through the notion of negative shapesCVGIP: Image Understanding, 1991