共查询到20条相似文献,搜索用时 468 毫秒
1.
本文讨论了一类在线变尺寸装箱问题,假定箱子的尺寸可以是不同的.箱子是在线到达的,仅当箱子到达后其尺寸才知道.给定一个带有核元的物品表及其上的核元关系图.我们的目标是要将表中元素装入到达的箱子中,保证任何箱子所装物品不互为核元,即所装物品对应的点所导出的子图是个空图,并使得所用的箱子总长最小.我们证明了该问题是NPHard的,并给出了基于图的点染色、图的团分解和基于背包问题的近似算法,给出了算法的时间复杂度和性能界. 相似文献
2.
J.Csirik与D.S.Johnson针对带k-箱限制的在线装箱问题提出了四种装入和关闭法则,并利用这些法则给出了四种相应的算法.其中BBFk,NkF和ABFk算法的紧界在文[1-3]中分别进行了很好的研究.但对算法AFBk来讲,其紧界仍是一个公开问题.本文给出了AFBk算法性能比的一个上界,即.同时,本文提出了一个新的关闭法则,对AFBk算法进行了修改,使修改后的算法AFBk的性能比不超过1.7(k3) 相似文献
3.
4.
王海明 《高校应用数学学报(A辑)》1997,(3):361-368
讨论部分机器个已安排有工件的情况下的P∥Cmax问题,证明了Multifit算法的最差情况指标满足Rm(MF「k)」∈(1.23,1.275+1/2^k),m≥4。 相似文献
5.
6.
7.
8.
超尺寸物品装箱问题及其算法 总被引:3,自引:0,他引:3
本文探讨一类新装箱问题-超尺寸物品装箱问题。针对实际解决该问题的两涉法,我们提出了一个评价效率更高的目标函数,证明了在此目标函数下两步法的渐近最坏比不小于2,并给出了渐近量坏比与拆分次数的关系。最后本文提出了一种不同于两步法的新在线算法MA,证明了在新目标函数下其渐近最坏比不超过7/4。 相似文献
9.
箱子是在线到达的带核元变尺寸装箱问题 总被引:3,自引:0,他引:3
本文考虑了一类箱子在线到达的带核元变尺寸装箱问题.假定箱子的尺寸可以是不同的.箱子是在线到达的,仅当箱子到达后其尺寸才知道.给定一个带有核元的物件表,目标是要将表中元素装入到达的箱子中,使得所用的箱子总长最小.我们首先证明了该问题是强NP—Hard,其次分析了经典算法NF(D)和FF(D)的性能界,指出NF(D)和FF(D)算法的性能界可以任意大.最后我们给出了相应的修改算法MNF(D)和MFF(D),证明了它们的性能界都是3,此界是紧的. 相似文献
10.
Yong HE Hao ZHOU Yi Wei JIANG 《数学学报(英文版)》2006,22(2):587-594
This paper investigates preemptive semi-online scheduling problems on m identical parallel machines, where the total size of all jobs is known in advance. The goal is to minimize the maximum machine completion time or maximize the minimum machine completion time. For the first objective, we present an optimal semi-online algorithm with competitive ratio 1. For the second objective, we show that the competitive ratio of any semi-online algorithm is at least (2m-3)/(m-1) for any m〉2 and present optimal semi-online algorithms for m = 2, 3. 相似文献
11.
本为1994年全国大学生数学建模竞赛B题(锁具装箱)中关于锁具总数的求解提供一种茼便易行的田论算法.只需具备最基本的图论知识,即可掌握该算法,而运用该算法,计算盘将比现有各种求解算法少得多. 相似文献
12.
13.
现实物流活动中大量存在的食品、药品和危险品等货物的分组包装问题属于带冲突关系的装箱问题(BPPC),其优化目标是在满足货物间冲突限制的前提下完成装箱操作,并最小化使用货箱的数量。本文从实际需求出发,基于货物之间的冲突关系、装箱顺序和货箱容量等约束建立相应的数学规划模型;随后设计了求解BPPC问题的启发式算法,算法通过迭代求解最大团结构实现货物间冲突关系的消去,根据当前货物最大团采用改进降序首次适应算法(FFD)完成货物装箱操作,并通过“洗牌”策略对已有装箱方案进行局部优化;最后,针对Iori算例数据,将以上算法与基于图着色的启发式算法进行比较分析,结果表明,本文算法是求解BPPC问题更为有效的方法。 相似文献
14.
15.
16.
17.
P‖Cmin随机算法研究 总被引:2,自引:0,他引:2
本文研究了P‖Cmin的随机算法及其最坏情况界,我们给出了Pm‖Cmin在线排序问题新的随机上界,并给出了P2‖Cmin的最好随机算法,其最坏情况界为2/3。对P2‖Cmin已知工件加工时间递减半在线模型,我们给出了一最坏情况界为6/7的随机算法并证明了它为最好的。 相似文献
18.
19.
BIN PACKING中γm≤1.20的直接证明 总被引:2,自引:0,他引:2
BINPACKING中γ_m≤1.20的直接证明刘明堂,越民义(中国科学院应用数学研究所,北京100080)ADIRECTPROOFOFTHEINEQUALITYγ_m≤1.20INMULTIPROCESSORSCHEDULING¥LIUMINGTAN... 相似文献
20.
近年来租赁行业竞争日益激烈,租赁企业为了吸引客户有时会开展一些优惠活动。针对这一现状,本文讨论了存在优惠合同时承租方的在线租赁决策问题,其中假设该优惠合同 给予承租方一次以比较优惠的价格连续租赁设备多期的机会。首先,分析了存在优惠合同时的最优离线策略。其次,利用在线算法和竞争比理论分别设计了承租方放弃优惠合同和签订优惠 合同两种情形下的最优在线策略及最优竞争比。最后,通过汽车租赁优惠的数值算例说明选择签订优惠合同是更好的策略,进一步给出了签订优惠合同和购买设备的最佳时间。 相似文献