Cutting and Packing (C&P) issues are usually present in our daily life. Common instances comprise of resource allocation, material cutting, package packing, to mention a few. The C&P dilemma is an optimization challenge for assigning small objects into some large ones. Its high complexity and difficulty are very well known, not just because it is NP-hard but in addition because of the multi-dimensional geometrical constraints added. Within this dissertation, a hybrid approach which includes heuristic approach and genetic algorithm (GA) is made to fix the C&P problems. Heuristic-based approximation method, though it is easy and has been used widely, is often criticized for having the sub-optimal solution only. Alternatively, GA, as a stochastic algorithm influenced by the mechanism of natural selection, is well known having its ability in searching global optimum….
Contents
1 Introduction
2 Cutting and Packing Problem
2.1 Definition of cutting and packing C&P problems
2.2 Components of C&P problem
2.3 Cutting and packing duality
2.4 Constraint and dimensionality
2.5 Examples of C&P problem
2.5.1 One-dimensional bin packing problem
2.5.2 Two-dimensional bin packing problem
2.5.3 Two-dimensional strip packing problem
2.5.4 Three-dimensional strip packing problem
2.5.5 Knap-sack problem
2.6 Summary
3 Overview of Genetic Algorithm
3.1 Optimization techniques
3.2 The flow of GA
3.3 Representation
3.3.1 Order chromosome
3.4 Fitness evaluation
3.4.1 Linear scaling
3.4.2 Sigma truncation
3.4.3 Power law scaling
3.5 Selection
3.5.1 Proportionate reproduction
3.5.2 Ranking
3.5.3 Tournament selection
3.6 Genetic operators
3.6.1 Crossover
3.6.2 Mutation
3.7 Genetic operators for order chromosome
3.7.1 Partially matched crossover
3.7.2 Order crossover
3.7.3 Cycle crossover
3.7.4 Order-based mutation
3.7.5 Inversion
3.8 Replacement
3.9 Simple GA
3.10 Theoretical foundation
3.10.1 Schema Theorem
3.10.2 Building block hypothesis
3.10.3 Some criticisms to the schema theorem
3.11 Factors that affect GA performance
3.11.1 Premature convergence
3.11.2 Population diversity and selective pressure
3.11.3 Genetic drift
3.11.4 Deception
3.12 Summary
4 Hybrid Genetic Algorithm for C&P problem
4.1 Hybridization of genetic algorithm
4.1.1 Deficiency of the standard approach
4.2 Metrics for measuring the performance of approximation algorithm
4.3 Some approximation heuristics for bin packing problem
4.3.1 Next-fit heuristic (NF)
4.3.2 First-fit heuristic (FF)
4.4 Design of a hybrid GA for C&P problem
4.4.1 Characteristics of the proposed approach
4.4.2 N-dimensional strip packing problem
4.4.3 General strategy
4.4.4 Advantages
4.5 Summary
5 Job-Shop Scheduling Problem
5.1 Problem definition
5.2 Job-shop as N one-dimensional strip packing
5.3 The GA part
5.4 Data structure and operations
5.4.1 Scheduling an operation
5.4.2 Scheduling a job
5.4.3 Overall design
5.5 Experimental result
5.6 Summary
6 Garment Cutting
6.1 Problem definition
6.2 The GA part
6.2.1 Fitness evaluation
6.3 LFLA approach
6.3.1 Definitions
6.3.2 Initial conditions
6.3.3 Operations
6.3.4 Time complexity of LFLA
6.3.5 Results of LFLA
6.4 LFB approach
6.4.1 Definitions and initial conditions
6.4.2 Operations
6.4.3 Time complexity of LFB
6.4.4 Results of LFB
6.5 Summary
7 Container Loading
7.1 Packing model
7.2 Definitions
7.3 Layer
7.3.1 Construction of layer
7.3.2 Clipping
7.4 Place a box
7.5 Constraint violation checking
7.5.1 The foundation polygon
7.5.2 Region of the point
7.5.3 Inner reference point
7.5.4 Masking
7.5.5 Trimming
7.5.6 Constructing foundation
7.6 Time complexity analysis
7.6.1 Best case scenario
7.6.2 Average case scenario
7.6.3 Worst case scenario
7.7 Experiment
7.7.1 Low order case
7.7.2 Case with known optimal solution
7.7.3 Medium size cases
7.8 Summary
8 Conclusion
Bibliography
Appendices….
Source: City University of Hong Kong
Download URL 2: Visit Now