关于带拒绝装箱问题的若干研究

摘要

该文讨论了带拒绝装箱问题,即给定大小一样的一批箱子和许多不可分割的物品,每个物品有大小和罚值,当物品被拒绝时要付出一定的罚值.目标是使所用的箱子数与被拒绝的物品的总罚值之和最小.文中研究了该问题的在线与离线情形,设计了一些近似算法并分析了算法的性能比.全文共分四章.首先第一章是绪论部分,主要介绍了经典装箱问题的有关背景知识和一些已有的研究结果,并列出了许多装箱问题的变形问题,另外还介绍了研究分析算法的准备知识.第二章讲带拒绝装箱问题的引出以及数学模型的建立.第三章设计了求带拒绝装箱问题的最优解的分枝定界法,并在计算机上实现.通过计算结果对算法进行说明分析.还比较了多种近似算法的平均情况的执行结果.最后第四章是后记部分.给出了带拒绝装箱问题目标函数变为箱子剩余容积与被拒绝物品的总罚值之和,原问题就转化为多背包问题了,还对该文作了总结,列出了可进一步研究的问题.

目录

文摘

英文文摘

第一章绪论

§1.1装箱问题

§1.2计算复杂性

§1.3近似算法

第二章带拒绝装箱问题及算法研究

§2.1问题描述与模型建立

§2.2带拒绝装箱问题最优解的下界

§2.3近似算法的设计与分析

第三章数值模拟

§3.1分枝定界法

§3.2计算

第四章后记

参考文献

致谢