A tabu search algorithm for large-scale guillotine (un)constrained two-dimensional cutting problems

DOI10.1016/S0305-0548(00)00095-2zbMath0995.90075MaRDI QIDQ5959380

Ramón Alvarez-Valdés, José Manuel Tamarit, Antonio Parajón

Publication date: 24 October 2002

Published in: Computers \& Operations Research (Search for Journal in Brave)

zbMATH Keywords

heuristics; tabu search; GRASP; knapsack problem; cutting stock problem; path relinking

Mathematics Subject Classification ID

90B40: Search theory

90C59: Approximation methods and heuristics in mathematical programming

90C27: Combinatorial optimization

Related Items

Heuristic for constrained T-shape cutting patterns of rectangular pieces, Improving the efficiency of a best-first bottom-up approach for the constrained 2D cutting problem, Trim loss optimization by an improved differential evolution, A heuristic approach based on dynamic programming and and/or-graph search for the constrained two-dimensional guillotine cutting problem, A bidirectional building approach for the 2D constrained guillotine knapsack packing problem, Exact algorithm for generating two-segment cutting patterns of punched strips, Simplest optimal cutting patterns for equal rectangles, Two-stage general block patterns for the two-dimensional cutting problem, T-shape homogeneous block patterns for the two-dimensional cutting problem, The stochastic trim-loss problem, A recursive algorithm for constrained two-dimensional cutting problems, A worst case analysis of a dynamic programming-based heuristic algorithm for 2D unconstrained guillotine cutting, New and improved level heuristics for the rectangular strip packing and variable-sized bin packing problems, Exact algorithms for unconstrained three-dimensional cutting problems: A comparative study, A best-fit branch-and-bound heuristic for the unconstrained two-dimensional non-guillotine cutting problem, Exact algorithms for the two-dimensional guillotine knapsack, Improved state space relaxation for constrained two-dimensional guillotine cutting problems, Comparative analysis of pattern-based models for the two-dimensional two-stage guillotine cutting stock problem, Exact solution techniques for two-dimensional cutting and packing, A bottom-up packing approach for modeling the constrained two-dimensional guillotine placement problem, Optimization of the distribution of small scale linear Fresnel reflectors on roofs of urban buildings, Fair and square: cake-cutting in two dimensions, An EDA for the 2D knapsack problem with guillotine constraint, Simple block patterns for the two-dimensional cutting problem, Strip generation algorithms for constrained two-dimensional two-staged cutting problems, Dynamic programming algorithms for the optimal cutting of equal rectangles, Generating optimal multi-segment cutting patterns for circular blanks in the manufacturing of electric motors, Modeling Two-Dimensional Guillotine Cutting Problems via Integer Programming, An improved best-first branch-and-bound algorithm for unconstrained two-dimensional cutting problems, A genetic algorithm for the two-dimensional knapsack problem with rectangular pieces

Uses Software

• Tabu search

Cites Work

• Unnamed Item
• Unnamed Item
• A probabilistic heuristic for a computationally difficult set covering problem
• An approximation algorithm for solving unconstrained two-dimensional knapsack problems
• An and-or-graph approach for two-dimensional cutting problems
• A recursive exact algorithm for weighted two-dimensional cutting
• Staged and constrained two-dimensional guillotine cutting problems: an AND/OR-graph approach
• The DH/KD algorithm: A hybrid approach for unconstrained two-dimensional cutting problems
• An improvement of Viswanathan and Bagchi's exact algorithm for constrained two-dimensional cutting stock
• An exact algorithm for orthogonal 2-D cutting problems using guillotine cuts
• Greedy randomized adaptive search procedures
• An improved version of Wang's algorithm for two-dimensional cutting problems
• An efficient approach for large-scale two-dimensional guillotine cutting stock problems
• Two Algorithms for Constrained Two-Dimensional Cutting Stock Problems
• Algorithms for Unconstrained Two-Dimensional Guillotine Cutting
• An Algorithm for Two-Dimensional Cutting Problems
• Best-First Search Methods for Constrained Two-Dimensional Cutting Stock Problems
• Constrained two-dimensional cutting: an improvement of Christofides and Whitlock's exact algorithm
• Recursive Computational Procedure for Two-dimensional Stock Cutting
• Une amélioration de l'algorithme récursif de Herz pour le problème de découpe à deux dimensions