A Simulated Annealing Enhancement of the Best-Fit Heuristic for the Orthogonal Stock-Cutting Problem

Edmund K. Burke
Edmund K. Burke
[email protected]
School of Computer Science, University of Nottingham, Nottingham, NG8 1BB, United Kingdom
Search for more papers by this author
,
Graham Kendall
Graham Kendall
[email protected]
School of Computer Science, University of Nottingham, Nottingham, NG8 1BB, United Kingdom
Search for more papers by this author
,
Glenn Whitwell
Glenn Whitwell
[email protected]
School of Computer Science, University of Nottingham, Nottingham, NG8 1BB, United Kingdom
Search for more papers by this author

Edmund K. Burke

[email protected]

School of Computer Science, University of Nottingham, Nottingham, NG8 1BB, United Kingdom

Search for more papers by this author

Graham Kendall

[email protected]

School of Computer Science, University of Nottingham, Nottingham, NG8 1BB, United Kingdom

Search for more papers by this author

Glenn Whitwell

[email protected]

School of Computer Science, University of Nottingham, Nottingham, NG8 1BB, United Kingdom

Search for more papers by this author

Published Online:5 Feb 2009https://doi.org/10.1287/ijoc.1080.0306

Supplemental Material

ijoc.1080.0306-sm-burke_kendall_whitwell.pdf (181 KB)

Cited by
- A dynamic clustering search algorithm for the rectangular strip packing problem
  Applied Soft Computing, Vol. 191
- An effective evolutionary algorithm for packing rectangles into a fixed size circular container
  European Journal of Operational Research, Vol. 327, No. 1
- Predictive container orchestration in the cloud using artificial intelligence techniques
  16 June 2025 | Computing, Vol. 107, No. 7
- Solving rectangular strip packing problem with reinforcement learning: a comparative case study
  20 June 2025 | RAIRO - Operations Research, Vol. 59, No. 3
- Cutting and Packing
  17 October 2025
- A backtracking heuristic algorithm for two-dimensional strip packing with rotation
  31 January 2025 | Science Progress, Vol. 108, No. 1
- Optimization of Sheet Material Layout in Industrial Production Using Genetic Algorithms
- Cutting and Packing
  2 August 2024
- A BIASED RANDOM-KEY GENETIC ALGORITHM FOR THE 2D STRIP PACKING PROBLEM WITH ORDER AND STABILITY CONSTRAINTS
  1 January 2024 | Pesquisa Operacional, Vol. 44
- An efficient constructive heuristic for the rectangular packing problem with rotations
  28 December 2023 | PLOS ONE, Vol. 18, No. 12
- A Q-learning-based algorithm for the 2D-rectangular packing problem
  4 June 2023 | Soft Computing, Vol. 27, No. 17
- Generalized multiple strip packing problem: Formulations, applications, and solution algorithms
  Computers & Industrial Engineering, Vol. 178
- Framework of algorithm portfolios for strip packing problem
  Computers & Industrial Engineering, Vol. 172
- TSMSA: a 2DSPP algorithm with multi-strategy rectangle selection
  28 February 2022 | The Journal of Supercomputing, Vol. 78, No. 10
- A cluster-based yard template design integrated with yard crane deployment using a placement heuristic
  Transportation Research Part E: Logistics and Transportation Review, Vol. 160
- Applying machine learning for the anticipation of complex nesting solutions in hierarchical production planning
  European Journal of Operational Research, Vol. 296, No. 3
- CBAC4C: conflict‐based VM isolation control for cloud computing
  14 January 2021 | International Transactions in Operational Research, Vol. 29, No. 1
- The rectangular two-dimensional strip packing problem real-life practical constraints: A bibliometric overview
  Computers & Operations Research, Vol. 137
- Intelligent Algorithms for Rectangular Packing Problem
  4 October 2022
- Introduction to the Packing and Cutting Problem
  4 October 2022
- Mass personalization strategy under Industrial Internet of Things: A case study on furniture production
  Advanced Engineering Informatics, Vol. 50
