Wu Yuen-Ting. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2005. / Includes bibliographical references (leaves 88-90). / Abstracts in English and Chinese. / Chapter 1. --- Introduction --- p.1 / Chapter 1.1 --- Background --- p.1 / Chapter 1.2 --- Research Objective --- p.4 / Chapter 1.3 --- Contribution --- p.5 / Chapter 1.4 --- Structure of this thesis --- p.6 / Chapter 2. --- Literature Review --- p.7 / Chapter 2.1 --- Genetic Algorithms --- p.7 / Chapter 2.1.1 --- Pre-processing step --- p.8 / Chapter 2.1.2 --- Generation of initial population --- p.10 / Chapter 2.1.3 --- Crossover --- p.11 / Chapter 2.1.4 --- Mutation --- p.12 / Chapter 2.1.5 --- Selection --- p.12 / Chapter 2.1.6 --- Results of GA on Container Loading Algorithm --- p.13 / Chapter 2.2 --- Layering Approach --- p.13 / Chapter 2.3 --- Mixed Integer Programming --- p.14 / Chapter 2.4 --- Tabu Search Algorithm --- p.15 / Chapter 2.5 --- Other approaches --- p.16 / Chapter 2.5.1 --- Block arrangement --- p.17 / Chapter 2.5.2 --- Multi-Directional Building Growing algorithm --- p.17 / Chapter 2.6 --- Comparisons of different container loading algorithms --- p.18 / Chapter 3. --- Principle of LFF Algorithm --- p.8 / Chapter 3.1 --- Definition of Flexibility --- p.8 / Chapter 3.2 --- The Less Flexibility First Principle (LFFP) --- p.23 / Chapter 3.3 --- The 2D LFF Algorithm --- p.25 / Chapter 3.3.1 --- Generation of Corner-Occupying Packing Move (COPM) --- p.26 / Chapter 3.3.2 --- Pseudo-packing and the Greedy Approach --- p.27 / Chapter 3.3.3 --- Real-packing --- p.30 / Chapter 3.4 --- Achievement of 2D LFF --- p.31 / Chapter 4. --- Error Bound Analysis on 2D LFF --- p.21 / Chapter 4.1 --- Definition of Error Bound --- p.21 / Chapter 4.2 --- Cause and Analysis on Unsatisfactory Results by LFF --- p.33 / Chapter 4.3 --- Formal Proof on Error Bound --- p.39 / Chapter 5. --- LFF for Container Loading Problem --- p.33 / Chapter 5.1 --- Problem Formulation and Term Definitions --- p.48 / Chapter 5.2 --- Possible Problems to be solved --- p.53 / Chapter 5.3 --- Implementation in Container Loading --- p.54 / Chapter 5.3.1 --- The Basic Algorithm --- p.56 / Chapter 5.4 --- A Sample Packing Scenario --- p.62 / Chapter 5.4.1 --- Generation of COPM list --- p.63 / Chapter 5.4.2 --- Pseudo-packing and the greedy approach --- p.66 / Chapter 5.4.3 --- Update of corner list --- p.69 / Chapter 5.4.4 --- Real-Packing --- p.70 / Chapter 5.5 --- Ratio Approach: A Modification to LFF --- p.70 / Chapter 5.6 --- LFF with Tightness Measure: CPU time Cut-down --- p.75 / Chapter 5.7 --- Experimental Results --- p.77 / Chapter 5.7.1 --- Comparison between LFF and LFFR --- p.77 / Chapter 5.7.2 --- "Comparison between LFFR, LFFT and other algorithms" --- p.78 / Chapter 5.7.3 --- Computational Time for different algorithms --- p.81 / Chapter 5.7.4 --- Conclusion of the experimental results --- p.83 / Chapter 6. --- Conclusion --- p.85 / Bibiography --- p.88

Bin packing is a problem with many applications in various industries. This thesis addresses a specific instance of the this problem, known as the Container Packing problem. Special attention is paid to the Pallet Loading problem which is a restricted sub-problem of the general Container Packing problem. Since the Bin Packing problem is NP-complete, it is customary to apply a heuristic measure in order to approximate solutions in a reasonable amount of computation time rather than to attempt to produce optimal results by applying some exact algorithm. Several heuristics are examined for the problems under consideration, and the results produced by each are shown and compared where relevant. / Thesis (M.Sc.)-University of Natal, Durban, 1991.

Cutting and packing problems are combinatorial optimisation problems. The major interest in these problems is their practical significance, in manufacturing and other business sectors. In most manufacturing situations a raw material usually in some standard size has to be divided or be cut into smaller items to complete the production of some product. Since the cost of this raw material usually forms a significant portion of the input costs, it is therefore desirable that this resource be used efficiently. A hybrid general genetic algorithm is presented in this work to solve one and two dimensional problems of this nature. The novelties with this algorithm are: A novel placement heuristic hybridised with a Genetic Algorithm is introduced and a general solution encoding scheme which is used to encode one dimensional and two dimensional problems is also introduced.