应用数学学报
應用數學學報
응용수학학보
ACTA MATHEMATICAE APPLICATAE SINICA
2004年
3期
423-429
,共7页
装箱%变尺寸%核元%在线算法%性能比
裝箱%變呎吋%覈元%在線算法%性能比
장상%변척촌%핵원%재선산법%성능비
本文考虑了一类箱子在线到达的带核元变尺寸装箱问题.假定箱子的尺寸可以是不同的.箱子是在线到达的,仅当箱子到达后其尺寸才知道.给定一个带有核元的物件表,目标是要将表中元素装入到达的箱子中,使得所用的箱子总长最小.我们首先证明了该问题是强NP-Hard,其次分析了经典算法NF(D)和FF(D)的性能界,指出NF(D)和FF(D)算法的性能界可以任意大.最后我们给出了相应的修改算法MNF(D)和MFF(D),证明了它们的性能界都是3,此界是紧的.
本文攷慮瞭一類箱子在線到達的帶覈元變呎吋裝箱問題.假定箱子的呎吋可以是不同的.箱子是在線到達的,僅噹箱子到達後其呎吋纔知道.給定一箇帶有覈元的物件錶,目標是要將錶中元素裝入到達的箱子中,使得所用的箱子總長最小.我們首先證明瞭該問題是彊NP-Hard,其次分析瞭經典算法NF(D)和FF(D)的性能界,指齣NF(D)和FF(D)算法的性能界可以任意大.最後我們給齣瞭相應的脩改算法MNF(D)和MFF(D),證明瞭它們的性能界都是3,此界是緊的.
본문고필료일류상자재선도체적대핵원변척촌장상문제.가정상자적척촌가이시불동적.상자시재선도체적,부당상자도체후기척촌재지도.급정일개대유핵원적물건표,목표시요장표중원소장입도체적상자중,사득소용적상자총장최소.아문수선증명료해문제시강NP-Hard,기차분석료경전산법NF(D)화FF(D)적성능계,지출NF(D)화FF(D)산법적성능계가이임의대.최후아문급출료상응적수개산법MNF(D)화MFF(D),증명료타문적성능계도시3,차계시긴적.
