浅议一个执行率为2.7687的两维调和算法

《浅议一个执行率为2.7687的两维调和算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、大连理工大学硕士学位论文一个执行率为2.7687的两维调和算法姓名：韩鑫申请学位级别：硕士专业：计算机应用技术指导教师：曹桂琴;郭禾20020320摘要本文硬究两缎空阆上的在线(On-line)装箱阁题(Binpackingproblem)。装箱阉惩是计算规科学理论帮缀合优化领域抟基本瓣题之一。简苹酌谎，两维空润上瓣在线装箱阕题就是，把由矩形颂胬缝成的输入麸射，用一种在线方式，装入蔺定形状大小的箱子堡，求最少需要多少个箱子。在现实中，它有很多实际的应用。镝如，调度问题，内存分配，新闻的鞘}版问题，卡车的装货问题，通信网络中包的路由问题，以及大规模集成电路(VLSI)

2、芯片设计问题等。因此，装箱问题的研究有它的实际应用价值。众所周知，它是一个NP一困难问题。因此，探求该问题的近似解是研究的主要目的。基兹，对该闯题的研究鸯各秽算法，主要有Harmonic帮ROUND算法，本文针对Harmonic莘馨ROUND算法存在翡闷题，掇出一种算法豁确(RefinedTwoDimensionalHARMONIC)，傲了裙废的分析，并且给出了该算法的最环位能院是2．7687的证翳，这个结果刷新了目前最好的结果2．85958．关键宇：装箱问题，调和算法，渐进最坏性能比，Np豳难问题，近似算法，调度问题，在线算法。Abstracth1t11ispap

3、er．westudyanon—lineversionof廿1etwo—dimensionalbinpackingproblemthatiStheproblemofpackingalistofrectangularitemsintoaminimumnumberofunit．squarebinsinanon—linemanner．Anon—linealgorithmcalledRTDH(RefinedTwoDimensionalHARMoNIC)isproposedandanalyzed．、ⅣeshOW岱甜R皿HCanachieveanasymptoticworst-c

4、aseratiooflessthan2．7687．whichbeatsthebest．knownbound2．85958．KeyWords：binpackingproblem，HARMONICalgorithm，asymptoticworst-caseratio，NP-hardproblern，approximatealgorithm，schedulingproblem，On-linealgorithm一个执行率为27687的两维调和算法刖吾装箱问题(binpackingproblem)是计算机科学理论和组合优化领域的一个基本问题。因此，它的发展对计算机科学理论和组

5、合优化领域的研究有重要意义。本文研究两维空间上的在线(On—line)装箱问题。简单的说，两维空间上的在线装箱问题就是，把由矩形项目组成的输入序列，用一种在线方式，装入固定形状大小的箱子里，求最少需要多少个箱子[8]。在现实中，它有很多实际的应用。例如，调度问题(schedulingproblem)，内存分配(memoryallocationinpagedcomputersystem)，新闻的排版问题，卡车的装货，在通信网络中包的路由，还有大规模集成电路(VLS])的芯片的设计问题等。众所周知，它是一个NP—hard[2]问题。因此，探求该问题的近似解是研究的主要目

6、的。下面，重点来看一下调度问题与该问题之间的联系。先举个任务调度(JobScheduling)的例子，现有PMCS(PartitionableMeshConnectedSystem)，其大小为hX，，和一些要执行的任务，每个任务需要大小为(x；，Y。)的submesh，且每个任务的执行时间为1个单位时间，求执行完所有任务，最少需要多少时间[9]?很明显，任何一个时刻，网格(mesh)中的一个CPU只能供一个任务独占。这一点与两维的装箱问题中，任何两个项目不可能重叠装在一起是一致的。而且，可以用箱子的大小来表示PMCS的大小，每个大小为(x，，Y；)项目代表大小为(x

7、。，Y。)任务，又因为任何一个任务的执行时间都为一个单位时间，所以求最少的时间也就是在求需要最少箱子的个数。本篇论文结构如下：第一章介绍了一些基本的概念，对项目进行分类。第二章提出RTDH的算法。第三章致力于最坏性能比的分析和相应的证明。第四章总结与展望。一个执行率为27687的两维调和算法1．1问题的定义第一章简介给定一个输入序列L{X。，X。⋯‰}，蕻中项目X。满足x：∈(0，1)，把序列L中豹所有豹颂西装入容量为1箱子中，求最少的情况下，需要多少个箱子，这就是典型豹一维装箱闻题。众赝爆知，它楚一个NP-hard[2】懑题。医此，探求该问题的近似解怒研究的主