- NHACR: A novel heuristic approach for 2D rectangle packing area minimization problem with central rectangle
  Engineering Applications of Artificial Intelligence, Vol. 103
- The effect of benchmark data characteristics during empirical strip packing heuristic performance evaluation
  9 February 2021 | OR Spectrum, Vol. 43, No. 2
- Fast Heuristic Algorithms for the Multiple Strip Packing Problem
  21 September 2021
- An Improved Adaptive Genetic Algorithm for Two-Dimensional Rectangular Packing Problem
  4 January 2021 | Applied Sciences, Vol. 11, No. 1
- A Controlled Stability Genetic Algorithm With the New BLF2G Guillotine Placement Heuristic for the Orthogonal Cutting-Stock Problem
- Odd Distance Anchors for Rapid Clustering
- An effective approach to the two-dimensional rectangular packing problem in the manufacturing industry
  Computers & Industrial Engineering, Vol. 148
- An improved priority heuristic for the fixed guillotine rectangular packing problem
  Journal of Physics: Conference Series, Vol. 1656, No. 1
- Improved metaheuristics for the two-dimensional strip packing problem
  Applied Soft Computing, Vol. 92
- Hybrid simulated annealing and reduced variable neighbourhood search for an aircraft scheduling and parking problem
  17 June 2019 | International Journal of Production Research, Vol. 58, No. 9
- Simultaneous Optimization of Passive Transit Priority Signals and Lane Allocation
  KSCE Journal of Civil Engineering, Vol. 24, No. 2
- Simultaneous Optimization of Passive Transit Priority Signals and Lane Allocation
  27 December 2019 | KSCE Journal of Civil Engineering, Vol. 24, No. 2
- An Effective Discrete Grey Wolf Optimization Algorithm for Solving the Packing Problem
  IEEE Access, Vol. 8
- Hybrid Heuristic Algorithm Based On Improved Rules & Reinforcement Learning for 2D Strip Packing Problem
  IEEE Access, Vol. 8
- Application of Nature Inspired Algorithms to Optimize Multi-objective Two-Dimensional Rectangle Packing Problem
  14 October 2019 | Journal of Industrial Integration and Management, Vol. 04, No. 04
- An efficient deterministic heuristic algorithm for the rectangular packing problem
  Computers & Industrial Engineering, Vol. 137
- A Controlled Stability Genetic Algorithm With the New BLF2G Guillotine Placement Heuristic for the Orthogonal Cutting-Stock Problem
  International Journal of Cognitive Informatics and Natural Intelligence, Vol. 13, No. 4
- A Greedy, Generative, Lattice Representation for Point Packing
- Hierarchical Search-Embedded Hybrid Heuristic Algorithm for Two-Dimensional Strip Packing Problem
  IEEE Access, Vol. 7
- Solving Two-Dimensional Rectangle Packing Problem Using Nature-Inspired Metaheuristic Algorithms
  11 July 2018 | Journal of Industrial Integration and Management, Vol. 03, No. 02
- Data driven point packing for fast clustering
- Cutting and Packing
  14 August 2018
- Cutting and Packing
  18 December 2017
- An Effective Corner Increment-Based Algorithm for the Two-Dimensional Strip Packing Problem
  IEEE Access, Vol. 6
- An improved skyline based heuristic for the 2D strip packing problem and its efficient implementation
  Computers & Operations Research, Vol. 80
- A hybrid algorithm based on variable neighbourhood for the strip packing problem
  13 June 2016 | Journal of Combinatorial Optimization, Vol. 32, No. 2
- A SURVEY ON HEURISTICS FOR THE TWO-DIMENSIONAL RECTANGULAR STRIP PACKING PROBLEM
  Pesquisa Operacional, Vol. 36, No. 2
- Conway crossover to create hyperdimensional point packings, with applications
- Scheduling Serial Locks: A Green Wave for Waterbound Logistics
  20 May 2015
- A Hybrid Algorithm for Strip Packing Problem with Rotation Constraint
  1 August 2016 | MATEC Web of Conferences, Vol. 68
