一种松弛的尺寸可变装箱问题及其在线算法

给定物品系列,不同尺寸的箱子依次到达,要求将所有物品装入到箱子中以实现从第一个箱子到最后一个被使用的箱子为止的所有箱子总尺寸最小化.为此给出了6种在线算法,并对这些算法在两种箱子尺寸约束条件下的最坏情形性能和一般情形性能分别进行了研究.理论分析表明最坏情形下6种算法的渐进竞争比在常规约束不小于2,在松弛的约束条件下为无穷;仿真试验表明一般情形下FFD(FirstFitDecreasing)算法最优.     

一种尺寸可变的装箱问题的在线近似算法

用最坏情况绝对性能研究尺寸可变的装箱问题的在线算法,对于两种箱子规格a和b,给出了一种最坏绝对性能比最多是2.75的在线近似算法.     

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

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

带核元的带拒绝装箱问题

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

最小费用箱子覆盖问题及其算法

提出了一种有实际背景的最小费用箱子覆盖问题──每个物品有长度和费用2个参数.针对局外最小费用箱子覆盖问题,给出了一个求解该问题的最坏情况渐近性能比为1/2算法C-FF1.同时给出了一个求解该问题的局内算法C-FF2,其绝对性能比为1/2,并证明了不存在绝对性能比大于1的算法.     

在线A形装箱问题: 模型及算法研究

A形装箱问题是由生产实际引发的一个新的数学模型,它是经典一维装箱问题的一种变形--每样物品有高度和半径两个参数.把装箱问题的经典算法推广到在线A形装箱问题,并分别从最坏情形分析与数值模拟两方面对算法进行了比较,得到了不同而且有趣的结果. 证明了 First Fit算法的渐近竞争比为2, 而其它在线启发式算法如Next Fit, Worst Fit, Best Fit(BF), Almost Worst Fit, Harmonic的渐近竞争比皆为无界; 通过数值模拟,在平均意义下BF的性质最好.     

带机器准备时间的同类机在线与半在线排序问题

研究带机器准备时间的m台同类机(uniform machines)在线和半在线排序问题，目标函数为极小化最大机器(工件)完工时间。对于在线情形，证明了LS算法的最坏情况为ρ=｛（1 √5）/2，m=2,1 √2m-2/2,m≥3，并且当m=2，LS算法是最好的近似算法；当m=2，3，…，6时界是紧的，特别地，当s1=s2=…=sm-1,sm≥l时，证明了LS算法的最坏情况界为ρ=｛（1 √5）/2，m=2,3-4/m 1,m≥3，而且界是紧的；对于已知加工时间递减的半在线排序问题，证明了LS算法的最坏情况界为2—2/(m 1)。     

关于恶化工件的单机在线调度最优算法的另一种证明

对于一台机器上在线调度简单恶化工件的最小化总完工时间问题,Liu在文献(Theoretical Computer Science 445(2012)75-81)中提出了一个最优在线算法DSGR,此算法在最坏情况下的比率是1+α_(max),其中α_(max)=majxα_j是所有工件的最大恶化率.对于这个结果我们给出了另外一种简单的证明.     

箱子装载问题的算法研究

