【摘 要】
：
装箱问题是组合优化的基本问题之一,有着广泛的实际背景.从七十年代至今,人们对经典装箱问题及其多种形式的扩展问题做了大量研究.由于其中绝大部分问题都是NP-hard,构造、分
论文部分内容阅读
装箱问题是组合优化的基本问题之一,有着广泛的实际背景.从七十年代至今,人们对经典装箱问题及其多种形式的扩展问题做了大量研究.由于其中绝大部分问题都是NP-hard,构造、分析启发式算法成为一个重要的研究方向.该文探讨了两类有实际应用背景的新的扩展问题,构造了启发式算法并从最坏情形分析的角度分析、比较了算法的性能.该文由四章组成.第一章是装箱问题一些主要研究结果的综述.第二章研究了超尺寸物品装箱问题.在超尺寸物品装箱问题中,物品的尺寸可以大于最大箱子的尺寸而且物品可以在限定拆分次数的条件下按任意比例拆分.分析了目前在实际生产中解决该问题所普遍采用的一类算法——两步法,证明当采用经典目标函数并且拆分次数不超过2时,第二步采用FFDLR算法的两步法TFR的渐近最坏比为3/2.进而针对超尺寸物品装箱问题提出了一种评价效率更高的目标函数,证明了在此目标函数下当物品的尺寸可以任意大时最优两步法TOPT的渐近最坏比为2,并给出渐近最坏比与拆分次数的关系.最后提出了一种不同于两步法的新的在线算法MA,证明了在新目标函数下其渐近最坏比为7/4.第三章研究了A形装箱问题.
其他文献
该文研究文[7]中提出的一般冲击模型的非参数统计推断问题.首先由Wald定理得到系统能承受的最大冲击强度Z的表达式,然后在随机截尾数据下,利用计数过程理论建立了冲击间隔Y的
该文在深入钻研逻辑代数创始人的原著并广泛查阅、分析二次文献的基础上,对于数理逻辑发展史上的一个重要事件——逻辑代数的产生进行了系统的研究,包括给出逻辑代数的创立背
请下载后查看，本文暂不支持在线获取查看简介。
Please download to view, this article does not support online access to view profile.
该文通过讨论吴方法的一些性质(比如所求得的扩展特征列的系数界)和模p映射下扩展特征列计算的性质,论证了用模算法求扩展特征列的可行性;给出了判定多项式属于理想的一个等
乡镇初中数学学困生的形成由学生的小学数学基础差,初中数学内容的加深,更加使学生缺乏学习热情和兴趣,缺乏科学的学习方法,缺乏独立思考的能力、家庭、社会、教师等几方面因
该文以J.M.Martire和L.T.Santos(1998)提出的一种递推二次规划为蓝本,将其与信赖域方法有机地结合起来,产生一种新算法,通过新引进和变量y对原递推二次规划方法和信赖与方法
该文讨论广义IMBq方程、广义Benney-Luke方程和广义双耗散方程的Cauchy问题.在一定的条件下研究这些Cauchy问题解的整体存在性,唯一性和正则性,并给出解发生焊破的充分条件,
模糊拓扑线性空间是将分明拓扑学，拓扑线性空间理论，格论与模糊数学理论进行有效的结合而诞生的一门新的学科。与分明的拓扑线性空间相比，模糊拓扑线性空间有着丰富的内容体系和
DNA序列的数据压缩是一项非常艰苦且极具挑战性的任务.它对基因序列的数据储存、DNA的序列分析以及研究基因组的进化关系等方面都有着非常重要的意义.基于颜色信息的渐进编码