A comparison of inventory replenishment heuristics for minimizing maximum storage
A comparison of inventory replenishment heuristics for minimizing maximum storage
复制标题
用于最小化最大存储量的库存补货启发式比较
DOI：
--
复制
发表时间：
1998
期刊：
影响因子：
--
通讯作者：
Nicholas G. Hall
中科院分区：
文献类型：
--
作者：
Nicholas G. Hall
概要摘要考虑最小化每个周期补充多个物品所产生的最大存储需求的问题。假设需求已知且恒定，并且不允许积压。与之前的模型相比，补货可能仅在 k 个离散时间点发生。我们证明这个问题对于固定 k 来说是二元 NP 困难问题。因此，描述了基于最佳连续时间解的舍入的自然启发式。此启发式提供的最坏情况性能比为 1 + C/k/k，其中 C 是数值常数，且 1/2 < C < 2。借用多处理器调度的启发式提供的最坏情况性能比为 2。广泛的计算测试表明，平均而言，启发式提供的解决方案非常接近最优值。
SYNOPTIC ABSTRACTConsider the problem of minimizing the maximum storage requirement resulting from the once-per-cycle replenishment of several items. Demand is assumed to be known and constant, and no backlogging is permitted. By contrast with previous models, replenishment may take place only at k discrete points in time. We prove that this problem is binary NP-hard for fixed k. Consequently, a natural heuristic based on the rounding of optimal continuous time solutions is described. This heuristic provides a worst case performance ratio of 1 + C/k/k, where C is a numerical constant, and 1/2 < C < 2. A heuristic borrowed from multiprocessor scheduling provides a worst case performance ratio of 2. Extensive computational testing indicates that the solutions delivered by the heuristics are, on average, very close to optimal in value.