在线装箱问题相关近似算法研究

发布时间：2018-11-25 12:08

【摘要】：作为计算机科学与技术领域最基础、最原始的问题之一,装箱问题的研究已延续四十年之久,许多关键结果相继涌现,一些隶属于计算机科学以及组合优化学科内的重大理论均起源于对装箱问题的研究,由此可见对装箱问题的研究意义深远。此外,装箱问题在实际生活中应用极其广泛,不论是计算机科学领域中的多处理器任务调度、负载均衡,还是工业制造领域中的切割存储和卡车装载都是装箱问题的具体例子。近年来,基于受限空间的在线装箱问题以及带建议的在线装箱问题成为在线装箱问题的两个研究热点,其中只打开两个箱子的二维在线装箱问题的最好的结果是Januszewski提出的近似度为3.8的算法,而带建议的一维在线装箱问题,到目前为止结果最好的是由Boyar等人提出的算法,其近似度达到了4/3。本论文主要针对这两个结果分别进行了改进和相应的扩展研究,具体工作如下：1.对于只开两个箱子的正方形在线装箱问题,基于Januszewski提出的在箱子划分块的思想,通过继续划分放大物体的混合箱子,使之包括一种新类型的块,从而达到只放小物体的简单箱子中划分出的块占用率提高的目的,另外采用将一部分小物体与大物体混合装入复杂箱子的方法,弥补混合箱子的空闲空间。最终使得打开的两种类型的箱子的占用率都得到提高。通过分析得出,本文提出的只开两个箱子的正方形在线装箱算法的近似度为3.63556。2.将正方形块划分的思想扩展到只开两个箱子的立方体在线装箱和超级立方体在线装箱问题上,通过不同维度的块划分技巧,分别提出一个近似度为5.43的立方体在线装箱算法和一个近似度为32/21·2d的超级立方体在线装箱算法,在只开两个箱子的在线多维立方体装箱问题上,这两个结果均为这类问题的首次的研究结果。3.对于带建议的在线装箱问题,本文通过细化物体分类,增加物体组合拼装的种类,以及设定最少数目的建议位来表示对应的组合物体类型,最终将一维带建议的在线装箱问题的近似算法的结果改进为5/4。对于最少要用到的建议位数目问题,通过构建一类特定形式的到来物体序列,本文分析出最少需要的建议位数为(n-3OPT) log OPT来达到最优装箱效果。4.将相应的思想扩展到二维的带建议的在线装箱问题上,分别提出了近似度为2的正方形在线装箱算法和近似度为2.25的可旋转长方形在线装箱算法,这两个结果不仅是这类问题的首次研究,而且均比目前最好的不带建议位的同类问题的结果要好。5.本论文研究了二维正方形在线装箱的并行化问题,提出了一个SIMD模型,并分析出基于此模型的并行装箱算法的近似度为9/4,时间复杂度为θ(n)。
[Abstract]:As one of the most basic and primitive problems in the field of computer science and technology, the study of the packing problem has been going on for more than 40 years, and many key results have emerged one after another. Some important theories belonging to computer science and combinatorial optimization all originate from the study of packing problem, so the research on packing problem is of great significance. In addition, the packing problem is widely used in real life. Whether it is multiprocessor task scheduling, load balancing, cutting storage and truck loading in the field of industrial manufacturing, it is a concrete example of packing problem. In recent years, the online packing problem based on restricted space and the online packing problem with suggestions have become two research hotspots in online packing problem. The best result of the two-dimensional online packing problem with only two open boxes is that the approximation is 3.8 proposed by Januszewski, while the best result of the proposed one-dimensional online packing problem is by far the algorithm proposed by Boyar et al. The approximation is 4 / 3. This paper mainly aims at these two results to carry on the improvement and the corresponding expansion research separately, the concrete work is as follows: 1. For the problem of square online packing with only two boxes open, based on the idea of dividing blocks in boxes proposed by Januszewski, a new type of block is included by continuing to divide mixed boxes with enlarged objects. In order to achieve the purpose of increasing the occupancy rate of blocks divided in simple boxes with only small objects, the method of mixing some small objects with large objects into complex boxes is adopted to make up for the free space of the mixed boxes. As a result, the occupancy rate of both types of open boxes is increased. Through analysis, the approximate degree of the square online packing algorithm with only two boxes is 3.63556.2. The idea of square block partition is extended to the problem of cubes online packing and super cube online packing with only two boxes, and the techniques of block partitioning in different dimensions are used. A cube online packing algorithm with an approximate degree of 5.43 and a super cube online packing algorithm with an approximate degree of 32 / 21.2 d are proposed, respectively. These two results are the first results of this kind of problem. 3. 3. For the online packing problem with suggestions, this paper presents the corresponding combination object types by refining the classification of objects, increasing the types of assembly of objects, and setting the minimum number of suggested bits. Finally, the approximate algorithm for one dimensional online packing problem with suggestions is improved to 5 / 4. For the problem of the least number of bits to be used, by constructing a class of special coming object sequences, this paper analyzes that the least required number of suggested bits is (n-3OPT) log OPT) to achieve the optimal packing effect. 4. In this paper, the corresponding idea is extended to the two dimensional online packing problem with suggestions, and a square online packing algorithm with approximate degree 2 and a rotating rectangle online packing algorithm with an approximate degree of 2.25 are proposed, respectively. These two results are not only the first study of this kind of problem, but also better than that of the best one without suggestion. In this paper, we study the parallelization of two-dimensional square online packing, propose a SIMD model, and analyze that the parallel packing algorithm based on this model has an approximate degree of 9 / 4 and a time complexity of 胃 (n).
【学位授予单位】：北京交通大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：TP301.6

【相似文献】