- An efficient intelligent search algorithm for the two‐dimensional rectangular strip packing problem
  3 December 2014 | International Transactions in Operational Research, Vol. 23, No. 1-2
- An Efficient Heuristic Approach for Irregular Cutting Stock Problem in Ship Building Industry
  Mathematical Problems in Engineering, Vol. 2016
- Heuristic and genetic approach for nesting of two-dimensional rectangular shaped parts with common cutting edge concept for laser cutting and profile blanking processes
  Computers & Industrial Engineering, Vol. 80
- A Hybrid Demon Algorithm for the Two-Dimensional Orthogonal Strip Packing Problem
  Mathematical Problems in Engineering, Vol. 2015
- A block-based layer building approach for the 2D guillotine strip packing problem
  European Journal of Operational Research, Vol. 239, No. 1
- A new metaheuristic genetic-based placement algorithm for 2D strip packing
  22 February 2014 | Journal of Industrial Engineering International, Vol. 10, No. 1
- An effective shaking procedure for 2D and 3D strip packing problems
  Computers & Operations Research, Vol. 40, No. 11
- Genotype–phenotype heuristic approaches for a cutting stock problem with circular patterns
  Engineering Applications of Artificial Intelligence, Vol. 26, No. 10
- A genetic algorithm for two-dimensional bin packing with due dates
  International Journal of Production Economics, Vol. 145, No. 2
- An improved best‐fit heuristic for the orthogonal strip packing problem
  27 June 2013 | International Transactions in Operational Research, Vol. 20, No. 5
- Bidirectional best-fit heuristic considering compound placement for two dimensional orthogonal rectangular strip packing
  Expert Systems with Applications, Vol. 40, No. 10
- An improved fuzzy C-means clustering algorithm based on simulated annealing
- A Binary Search Heuristic Algorithm Based on Randomized Local Search for the Rectangular Strip-Packing Problem
  Defu Zhang,
  Lijun Wei,
  Stephen C. H. Leung,
  Qingshan Chen,
  6 June 2012 | INFORMS Journal on Computing, Vol. 25, No. 2
- Heuristics and memetic algorithm for the two-dimensional loading capacitated vehicle routing problem with time windows
  27 May 2011 | Central European Journal of Operations Research, Vol. 21, No. 2
- An Approach Based on Evaluation Particle Swarm Optimization Algorithm for 2D Irregular Cutting Stock Problem
- A simple randomized algorithm for two-dimensional strip packing
  Computers & Operations Research, Vol. 40, No. 1
- A Heuristic Based on PSO for Irregular Cutting Stock Problem
  IFAC Proceedings Volumes, Vol. 46, No. 13
- An exact strip packing algorithm based on canonical forms
  Computers & Operations Research, Vol. 39, No. 12
- Data Structures for Higher-Dimensional Rectilinear Packing
  Sam D. Allen,
  Edmund K. Burke,
  21 July 2011 | INFORMS Journal on Computing, Vol. 24, No. 3
- A heuristic algorithm for the strip packing problem
  30 May 2012 | Journal of Heuristics, Vol. 18, No. 4
- Solving 2D Rectangle Packing Problem Based on Layer Heuristic and Genetic Algorithm
- A tree search algorithm for solving the multi-dimensional strip packing problem with guillotine cutting constraint
  23 February 2012 | Annals of Operations Research, Vol. 196, No. 1
- An efficient deterministic heuristic for two-dimensional rectangular packing
  Computers & Operations Research, Vol. 39, No. 7
- A reference length approach for the 3D strip packing problem
  European Journal of Operational Research, Vol. 220, No. 1
- The three-dimensional knapsack problem with balancing constraints
  Applied Mathematics and Computation, Vol. 218, No. 19
- Cyclic-order neighborhoods with application to the vehicle routing problem with stochastic demand
  European Journal of Operational Research, Vol. 217, No. 2
- Automating the Packing Heuristic Design Process with Genetic Programming
  Evolutionary Computation, Vol. 20, No. 1
