Heuristic Algorithm Design And Analysis Of One-Dimensional Bin Packing Problem

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.