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

第2 3 卷 第4 期 2 0 0 5 年 1 0月 佳 木 斯大 学 学 报 自 然 科学 版 J o u rna l o f J i a m u s i U n i v e r s i t y N a t u r a l S c i e n c e E d i t i o n V0 1 2 3 N 0 4 Oc t 2 0 0 5 文章缩号 1 0 0 8 一l 4 o 2 2 o o 5 o 4 0 6 0 6 0 4 有色装箱问题的一种新的近似算法 刘春霞 于洪霞 大连理工大学应用数学系 辽宁 大连 1 1 6 0 2 4 摘要 作为经典装箱问题的推广 有色装箱问题在多处理器实时计算机系统的任务调度等实际问 题中有着很强的应 用背景 本文提 出了有色装箱问题 的一种新的近似算法 交叉装箱算法 简称 J C B P 该算法首先对物品按长度进行排列 再从两头交叉进行装箱 实验证明 该算法较其他算法有较好 的装箱效果 并且很多情况下能达到最优解 关键词 装箱问题 近似算法 多处理器调度 中图分类号 T P 3 0 1 文献标识吗 A O 引 言 有色装箱问题是一种带约束的一维装箱问题 它最初在支持容错的多处理器实时计算机系统的任务 调度问题中被提出 有色装箱问题在多处理器任务调度 2 并行处理 资源分配和现实生活中的包装等 问题中有着广泛的应用背景 下面简单介绍一个有色装箱问题的例子 在多处理器实时调度系统中 往往需要将一个任务分割成若干个子任务 为了支持容错 每个子任务 都必须有若干个拷贝 这些拷贝在不同的处理器上运行 以保证处理结果的正确性 现在的问题是 如何分 配这些子任务 使得整个任务在规定的时间内完成 同时使得运行该任务的处理器的数量尽可能少 因为同一个子任务的拷贝必须放在不同的处理器上运行 相当于对同一子任务的每份不同的拷贝赋 予不同的颜色 要求装在箱子中的物品的颜色各不相同 这种带约束的一维装箱问题就是有色装箱问题 解决好有色装箱问题 既是对上述此类问题的良好解决 同时 有色装箱问题的解决 对于一维装箱问 题及其一维装箱问题的其他衍生问题也有很大的帮助 1 相关知识 1 1 经典的一维装箱问题 经典的一维装箱问题是这样描述的 给定 n 个物品的序列 口 a 口 物品 1 s s n 的大小 s 0 1 B 为一个由单位容积的箱子组成的无限序列 我们要求 每一个物品 只能装入到唯一的箱子里 每一个箱子中的数字和不超过 1 如何用最少的单位容积的箱子 装下所有的 物品 用线性规划的方式来描述一维装箱问题如下 n m l n z 2 5 Y l i l n s t s a j x s Y i 1 2 n 收稿 日期 2 0 0 I5 一o 7 一l l 作者简介 刘春霞 1 9 8 1 一 女 山东滨州人 大连理工大学应用数学系 硕士研究生 维普资讯 第 4期 刘春霞 等 有色装箱问题的一种新的近似算法 1 1 2 n Y f 0 或 1 i 1 2 n 0 或 1 1 2 n 其中变量 Y的含义是 Yl f 个 箱 子 被 使 用 1 2 n 1 o 否则 f 1 第 个物品放入第 i 个箱子 1 0 否 则 装箱问题是一个典型的N P 完全问题 引 由于目前N P 完全问题不存在有效时间内求得精确解的算法 因此陆续提出了各种求解装箱问题的近似算法 其中 N F F F B F F F D B F D等是部分著名装箱问题的近似 算法 1 2有色装箱问题 有色装箱问题是 给定 n 个物品的序列厶 a a a a 物品 a i 1 s s n 的大小 s a 0 1 颜色为 c l 1 s i s K 其中物品的颜色数不超过 K K K是常数 B B 为一个由单位 容积的箱子组成的无限序列 我们要求 每一个物品a 只能装入到唯一的箱子里 每一个箱子中的数字和 不超过 1 同一箱子中各物品颜色互不相同 如何用最少的单位容积的箱子 装下所有的物品 有色装箱问题也是 N P 完全问题 因为当 K 时 即物品的颜色数无穷大 每个物品颜色相同的机 会就大大减少 就变成了经典的一维装箱问题了 1 3 解决有色装箱问题的两种算法 文献 5 和文献 6 分别提出了有色装箱问题的 K C A算法和 S c P F A算法 K C 一 A算法 首先把箱子分成 K类 对任何一种颜色 输入序列中第 i 个具有这种颜色的物品只能放 在第 类箱子中 从而保证相同颜色的物品不会出现在同一类箱子中 然后在任何一个箱子类内部 物品 的放置采用近似策略A 我们称这样的算法为以A为基础的K一 分类算法 记为K c A 算法 相应的 当算 法取 F F 算法时 则得到 K C F F 算法 S c P F A算法 首先对输入物品按颜色分类 将相同颜色的物品分成一类 放置时按照相同颜色的物 品首先放置的原则 即颜色 C 的所有物品先分别放在不同的箱子中 然后再处理颜色 C 的所有物品 一 直到所有颜色的物品都放置完毕 在放置物品的过程中 相同颜色的物品必须放在不同的箱子中 在放置 颜色 f 2 的所有物品时 物品的放置采用经典装箱问题的近似算法A 如当算法A 选取的是F F 算法 则得到 S C P F F F 算法 2 交叉装箱算法 2 1 预 备 知识 令 a a a a 为任意给定的 n 个物品的一个序列 物品 a 1 s s n 的大小 s a O 1 颜色为 C 1 s s K 其中物品的颜色数不超过 K K N K是常数 毋表示所用的第 个箱子 箱子S j 的容量均为1 1 2 m 这里 m表示一种给定的装箱方案所需的箱子数 目 易知 不同算法 产生的箱子数目不必相同 令 盯 B 表示箱子 S j 中所有物品的数目 令f S j 表示装入箱子 S j 中的所有 物品的大小之和 口 表示按装箱算法放入第 个箱子的第k 个物品 因此我们有 维普资讯 6 0 8 佳 木 斯 大 学 学 报 自 然 科 学 版 2 0 0 5 年 弓 f B j s 1 2 ra l f B j s a i 2 2 交叉装箱算法 下面给出有色装箱问题的交叉装箱算法 输入 物品序列 L 口 C 口 C 口 c 物品 的大小s 0 1 C 1 c j K 为颜色编号 K为物品的总颜色数 输出 使用的箱子数 m S t e p 1 把物品 口 C 口 C 口 c 按其大小进行非增序排列 不妨设 s 口 s 口 s 口 S t e p 2 首先把 口 C 放入箱子 中 然后从最 右端开始从 右往左依次查看物 品 口 c 口 一 c 一 如果物品 c 1 Z l 满足以下两点 假设 中已经装了P个物品 p i c 与箱 子 中 已 装的P 个 物品 的 颜色 各不相同 i i s 1 一 s 口 t 则将 C 装入箱子 中 并检查下一个物品 如果 口 c 不满足以上两条则直接查看下一个物 品 直到所有物品不能再放入箱子为止 打开新的箱子 B S te p 3 设在第 i 步循环时 打开第 i 个箱子 此时把物品 c i 放人箱子 鼠 中 再从最右端开始从右 往左依次查看装完箱子 一 后剩下的物品 口 啦 c 啦 假设 c 是被查看的物品 假设 中已经装有P个物品 p i c 与箱 子 中 已 装的p 个 物品的 颜色各 不相同 i i s 口 1 一 s 口 则将 c 装入箱子 中 并检查下一个物品 如果 c 不满足以上两条则直接查看下一个物 品 直到所有物品不能再放入箱子为止 打开新的箱子 B 直到把所有物品都放入箱子中 S t e p 4 输出使用的箱子数 m 2 3 实例 例 给定物品序列 L 5 a 8 B 3 B 2 a 6 C 7 B I C 9 A 4 A 2 c 3 C 4 C 括 号中的字母表示颜色值 A表示颜色 A B 表示颜色 B C 表示颜色 C 箱子的长度为 l 0 根据交叉装箱算法 首先将物品按长度从大到小排序 9 A 8 B 7 B 6 C 5 A 4 A 4 C 3 B 3 C 2 A 2 C 1 C 装箱后的结果为 B 9 A I C B 8 B 2 C B 3 7 B 2 a B 4 6 C 3 B B 5 5 a 3 C B 4 A 4 C 从这个例子看出一共使用了6 个箱子 2 4 与其它算法的比较 作者采用随机产生实例的方法对 J C B P算法和 K C A算法 S C P F A算法进行了比较 实验证明交叉 装箱算法比其它算法具有更好的装箱效果 并且对很多情况都能达到最优解 这里仅列举几例进行比较 它们的比较结果如表 1 所示 维普资讯 第 4 期 刘春霞 等 有色装箱问题的一种新的近似算法 表 1 交叉装箱算法与其它算法的比较 图中 K C F F F F D表示分别以F F F F D为基础的 K C算法使用的箱子数 S C P F F F F F D表示分别以 F F F F D为基础的 S C P F 算法使用的箱子数 最优值表示最少使用的箱子数 3 小 结 本文提出了有色装箱问题的一种新的近似算法 交叉装箱算法 并将其与以前文献中提出的 K C A 算法 S C P F A算法进行了比较 实验证明 交叉装箱算法比其它算法使用的箱子数要少 装箱效果较 好 并且很多情况能达到最优值 因此交叉装箱算法是有色装箱问题的一种有效算法 此外 一维装箱问题的其它衍生问题也得到了广泛研究 如最大基数装箱问题 箱子覆盖问题L 7 有 可变容量的装箱问题 8 等 这些衍生问题一方面与一维装箱问题有着密切联系 另一方面又有着更广泛的 实际应用背景 我们未来的工作将继续关注并研究一维装箱问题的各种衍生问题 以期能对实际生活工作 提供更大的帮助 参考文献 1 c L J 8 n d S c h u t i n g a l t I l r rI 8 f o r m u l ti p 咿 删 Iir I g in a b a ld r e a l t i m lv i r o n r n e n t J J o u r n a l A C lV 1 1 9 7 3 l o 1 1 7 4 1 8 9 2 A K h e m k a RK S h r m s u A n o p t i m a l m u h i p r o c e s s o r r e a l ti m e 8 d a e d u l i n g l g o n t h m J J o u r n a l o f P a r a l l d 8 ri d D i s t r i lm t e d n g 1 9 9 7 4 3 1 3 7 4 5 3 Y0 h T h e d e s i l 8 ri d 8 r Ia l s s c h l g a l t l 1f n 8 f o r 嘲l ti m e 8 ri df a u l t to l e n t e o t n p u t e r s y s t e m s P h D d i s s e r t a t i 1 1 V 1 D c p a 血蜘t c 0 S e i mc e U n i v e r s i t y 0 f V i r g iI Ii a V i n g m i a 1 9 9 4 4 lV l R r e y D S J o h m o n C o m p u t e r s 8 ri d I n tr a c t a b i l i ty A G u il d t o t h e T h e o r y o f N P e t 哪e s 8 M Y o r k w H F r e m n 8 ri d c 0 1 9 7 8 5 顾晓东 许胤龙 陈国良 顾钧 有色装箱问题的在线近似算法 J 计算机研究与发展 2 O O 2 3 9 3 3 3 5 3 4 0 6 董一鸿 赵杰煜 带约束的一维装箱问题近似算法的研究 J 计算机工程与应用 2 O O 3 1 8 4 1 4 4 7 J A N S E N K S O L I S O B A R A n a w m g t t i e f h u y y a l ti m e 8 p p l 0 f I s c h e m e f o r b i n x v i n g J T h e o e t l c a l 0 m S c i e n c e 2 O O 3 3 0 6 5 4 3 5 51 8 K A N C J P A R K S L l g o i t h m s f o r t h e v a r i a b l e s i z e d b i n p a c k i I l g p r b l e m J l I 叩e a r I J o u r n a l 0 f O p e r a t i o ml R e B 阻 I c I 1 2 O O 3 1 4 7 3 6 5 3 7 2 A Ne w Ap p r o x i n mt i o n Al g o r i t h m f o r Co l o r i n g B i n P a c k i n g L I U C h u n x i a Y U l g x i a 巾珊玎 t o t A l lp l i e d Ma nt l e s D a l l a n U I l y o t T e d mo l o 1 1 6 0 2 4 C h i n q A b s t r a c t A s o n e o f t h e e o mt r a i n e d b i n p a c k i n g p r o b l e m B P P c o l o r i n g B P P h a s m a n y i mp o r t a n t a p p l i e a t i o m s u c h a s mu l t i p r o c e s s o r r e a l t i me s c h e d u l i n g e t c A n e w a p