The solutions achieved by each of the placement policies: a) Leftmost, b) Tallest Neighbour, and c) Smallest Neighbour on problem C2P3 from Hopper and Turton (2001).
Processing of the tower rectangles.76 Figure 3.7. Procedure when no rectangle will fit gap.75 Figure 3.6. Finding a new gap when the old gap has not been completely filled.74 Figure 3.5. Storing the skyline heights of the layout on a sheet of width 9 units when empty and after packing seven rectangles.72 Figure 3.4. Placement next to shortest neighbour.70 Figure 3.3. Placement next to tallest neighbour.70 Figure 3.2.
Expanding shapes by ½ kerf width.62 Figure 3.1. Nuances of the knife cutting procedure.61 Figure 2.6. A comparison of the BL and BLF placement heuristics when adding a rectangle.25 Figure 2.5. Storing placement locations for one implementation of bottom-left-fill.25 Figure 2.4. An Improved Bottom-Left Method (Liu and Teng, 1999). 1 Novel Heuristic and Metaheuristic Approaches to Cutting and Packing by Glenn Whitwell, BSc Thesis Submitted to the University of Nottingham for the degree of Doctor of Philosophy School of Computer Science and Information Technology September 2004Ģ Table of Contents TABLE OF CONTENTS List of Figures.vi List of Tables.xi Abstract.xiv Publications Produced.xv Acknowledgements.xvi PART A CUTTING AND PACKING 1 1 Introduction Background and Motivation Aims and Scope Contributions Overview of the Thesis The Stock Cutting Problem Cutting and Packing: An Overview Two Dimensional Orthogonal Packing Rectangular Benchmark Problems from the Literature Two Dimensional Irregular Packing Irregular Benchmark Data from the Literature Optimisation and Search Methods Packing within Industry Cutting and Packing: Summary.64 iiģ Table of Contents PART B RECTANGULAR PACKING 65 3 The Best-Fit Placement Heuristic Overview Implementation Benchmark Problems Experimentation and Results Summary A Metaheuristic Hybrid Approach Overview of the Hybrid Metaheuristic Approach Motivation of the Hybrid Strategy Development of a Floating Point Skyline Representation Best-Fit Conversion to Bottom-Left-Fill Representation Hybrid Approach Summary Benchmark Test Data Experimentation and Results Summary An Interactive Approach An Overview of the New User-Guided Approach User-Guided Procedure Benchmark Data Experimentation and Results Summary iiiĤ Table of Contents PART C IRREGULAR PACKING Geometry, Trigonometry and the No-Fit Polygon Geometry Libraries Shape Representation The No-Fit Polygon No-Fit Polygon Versus Standard Trigonometry Overlap Detection Generation of the No-Fit Polygon: Previous Literature Approaches and their Degeneracies Automated Packing using Trigonometric Approaches Motivation for the Approach The New Bottom-Left-Fill Approach Benchmark Problems Experiments Summary The No-Fit Polygon: A Robust Implementation The New No-Fit Polygon Construction Algorithm Orbiting / Sliding Start Points Pseudocode Problem Cases Generation Times on the Benchmark Data Summary ivĥ Table of Contents 9 Automated Packing using the No-Fit Polygon Modifying the No-Fit Polygon Generation Algorithm to Handle Arcs An Amended Packing Algorithm using the No-Fit Polygon Experimental Results Summary PART D DISCUSSION Conclusions Discussion Future Work Dissemination Academic Community Industrial Partner Commercial Exploitation REFERENCES 255 APPENDICES APPENDIX A Layouts for Rectangular Benchmarks APPENDIX B Layouts for Irregular Benchmarks APPENDIX C New Rectangular Benchmark Instances APPENDIX D New Irregular Benchmark Instances vĦ List of Figures LIST OF FIGURES Figure 2.1.
0 kommentar(er)
