南昌大学学报（理科版）
南昌大學學報（理科版）
남창대학학보（이과판）
JOURNAL OF NANCHANG UNIVERSITY(NATURAL SCIENCE)
2006年
6期
522-524
,共3页
组合优化%装箱问题%算法分析
組閤優化%裝箱問題%算法分析
조합우화%장상문제%산법분석
A型装箱问题(ASBP)是BP(Backing Problem)的一种变型问题,与经典的BP问题不同的是,在ASBP中物品有两个参数:高度和半径.在装箱过程中,除了要求箱子中所有物品的高度和不大于1之外,还要求后到达的物品放在先到达的物品之上且上层物品的半径不超过下层物品的半径.分析了无穷数目的不同半径和有限数目的不同半径两种情形.对于无穷数目的不同半径的情形,我们证明了NF(Next Fit)、FF(First Fit)、BF(Best Fit)、RBF(Radius Best Fit)和AF(Any Fit)算法的渐近最坏比为无穷大;对于有限数目的不同半径的情形,我们得到了FF、RBF算法的精确渐近最坏界.
A型裝箱問題(ASBP)是BP(Backing Problem)的一種變型問題,與經典的BP問題不同的是,在ASBP中物品有兩箇參數:高度和半徑.在裝箱過程中,除瞭要求箱子中所有物品的高度和不大于1之外,還要求後到達的物品放在先到達的物品之上且上層物品的半徑不超過下層物品的半徑.分析瞭無窮數目的不同半徑和有限數目的不同半徑兩種情形.對于無窮數目的不同半徑的情形,我們證明瞭NF(Next Fit)、FF(First Fit)、BF(Best Fit)、RBF(Radius Best Fit)和AF(Any Fit)算法的漸近最壞比為無窮大;對于有限數目的不同半徑的情形,我們得到瞭FF、RBF算法的精確漸近最壞界.
A형장상문제(ASBP)시BP(Backing Problem)적일충변형문제,여경전적BP문제불동적시,재ASBP중물품유량개삼수:고도화반경.재장상과정중,제료요구상자중소유물품적고도화불대우1지외,환요구후도체적물품방재선도체적물품지상차상층물품적반경불초과하층물품적반경.분석료무궁수목적불동반경화유한수목적불동반경량충정형.대우무궁수목적불동반경적정형,아문증명료NF(Next Fit)、FF(First Fit)、BF(Best Fit)、RBF(Radius Best Fit)화AF(Any Fit)산법적점근최배비위무궁대;대우유한수목적불동반경적정형,아문득도료FF、RBF산법적정학점근최배계.
