装箱问题是组合优化的经典问题之一,在近似算法和在线算法领域有重要地位.自从David Johnson关于装箱问题的博士论文1973年诞生以来,装箱问题的相关模型和算法研究便层出不穷.本文讨论了以下三类这样的问题.(一)最小数目机器的排序问题：给定无限数目的相同的机器,以及一个工件集L={J1,J2,…,Jn}.每个工件Ji都有一个到达时间ri,一个完工期限di和一个加工时间pi,其中ri,di,pi都是非负数.工件Ji可以记为三元组(ri,di,pi)问题的目标是把所有的工件安排在最小数目的机器上,并且使得每个工件的开工时间不早于它的到达时间以及完工时间不晚于它的完工期限.当所有工件的到达时间相同并且完工期限也相同的情形下,这时该问题就是经典的一维装箱问题.所以我们可以把这个问题看作是装箱问题的推广形式Cieliebak等人[4]设计了一个近似算法GBF,并且证明了：当所有工件的加工时间时间都相同的情形下,GBF的渐近近似比至多为9.他们还对到达时问都相同的情形给出了一个渐近近似比至多为4.6的近似算法DBF.我们分析了这两种特殊情形.对于所有工件加工时间都相同的情形,我们给出了相对于DBF更为简单的一个近似算法,并且证明了2是这个算法的紧的绝对近似比；而对于到达时间都相同的情形,我们改进了Cieliebak等人的证明,得到了结论：GBF的绝对近似比不超过6,另外我们还给出一个绝对近似比为4的例子.(二)装箱博弈问题：在一个装箱系统中,每个物品(或用户)都是自利的并且它们之间互不合作,每个物品都希望最优化自己的费用,其中箱子的费用由该箱子内的物品按照它们的尺寸成比例分担.如果某种装箱方案中的所有物品都不想单独移动,(即如果其它物品不移动而仅有它移动,它的分担费用不会减少),则这种方案是一个纳什均衡Bilo[2]证明了纳什均衡所用箱子数与最优装箱所用箱子数的最坏比值介于1.6和1.667之间(这个比值我们称之为最坏均衡近似比).我们改进了他的结果,证明了这个比值的范围介于1.6416和1.6575之间.我们而且还把Bilo的结论推广到带参量形式下的装箱博弈,即对每个物品的尺寸都不超过某个参量的情况下,我们分别给出了最坏均衡近似比的一个上界和一个下界Bilo在文献[2]中说明了：从任意一种可行的装箱开始,我们总能通过有限步的移到(移动的次数可以由一个指数界定)得到一个纳什均衡.所以总存在一个最优的装箱是纳什均衡,因而,求解最好的纳什均衡是NP-困难的.然而求解一个纳什均衡是否是困难的却是一个未解问题.在里我们给出了一个寻找纳什均衡的多项式时间算法RFFD,从而解决了这个问题.(三)带有优先序的装箱问题：给定一个有限的任务集L以及L上的一个偏序关系(即为优先关系),我们希望找到L的一个有序的划分.我们这里考虑了两种优先序装箱问题.对于任意两个具有优先顺序的物品a(?)b,如果b不允许安排a在所在的箱子之前的箱子,则是(?)装箱问题；如果b只能安排a所在的箱子之后的箱子,则是(?)装箱问题.对于(?)装箱问题,Wee and Magazine[33]证明了FF所导致的算法GFF的绝对近似比等于2.我们把这个结论推广到了带参量的形式(下面的x均是指所有物品的尺寸均不超过x)：如果(?)≤x≤1,则RGFF∞=2；如果1/(k+1)≤x＜1/k(k≥2)则RGFF∞=1/(1-x)我们还证明了(?)装箱问题的任意在线算法的渐近近似比不会小于2.对于(?)装箱问题,文献[12]给出了FF所导致的算法GFF的渐近近似比的估计.我们同样地把他们的结论推广到了带参量的形式：如果(?)<x≤1,则RGFF∞=2.7；如果1/(k+1)＜x≤1/k(k≥2),则RGFF∞=2+1/k我们证明了(?)装箱问题的任意在线算法的渐近近似比不会小于2.6910.上述三类问题分别在正文的第二章到第四章中详细介绍.第一章将概述装箱及其相关问题.