- Simulated Annealing
- Automatic Discovery of Optimisation Search Heuristics for Two Dimensional Strip Packing Using Genetic Programming
- A hybrid simulated annealing metaheuristic algorithm for the two-dimensional knapsack packing problem
  Computers & Operations Research, Vol. 39, No. 1
- A Reinforced Tabu Search Approach for 2D Strip Packing
- A new guillotine placement heuristic combined with an improved genetic algorithm for the orthogonal cutting-stock problem
- A effective heuristic algorithm for two-dimensional rectangle-packing problems
- A two-stage intelligent search algorithm for the two-dimensional strip packing problem
  European Journal of Operational Research, Vol. 215, No. 1
- A fast layer-based heuristic for non-guillotine strip packing
  Expert Systems with Applications, Vol. 38, No. 10
- A hybrid algorithm for the orthogonal stock-cutting problem
- A squeaky wheel optimisation methodology for two-dimensional strip packing
  Computers & Operations Research, Vol. 38, No. 7
- A skyline heuristic for the 2D rectangular packing and strip packing problems
  European Journal of Operational Research, Vol. 35
- A grid-based heuristic for two-dimensional packing problems
- Development of an algorithm to generate and evaluate cutting solutions in edging and trimming operations at sawmills
  29 November 2012 | Revista Facultad de Ingeniería Universidad de Antioquia, No. 59
- A hybrid placement strategy for the three-dimensional strip packing problem
  European Journal of Operational Research, Vol. 209, No. 3
- A Parallel Branch-and-Bound Approach to the Rectangular Guillotine Strip Cutting Problem
  Sławomir Bąk,
  Jacek Błażewicz,
  Grzegorz Pawlak,
  Maciej Płaza,
  Edmund K. Burke,
  Graham Kendall,
  2 July 2010 | INFORMS Journal on Computing, Vol. 23, No. 1
- Effective Application of Simulated Annealing
  15 February 2011
- A Skyline-Based Heuristic for the 2D Rectangular Strip Packing Problem
- An Exact Algorithm for the Two-Dimensional Strip-Packing Problem
  Marco Antonio Boschetti,
  Lorenza Montaletti,
  1 December 2010 | Operations Research, Vol. 58, No. 6
- A Genetic Programming Hyper-Heuristic Approach for Evolving 2-D Strip Packing Heuristics
  IEEE Transactions on Evolutionary Computation, Vol. 14, No. 6
- A Reinforced Tabu Search Approach for 2D Strip Packing
  International Journal of Applied Metaheuristic Computing, Vol. 1, No. 3
- The best-fit heuristic for the rectangular strip packing problem: An efficient implementation and the worst-case approximation ratio
  Computers & Operations Research, Vol. 37, No. 2
- A Hyper-Heuristic Approach to Strip Packing Problems
- Bidirectional best-fit heuristic for orthogonal rectangular strip packing
  13 October 2009 | Annals of Operations Research, Vol. 172, No. 1
- An optimisation model for airlift load planning: Galahad and the quest for the ‘holy grail’
- Evolutionary and Ant Colony Optimization Based Approaches for a Two-Dimensional Strip Packing Problem

cover image INFORMS Journal on Computing

Volume 21, Issue 3

Summer 2009

Pages 347-516

Article Information

Supplemental Material

Metrics

Information

Received:July 01, 2004
Accepted:July 01, 2008
Published Online:February 05, 2009

Cite as

Edmund K. Burke, Graham Kendall, Glenn Whitwell, (2009) A Simulated Annealing Enhancement of the Best-Fit Heuristic for the Orthogonal Stock-Cutting Problem. INFORMS Journal on Computing 21(3):505-516.

https://doi.org/10.1287/ijoc.1080.0306

Keywords

PDF download

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

A Simulated Annealing Enhancement of the Best-Fit Heuristic for the Orthogonal Stock-Cutting Problem

Supplemental Material

Volume 21, Issue 3

Article Information

Supplemental Material

Metrics

Information

Cite as

Keywords

Sign Up for INFORMS Publications Updates and News