基于物品移动的局内装箱算法的改进  

Improved Bound of Online Bin-packing Algorithm Based on Move Model

作　　者：杨鼎强[1] 王晨[2] 

机构地区：[1]长沙理工大学计算机通讯工程学院,湖南长沙410076 [2]湖南现代物流职业技术学院信息系,湖南长沙410001

出　　处：《计算技术与自动化》2008年第2期44-48,共5页Computing Technology and Automation

基　　金：国家自然科学基金资助项目(20676154);湖南省教育厅资助科研项目(06C126)

摘　　要：局内装箱问题在多处理器调度、资源分配和日常生活中的计划、包装、调度等优化问题中有着极为重要的应用。提出一个新的局内线性算法MAMOV,算法中采用"物品移动模型",当新物品到达时,允许首次入箱后的固定数目的物品再次移动;证明MAMOV算法的最坏情况渐近性能比1.25,该算法最坏情况渐近性能比低于同类算法最坏情况渐近性能比的下界值。Online bin- packing problem has many important applications such as multiproeessor scheduling, resource allocation, real- world planning, and packing and scheduling optimization problem. A liner space online approximation algorithm is MAMOV （Modified Algorithm for Move model） is presented. This algorithm uses ＂Move model＂ , allows a constant number of elements to move from one bin to another, as a consequence of the arrival of a new input element. Also given is 1.25 asymptotic worst- ease performance ratio, below the past researches asymptotic worst- case performance ratio lower bound.

关 键 词：装箱问题 局内算法 近似算法 复杂性 

分 类 号：TP301.5[自动化与计算机技术—计算机系统结构]