Hybridising tabu search with optimisation techniques for irregular stock cutting

• 成果类型: Article
• 署名作者: Bennell, JA; Dowsland, KA
• 署名单位: University of Southampton; Swansea University
• 刊物名称: MANAGEMENT SCIENCE
• ISSN/ISSBN: 0025-1909
• DOI: 10.1287/mnsc.47.8.1160.10230
• 发表日期: 2001
• 页码: 1160-1172
• 关键词: irregular stock cutting; packing problems; tabu search; linear programming

摘要

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.