论文标题
补充存储问题的完全多项式时间近似方案
A Fully Polynomial Time Approximation Scheme for the Replenishment Storage Problem
论文作者
论文摘要
补货存储问题（RSP）是为确定性需求，多项目库存系统的存储容量需求最小化，其中每个项目都有给定的重新订购尺寸和周期长度。换层只能在周期内的整数时间单元进行。对于恒定的关节周期长度（所有单个周期的长度的最小倍数），该问题被证明是弱的NP硬化。当所有项目具有相同的恒定循环长度时，存在完全多项式时间近似方案（FPTA），但是在单个周期不同的情况下，尚无FPTA。在这里，我们设计了具有不同单个周期和恒定关节周期长度的RSP的第一个已知FPTA。
The Replenishment Storage problem (RSP) is to minimize the storage capacity requirement for a deterministic demand, multi-item inventory system where each item has a given reorder size and cycle length. The reorders can only take place at integer time units within the cycle. This problem was shown to be weakly NP-hard for constant joint cycle length (the least common multiple of the lengths of all individual cycles). When all items have the same constant cycle length, there exists a Fully Polynomial Time Approximation Scheme (FPTAS), but no FPTAS has been known for the case when the individual cycles are different. Here we devise the first known FPTAS for the RSP with different individual cycles and constant joint cycle length.
