An efficient algorithm for bin stretching
An efficient algorithm for bin stretching
复制标题
DOI：
10.1016/j.orl.2013.03.005
复制
发表时间：
2013-07-01
影响因子：
1.1
通讯作者：
Kotov, Vladimir
中科院分区：
文献类型：
--
作者：
Kellerer, Hans;Kotov, Vladimir
可以打包到 m 个单位大小的箱中的物品序列必须在线分配给箱，以最小化拉伸因子，即，尽可能小地拉伸箱尺寸，以便物品适合箱。我们提出了一种拉伸因子为 11/7 的基本算法，改进了 Cheng 等人最著名的算法。 (2005) [5] 拉伸因子为 1.6。我们的算法使用简单但有效的技术将垃圾箱分组为具有相似结构的批次。 (C) 2013 Elsevier B.V. 保留所有权利。
A sequence of items that can be packed into m bins of unit size has to be assigned online to the bins minimizing the stretching factor, i.e., to stretch the bin sizes as little as possible such that the items fit into the bins. We present an elementary algorithm with stretching factor 11/7 improving the best known algorithm by Cheng et al. (2005) [5] with a stretching factor of 1.6. Our algorithm uses simple but efficient techniques of grouping the bins in batches of similar structure. (C) 2013 Elsevier B.V. All rights reserved.