多约束的箱子大小可变的装箱问题

作为经典装箱问题的扩展,带有约束条件的装箱问题有着很强的应用背景。从钢铁公司板坯入库引发的装箱问题中,物品除了重量这一参数,还引入了特性和种类等参数。将板坯入库归结为多约束的箱子大小可变的装箱问题后,建立了数学模型,将经典装箱算法进行了推广,构建了新的启发式算法A,它对输入物品按特性进行预处理,再进行装箱。理论分析了NFD,FFD,算法A的最坏情况的性能,并对这三种算法进行了数值模拟,得出在相关特性均匀分布下,算法A的性能最好。

Multi-constrained Variable-sized Bin Packing Problem

As the extension of classical bin packing problem,constrained bin packing problem has many important applications.In this bin packing problem extended from slab loading problem in steel enterprise,item not only has the parameter about weight,but also has the parameters about the custom property and type.This slab loading problem is reduced to MVBPP,and math model is established.The classical algorithms are used,and a new heuristic algorithm is presented,in which inputs are pre-process by the custom property of item before packing.The competitive ratios of NFL,FFD,and algorithm A in worst-case are analyzed.By comparing the performance of three algorithms with numerical experiments under the conditions which the values of property are uniform,algorithm A outperforms any others.