A Lower Bound and an Efficient Heuristic for Multistage Multiproduct Distribution Systems
针对多阶段多设施纯分销网络中的批量问题，提出一个复杂度为O(rd log r)的算法，利用分解网络得到下界，并给出性能不超过最优解2%的启发式方法。
This paper concerns lot-sizing in a multistage and multifacility pure distribution network. A facility at the end of the distribution network experiences a deterministic and continuous demand. Each facility has an echelon holding cost rate for each item it distributes, and a facility-dependent set up cost. In this paper an algorithm is presented of complexity 0(rd log r) where r is the number of end facilities and d is the maximum depth of the distribution system. The algorithm exploits a lower bound obtained by decomposing the distribution network into facilities-in-series problems. Using a set up cost allocation procedure, the maximum of the continuous solution of the decomposed problem is obtained. This maximizing solution provides the lower bound which is used for solving the distribution problem. This gives a power-of-two heuristic with a worst case performance no more than 2% above optimal.