1　引言　　设有ｎ件物品 ,每件物品的体积分别为ｓ1,ｓ2 ,… ,ｓｎ,且 0 <ｓｉ≤ 1(ｉ =1,2 ,… ,ｎ) .现有一批箱子 ,每只箱子的容量为一个单位 ,现在的问题是能够容纳这ｎ件物品的箱子至少需多少只 ?此问题为著名的ＮＰ复杂问题 ,迄今在多项式时间内尚无求解的办法 .但可用近似算法求解 ,使结果接近最优解 .对于此问题 ,有 4种流行的求解算法 :( 1)最先匹配法 (ＦｉｒｓｔＦｉｔ ,ＦＦ) ;( 2 )最优匹配法 (ＢｅｓｔＦｉｔ ,ＢＦ) ;( 3)最先匹配递减法 (ＦＦＤ) ;( 4 )最优匹配递减法 (ＢＦＤ) .这 4种算法的时间复杂度均为Ｏ(ｎ×ｌｏｇ(…     

流水作业问题的一个启发式算法

讨论具有延迟时间的流水作业问题,并提出了解决该问题的一种启发算法,证明了其最坏性能比是（m 1）/2,并且上界是紧的,特别当m=2,即两台机器上具有延迟时间的流水作业问题时,其最坏性能比是3/2,最后将所得结论推广到FmID2问题,即加工时间相等且延迟时间只取两上值的流水作业问题,其最坏性能比也是m 1/2。     

谁发明了集装箱运输

不知道大家注意过海港码头的货物装卸吗？宽阔的货场上，一个个巨大的金属箱子整齐地排列着，拖车拖着这些巨型箱子，通过码头的吊桥，把箱子运送到货轮上去，或者用起重机把箱子吊起，稳稳地放进船仓。也许你会觉得这很正常，事实上，这种集装箱货物装卸方法经历了漫长的创新历程。     

集装箱船全航线预配优化模型与算法研究

集装箱船全航线配载问题属于NP-hard问题.为降低问题求解难度,提出了解决全航线配载问题的分解算法,即将配载问题分解为Bay位选择和Bay位中集装箱排序两个子问题.将Bay位选择看成是"装箱问题",以不同属性集装箱作为待装"物品",以船舶上的Bay位为箱子,以最优装箱(即使用箱子的数量最少)及集装箱在每个港口的倒箱数量最少为目标进行总布置配载;Bay位中集装箱排序是将Bay位选择阶段分配到不同Bay位的集装箱按某些规则进行排序,确定其在Bay位中的具体箱位.主要研究了Bay位选择阶段的模型及算法.实例模拟结果表明该方法可行,为集装箱船全航线配载优化提供了一个实用的模型.     

基于任务映射与缓存划分的WCRT优化方法

为了降低系统最坏响应时间（WCRT）,提出了一种基于任务映射与缓存划分的WCRT优化方法.该方法分为两个阶段,第一阶段采用任务在最佳缓存容量下的最坏情况执行时间（WCET）进行任务映射;第二阶段以满足系统的缓存容量约束为原则对映射后的任务进行缓存容量回收及任务映射的再调整,同时在两个阶段均兼顾系统的负载均衡.实验结果表明,该方法在降低系统最坏响应时间及执行效率方面都能获得良好的效果,系统最坏响应时间相比GCP算法平均降低了6.7%,相比ILP方法有更快的执行效率.      

一种用遗传算法求解装箱问题的新编码方法

装箱问题在实际生产中应用非常广泛,然而在传统装箱问题中箱子的容量是固定的,并没有考虑多种容量箱子的问题;文章提出一种用遗传算法求解装箱问题的新编码方法,并用单亲遗传算法实现;这种算法和混合遗传算法相比,有编码简单、收敛快及实现容易等优点。     

车载电子系统中场景感知的实时性分析的优化

提出基于场景的车载电子系统实时性分析,并设计了一种基于日志信息的自动场景拆分算法,通过以场景局部的最坏情况替代系统全局的最坏情况作为实时性分析的基础来优化实时性分析的结果,以提高系统的可扩展性和降低系统成本.仿真实验证明了该方法的有效性.     

原子核是“黑箱”

科学的研究对象许多是“黑箱”。何为黑箱?世界上有三种箱子,一种是白箱,例如金鱼缸,玻璃透光,人们对金鱼的活动一目了然。第二种是灰箱,箱子灰蒙蒙的,能透出一些光,或者有的部分透光,有的部分不透光,例如仪表、手表、观察者可以从表盘上了解数据,但仪表、     

“巾箱”考略

版本学中“巾箱本”之“巾箱”何指？有人认为是放置手巾的箱子，但在史书中却未发现证据。从二十五史中书籍材质、装帧形式的变迁历史考证“巾箱本”中“巾箱”的来历，“巾箱”内装物品种类丰富，形积较小，而多为书籍，所以就成为了版本学中“巾箱本”的省称，“巾箱”还可引申为“学问著述”之义。     

基于拍卖的电子商务动态定价研究

产品定价是企业最重要的决策之一。随着电子商务的兴起,网上商品的销售价格不再是固定不变,动态定价已经成为网络驱动的新经济特征之一。在线拍卖是电子商务动态定价中最常用的一种形式。传统上的多物品拍卖研究是建立在拍卖方拍卖商品的数量或竞标方商品需求的数量是固定不变的假设基础之上,这种假设不能满足实际应用的需要。文中摈弃这种假设,论述了网上竞标方需求数量不定前提下同质多物品拍卖动态定价模型,并分析了基于Agent的算法实现。     

一种Douglas—Peucker加速算法

本文分析了Douglas—Peucker（DP）算法的复杂度,表明在最坏情况下为O（n^2）其中n为矢量压缩前的顶点数。接着,提出了一种基于路径凸壳的算法,在最坏情况下的复杂度仍为O（nlog2）,与常规DP算法在最优情况下的复杂度相同。     

条条道路通罗马

[题目]每个箱子装袋牛奶,一个奶站有袋牛奶。用个箱子够装吗?[分析与解]这是一个份总关系的数学问题,里面涉及的数量只有每份数、份数、总数,而且它不必得出具体数量,只要进行判断。比较每份数、份数、总数,就可以作出判断了。第一种方法,比较总数,进行判断。=袋<袋,说明用个箱子不够装。