Pm||C_(max)问题的算法A_(KK)的一个改进的最坏情况性能比(英文)

本文考虑的是平行机排序问题Pm||Cmax.对此问题Knuth和Kleitman给出了一个近似算法AKK,Graham证明了此算法的最坏情况性能比不大于1+(1-1/m/1+|k/m|),而且当k(?)0(modm)时这个界是紧的.在本文中我们给出了此算法的一个改进的最坏情况性能比:1+max{1-1/m/1+k1+1/m,1-1/m-k2/1+k1},其中k1和k2为非负整数且k1m+k2=k.本文证明了当k2≠0时,它好于Graham的结果,同时我们给出了两个实例说明这个界是紧的.

机器不同时开工排序问题算法A_(KK)的最坏情况性能比

对于经典排序中的同型机(identical machines)排序问题Pm||Cmax,1969年Graham根据Kleitman和Knuth的建议提出著名的近似算法——算法AKK。2005年李红英等对于算法AKK提出改进的最坏情况性能比。机器不同时开工排序问题Pm,ai||Cmax是经典的同型机排序问题的推广,是一种新型排序。把算法AKK用到机器不同时开工排序问题Pm,ai||Cmax上去,得到新的最坏情况性能比,并把此最坏情况性能比与Graham得到的和李红英等人得到的最坏情况性能比进行了比较。

P_m,a_i‖C_(max)问题的A_(kk)算法的最坏情况性能比

讨论任务的加工是不可中断,机器速度相同且机器具有不同开始加工时间的排序问题,目标函数是极小化最大完工时间.对于一般情况,给出了关于Akk算法的最坏情况性能比.

有元素类型约束的k-划分问题研究

研究有元素类型约束且每个元素权重为正数的κ-集合划分问题,元素类型约束指κ-划分后每个集合所包含的元素的类型均不同,该问题是对κ-划分问题(κ-partitioning problem)的一个拓展,在一人可拥有多技能执照的行业有广泛的应用背景,提出基于LPT算法思想的贪婪算法,并得出以下结论:κ≤2,该算法给出最优解:κ>2,最坏情况下的性能比为2-m^(-1),这里m指待分配集合的数量。

受启动空间约束的装箱问题

提出了一种带有启动空间的约束装箱问题(start-up bin packing problem,简称SBPP),即不同类型的物品放入同一箱子中需要一个启动空间.该问题在工作分配、任务调度和日常生活中的包装等问题中有着广泛的应用背景.给出了一个求解SBPP的线性脱线算法C-NF,其最坏情况渐近性能比为2,与启动空间的大小无关.对该算法的平均性能进行了实验分析.另外,还分析了SBPP的在线特性,指出大量的经典在线装箱算法应用于SBPP都不存在确定的最坏情况渐近性能比,也给出了一种具有确定的最坏情况渐近性能比的在线算法.

受位置约束的有色装箱问题

作为对有色装箱问题的推广,提出了一种受位置约束的有色装箱问题(longest item at the bottom coloring bin packingproblem,LIBCBPP),即在有色物品的装箱过程中,要求重(长)的物品置于轻(短)的物品下方。该问题在任务调度和日常生活中的运输等问题中有着广泛的应用背景。给出了一个求解该问题的近似KC-LIBFF算法,分析其最坏情况渐进性能比为2,并给出了相应的实验结果。

局内装箱算法综述

系统地介绍了局内装箱算法,归纳了其发展过程中的各种改进如数据分配模型、箱的划分等。阐述了该算法在工作分配、任务调度以及日常生活中的计划、包装、调度等计算机工程领域的应用。最后,对局内装箱算法提出了进一步的研究方向。

带启动重量的脆度装箱问题

讨论如下定义的带启动重量的脆度装箱问题:设有许多等长的一维箱子,给定一个物品集,每个物品有2个参数(脆度和重量),若箱子是首次装入物品,则需要添加额外的启动重量,在装箱的过程中要保证每个箱子的启动重量和所装物品重量之和不能超过该箱子内物品的最小脆度,问怎样安排物品使所用箱子数最小.该问题是一个新的组合优化问题,来源于CDMA蜂窝通信系统中的信道分配.本研究给出了一个求解该问题的线性脱线算法C-NFI,分析了其最坏情况渐进性能比为2,并给出了相应的试验结果.

带核元的带拒绝装箱问题

讨论了如下定义的带核元带拒绝装箱问题:设有许多等长的箱子,给定一个带核元的物品集,每个非核元有2个参数:大小和罚值.非核元物品可以放入箱子也可被拒绝放入箱子.如果某物品被拒绝放入箱中,则产生惩罚值,同时要求核元不允许被拒绝且每只箱子中所装核元个数不超过1,问怎样安排物品使所用箱子数与未装箱的物品总罚值之和最小.该问题是一个新的组合优化问题,在多处理器任务调度及内部互联网信息管理等问题中有着广泛的应用背景.提出了一个求解该问题的局外近似算法,分析其最坏情况渐进性能比为2,并给出了相应的实验结果.

基于LIB的有色箱覆盖问题

提出了如下定义的受位置约束的有色箱覆盖问题,即在有色物品的箱覆盖过程中,要求重(长)的物品置于轻(短)的物品下方。该问题是一个新的组合优化问题,来源于多处理器任务调度。给出一个求解该问题的局内近似算法KC-LIBFF算法,分析其最坏情况渐进性能比为0,并给出了相应的实验结果;进一步对求解该问题的局内算法性能比的下界进行了讨论。

互联网信息管理中的带拒绝装箱覆盖问题

作为对装箱覆盖问题的推广,提出了带拒绝的装箱覆盖问题:设有许多等长的一维箱子,给定一个物品集,每个物品有两个参数:长度和费用。物品可以放入箱子也可被拒绝放入箱子。每个物品只准放入一只箱子中,每只箱子中的物品容量总和至少为箱子容量,一旦箱子中的物品长度达到要求则需启用新箱。如果物品被放入箱中,则产生费用。该问题是一个新的组合优化问题,在内部互联网信息管理等问题中有着广泛的应用背景。给出了一个求解该问题的局外近似算法C-FF,分析其最坏情况渐进性能比为1/2,并给出了相应的实验结果。

带拒绝箱覆盖问题的局内算法

作为对装箱覆盖问题的推广,提出带拒绝的装箱覆盖问题。设有许多等长的一维箱子,给定一个物品集,每个物品有两个参数:长度和费用。物品可以放入箱子也可被拒绝放入箱子,每个物品只准放入一只箱子中,每只箱子中的物品容量总和至少为箱子容量,一旦箱子中的物品长度达到要求则需启用新箱。如果物品被放入箱中,则产生费用。该问题是一个新的组合优化问题,在内部互联网信息管理等问题中有着广泛的应用背景。给出一个求解该问题的局内近似算法C-FF,分析其最坏情况渐近性能比为1/2,并给出了相应的实验结果。