Dissertation > Excellent graduate degree dissertation topics show

Heuristic Algorithm Design and Analysis of One-Dimensional Bin Packing Problem

Author: ShaoFeiNiu
Tutor: PangHaLi
School: Northeastern University
Course: Systems Engineering
Keywords: Heuristic algorithm Bin packing problem Dynamic programming Batchesarriving First-fit algorithm
CLC: TP301.6
Type: Master's thesis
Year: 2013
Downloads: 5
Quote: 0
Read: Download Dissertation

Abstract


Bin Packing Problem (BPP) is one of the most famous combinatorial optimization problems. And as one of the earliest studied NP-hard problem, it works as a research platform for the complexity theory and gives director to other NP-hard problems. Bin packing problem has many important applications such as multiprocessor scheduling, resource allocation, and real-world planning, packing and scheduling optimization problems. The problem has been studied for more than forty years, many combinatorial optimization researchers, including E.G. Coffman, D.S. Johnson and Turing Prize winner A.C. Yao, have built up integrate theories and explored many algorithms for the problem though the topics are far from ending.To Coffman’s opinion, the research on bin packing problem can be divided into three parts:designing and analyzing new approximation algorithms, provide performance bounds for approximation algorithms, and study new bin packing problem with constraint pick up from real-world applications. Let n be the length of input list (problem scale), the main contributions of this thesis are in the following.For one-dimensional packing problem presents a heuristic algorithm with a buffer tank, through the Benchmark problem solving, on the proposed algorithm and the performance of other classical algorithms are compared and analyzed; on the proposed algorithm is time and space complexity analysis and worst performance ratio analysis. Analyzed the algorithm parameters affect the algorithm performance ratio.Packing problem with constraints:This article is based on the actual application needs, proposed a work piece arrive in batches packing problem, the problem is given an approximation algorithm based on dynamic programming, analysis time and space complexity of the algorithm degrees, the worst performance ratio.Finally, this paper summarizes the work and look forward to further research directions.

Related Dissertations

  1. Study on Site Selection of Ecological Food Franchisees in Jiaxiang, Taiyuan,F426.82
  2. A Hyper-heuristic Using GRASP with Path-Relinking,TP301.6
  3. Research on Combinatorial Optimization Problem Based on DNA Self-Assemble,TP399-C8
  4. Container berths Scheduling Optimization Model and Algorithm,U691.3
  5. Hotels based collaborative filtering recommendation system Research and Implementation,TP391.3
  6. Research of Vehicle Scheduling Problem Based on Ant Colony Algorithm,TP301.6
  7. The Research of Signal Detecting Algorithms and Improved Sphere Detecting Algorithms in MIMO Systems,TN919.3
  8. Reasearch on Packing of Apparel Shaped Parts Using Genetic Simulated Annealing Algorithm,TP301.6
  9. Research on Network Automat IC Test Based on Set Cover Theory,TP393.06
  10. Efficient Algorithms for the Job Shop Scheduling Problem,O224
  11. Global Optimization Algorithms of Clusters,O561
  12. Hysteresis -based optimization of vehicle routing problem,O224
  13. Parallel sorting multiple orders optimization problem,F224
  14. Aircraft assembly moving assembly line job scheduling optimization,V262.43
  15. Flexible resource scheduling algorithm for dynamic combinatorial production and realization,F426.8
  16. Resource-based needs analysis study time production plant logistics optimization,F426.471
  17. Study on Real-time Rhythmic Information Retrieval of Musical Audio Signal and the System Implementation,TN912.3
  18. Vendor Selection under Fuzzy Environment Research,F224;F274
  19. Study on Mixed Model Line Balancing with Human Factors Under Make-to-Order Environment,F273;F224
  20. Application Research of Critical Chain Project Method in Project Schedule Management,F224
  21. Distribution center location based on the supply chain environment research,F224

CLC: > Industrial Technology > Automation technology,computer technology > Computing technology,computer technology > General issues > Theories, methods > Algorithm Theory
© 2012 www.DissertationTopic.Net  Mobile