论文标题
两杆图表包装问题
Two-Bar Charts Packing Problem
论文作者
论文摘要
我们考虑一个条形图包装问题（BCPP），其中有必要以最小长度的条形打包条形图（BCS）。一方面，问题是垃圾箱包装问题（BPP）的概括，另一方面，具有多学科工作的项目调度问题的特定情况和一种有限的非利用资源。早些时候，我们提出了一种多项式算法，该算法为给定的非进攻BC构建最佳包装。该结果概括了BPP的类似结果。对于两杆图表包装问题（2-BCPP）时，当每个BC由两个条组成时，我们已经提出的算法在多项式时间内构造一个包装，其长度不超过$ 2 \ opt+1 $，而$ opt opt opt $是包装的最小可能长度。据我们所知，这是对2-BCPP的第一个保证估计。我们还进行了一个数值实验，在其中比较了通过近似算法构建的解决方案与CPLEX软件包构建的最佳解决方案。实验结果证实了已开发算法的高效率。
We consider a Bar Charts Packing Problem (BCPP), in which it is necessary to pack bar charts (BCs) in a strip of minimum length. The problem is, on the one hand, a generalization of the Bin Packing Problem (BPP), and, on the other hand, a particular case of the Project Scheduling Problem with multidisciplinary jobs and one limited non-accumulative resource. Earlier, we proposed a polynomial algorithm that constructs the optimal package for a given order of non-increasing BCs. This result generalizes a similar result for BPP. For Two-Bar Charts Packing Problem (2-BCPP), when each BC consists of two bars, the algorithm we have proposed constructs a package in polynomial time, the length of which does not exceed $2\ OPT+1$, where $OPT$ is the minimum possible length of the packing. As far as we know, this is the first guaranteed estimate for 2-BCPP. We also conducted a numerical experiment in which we compared the solutions built by our approximate algorithms with the optimal solutions built by the CPLEX package. The experimental results confirmed the high efficiency of the developed algorithms.
