有色装箱问题的一种新的近似算法..docVIP

有色装箱问题的一种新的近似算法 刘春霞 于洪霞 (大连理工大学应用数学系 大连市 116024) 摘 要：作为经典装箱问题的推广,有色装箱问题在多处理器实时计算机系统的任务调度等实际问题中有着很强的应用背景.论文提出了有色装箱问题的一种新的近似算法——交叉装箱算法(简称JCBP),该算法首先对物品按长度进行排列,再从两头交叉进行装箱.实验证明,该算法较其他算法有较好的装箱效果,并且很多情况下能达到最优解. 关键词：装箱问题;近似算法;多处理器调度 中图分类号：TP301 文献标识吗：A 引言 有色装箱问题是一种带约束的一维装箱问题,它最初在支持容错的多处理器实时计算机系统的任务调度问题中被提出[1].有色装箱问题在多处理器任务调度[2,3]、并行处理、资源分配和现实生活中的包装等问题中有着广泛的应用背景. 下面简单介绍一个有色装箱问题的例子: 在多处理器实时调度系统中,往往需要将一个任务分割成若干个子任务.为了支持容错,每个子任务都必须有若干个拷贝,这些拷贝在不同的处理器上运行,以保证处理结果的正确性.现在的问题是:如何分配这些子任务,使得整个任务在规定的时间内完成,同时使得运行该任务的处理器的数量尽可能少. 因为同一个子任务的拷贝必须放在不同的处理器上运行,相当于对同一子任务的每份不同的拷贝赋予不同的颜色,要求装在箱子中的物品的颜色各不相同.这种带约束的一维装箱问题就是有色装箱问题. 解决好有色装箱问题,既是对上述此类问题的良好解决,同时,有色装箱问题的解决,对于一维装箱问题及其一维装箱问题的其他衍生问题也有很大的帮助. 相关知识 1.1 经典的一维装箱问题 经典的一维装箱问题是这样描述的:给定个物品的序列,物品的大小,为一个由单位容积的箱子组成的无限序列.我们要求:每一个物品只能装入到唯一的箱子里,每一个箱子中的数字和不超过1,如何用最少的单位容积的箱子,装下所有的物品? 用线性规划的方式来描述一维装箱问题如下: 其中变量的含义是： , , 装箱问题是一个典型的NP完全问题[4],由于目前NP完全问题不存在有效时间内求得精确解的算法,因此陆续提出了各种求解装箱问题的近似算法.其中NF、FF、BF、FFD、BFD等是部分著名装箱问题的近似算法. 1.2 有色装箱问题 有色装箱问题是:给定个物品的序列,物品的大小,颜色为,其中物品的颜色数不超过.为一个由单位容积的箱子组成的无限序列.我们要求: 每一个物品只能装入到唯一的箱子里,每一个箱子中的数字和不超过1,同一箱子中各物品颜色互不相同,如何用最少的单位容积的箱子,装下所有的物品? 有色装箱问题也是NP完全问题,因为当时,即物品的颜色数无穷大,每个物品颜色相同的机会就大大减少,就变成了经典的一维装箱问题了. 1.3 解决有色装箱问题的两种算法 文献[5]和文献[6]分别提出了有色装箱问题的KC-A算法和SCPF-A算法. KC-A算法：首先把箱子分成K类,对任何一种颜色,输入序列中第个具有这种颜色的物品只能放在第类箱子中,从而保证相同颜色的物品不会出现在同一类箱子中.然后在任何一个箱子类内部,物品的放置采用近似策略A.我们称这样的算法为以A为基础的K-分类算法,记为KC-A算法.相应的,当算法取FF算法时,则得到KC-FF算法. SCPF-A算法：首先对输入物品按颜色分类,将相同颜色的物品分成一类,放置时按照相同颜色的物品首先放置的原则,即颜色的所有物品先分别放在不同的箱子中,然后再处理颜色的所有物品,一直到所有颜色的物品都放置完毕.在放置物品的过程中,相同颜色的物品必须放在不同的箱子中.在放置颜色的所有物品时,物品的放置采用经典装箱问题的近似算法A.如当算法A选取的是FF算法,则得到SCPF-FF算法. 交叉装箱算法 2.1 预备知识 令为任意给定的个物品的一个序列,物品的大小,颜色为,其中物品的颜色数不超过.表示所用的第个箱子,箱子的容量均为1,,这里表示一种给定的装箱方案所需的箱子数目.易知,不同算法产生的箱子数目不必相同.令表示箱子中所有物品的数目,令表示装入箱子中的所有物品的大小之和.表示按装箱算法放入第个箱子的第个物品.因此我们有 ; . 2.2 交叉装箱算法 下面给出有色装箱问题的交叉装箱算法： 输入：物品序列,物品的大小,为颜色编号,为物品的总颜色数 输出：使用的箱子数 Step1:把物品按其大小进行非增序排列,不妨设; Step2: 首先把放入箱子中,然后从最右端开始从右往左依次查看物品,如果物品满足以下两点(假设中已经装了个物品)： (i) 与箱子中已装的个物品的颜色各不相同, (ii), 则将装入箱子中,并检查下一个物品