Dissertation > Excellent graduate degree dissertation topics show

An execution rate of 2.7687 two-dimensional harmonic algorithm

Author: HanZuo
Tutor: CaoGuiQin；GuoHe
School: Dalian University of Technology
Course: Applied Computer Technology
Keywords: bin packing problem HARMONIC algorithm asymptotic worst-case ratio NP -hard problem approximate algorithm scheduling problem On-line algorithm
CLC: TP301.6
Type: Master's thesis
Year: 2002
Downloads: 36
Quote: 0
Read: Download Dissertation

Abstract


In this paper, we study an on-line version of the two-dimensional bin packing problem that is the problem of packing a list of rectangular items into a minimum number of unit-square bins in an on-line manner. An on-line algorithm called RTDH (Refined Two Dimensional HARMONIC) is proposed and analyzed. We show that RTDH can achieve an asymptotic worst-case ratio of less than 2.7687, which beats the best-known bound 2.85958.

Related Dissertations

  1. Research on Scheduling of Whole-set Orders in JSP Based on Differential Evolution Algorithm,F273
  2. Several studies for scheduling problem,O157.5
  3. Research on the Improvements and Applications of Particle Swarm Optimization,TP18
  4. Research on Combinatorial Optimization Problem Based on DNA Self-Assemble,TP399-C8
  5. Research on Design and Application of Optimization Algorithms in Scheduling and Control Problems,TP273
  6. The sequence annotation Online Algorithm,TP391.1
  7. Research on Scheduling Semiconductor Manufacturing Using Genetic Algorithm,O223
  8. A Flow-shop S with Parameters Research of Complexity and Heuristic Lgorithms for the Parallel Machine and Cheduling Problems,O223
  9. Semi-on-line Scheduling on Parallel Machines with Non-simultaneous Machine Available Times,O223
  10. Cellular Particle Swarm Optimization and Its Applications on Flexible Job Shop Scheduling Problem,TP301.6
  11. Design and Implementation of a Platform for Defining Scheduling Problems and Evaluating Scheduling Algorithms,TP311.52
  12. Multi-Objective Flexible Job Shop Scheduling Problem Based on Hybrid Particle Swarm Optimization,TP301.6
  13. Research on PI-Line Algorithm of Volume CT Exact Reconstruction Image,TP391.41
  14. Algorithm Design for Multi-objective Flexible Job Shop Scheduling Problems,TP301.6
  15. Study on Vehicle Routing Problems with Tractor and Semitrailer Separated,F512;F259.2
  16. Design of Vehicles Dispatching System Based on Genetic Algorithm,O221
  17. Research and Development of JSP Based on IVNS Algorithm,TP301.6
  18. SMC for Sequencing Problem and SMC Based on Publicly Verificable Secret Sharing,TN918.1
  19. Under Uncertainty Based on Genetic Algorithm for Flexible Job Shop Scheduling Problem,TH165
  20. Study on Time Series Partial Periodic Patterns Based on Dynamic Time Warping Algorithm,TP311.13
  21. Packing Problem Solving and round fast optimization algorithm,TP301.6

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