الگوریتم کردن فضای حالت برای سیاست دوباره پر کردن چرخه موجودی

In this work we propose an efficient dynamic programming approach for computing replenishment cycle policy parameters under non-stationary stochastic demand and service level constraints. The replenishment cycle policy is a popular inventory control policy typically employed for dampening planning instability. The approach proposed in this work achieves a significant computational efficiency and it can solve any relevant size instance in trivial time. Our method exploits the well known concept of state space relaxation. A filtering procedure and an augmenting procedure for the state space graph are proposed. Starting from a relaxed state space graph our method tries to remove provably suboptimal arcs and states (filtering) and then it tries to efficiently build up (augmenting) a reduced state space graph representing the original problem. Our experimental results show that the filtering procedure and the augmenting procedure often generate a small filtered state space graph, which can be easily processed using dynamic programming in order to produce a solution for the original problem.

Inventory theory provides methods for managing and controlling inventories under different constraints and environments. An interesting class of production/inventory control problems is the one that considers the single-location, single-product case under non-stationary stochastic demand and service level constraints. Such a problem has been widely studied because of its key role in practice. Different inventory control policies can be adopted for the above mentioned problem. For a discussion of inventory control policies, see Silver et al. (1998). One of the possible policies that can be adopted is the replenishment cycle policy, (R,S). A detailed discussion on the characteristics of (R,S) can be found in de Kok (1991). In this policy an order is placed every R periods to raise the inventory level to the order-up-to-level S. This provides an effective means of dampening planning instability (deviations in planned orders, also known as nervousness ( de Kok and Inderfurth, 1997 and Heisig, 2002) and coping with demand uncertainty. As pointed out by Silver et al. (1998, pp. 236–237), (R,S) is particularly appealing when items are ordered from the same supplier or require resource sharing. In these cases all items in a coordinated group can be given the same replenishment period. Periodic review also allows a reasonable prediction of the level of the workload on the staff involved, and is particularly suitable for advanced planning environments and risk management ( Tang, 2006). Under the non-stationary demand assumption the replenishment cycle policy takes the form (R n,S n) where R n denotes the length of the n th replenishment cycle and S n the respective order-up-to-level. In this policy, the actual order quantity for replenishment cycle n is determined after the demand in previous periods has been observed. The order quantity is computed as the amount of stock required to raise the closing inventory level of replenishment cycle n −1 up to level S n. In order to provide a solution for our problem under the (R n,S n) policy we must populate both the sets {Rn|n=1,…,M}{Rn|n=1,…,M} and {Sn|n={1,…,M}{Sn|n={1,…,M}, where M denotes the number of replenishment cycles scheduled over a finite planning horizon of N periods. The problem of populating these sets has been solved to optimality only recently, due to the complexity involved in the modeling of uncertainty and of the policy-of-response. As Silver points out, computing replenishment cycle policy parameters under non-stationary stochastic demand is a computationally hard task (Silver, 1978). Early works in this area adopted heuristic strategies such as those proposed by Silver (1978), Askin (1981), and Bookbinder and Tan (1988). Under some mild assumptions, the first complete solution method for this problem was introduced by Tarim and Kingsman (2004), who proposed a deterministic equivalent mixed integer programming (MIP) formulation for computing (Rn,Sn) policy parameters. Tempelmeier (2007) extended Tarim and Kingsman's MIP formulation in order to consider different service level measures, such as the “fill rate”. Nevertheless, empirical results showed that Tarim and Kingsman's model is unable to solve large instances. Tarim and Smith (2008) therefore introduced a more compact and efficient constraint programming formulation of the same problem that showed a significant computational improvement over the MIP formulation. The constraint programming formulation has been further enhanced by means of dedicated cost-based filtering algorithms developed by Tarim et al. (2009). A stochastic constraint programming ( Tarim et al., 2006) approach for computing optimal (Rn,Sn) policy parameters is proposed in Rossi et al. (2008). In this work the authors drop the mild assumptions originally introduced by Tarim and Kingsman and compute optimal (Rn,Sn) policy parameters. Of course, there is a price to pay for dropping Tarim and Kingsman's assumptions, in fact this latter approach is less efficient than the one in Tarim and Smith (2008). Finally, Pujawan and Silver (2008) recently proposed a novel and effective heuristic approach. In this paper, we build on Tarim and Kingsman's modeling assumptions and we develop a state-of-the-art algorithm for computing optimal (Rn,Sn) policy parameters. Two existing techniques—dynamic programming and state space relaxation—are combined in order to obtain an effective approach for computing (Rn, Sn) policy parameters. Dynamic programming (DP) is an optimization procedure that solves optimization problems by decomposing them into a nested family of subproblems. DP is based on the principle of optimality ( Bellman, 1957 and Dreyfus and Law, 1989) and it has been applied to solve a wide variety of combinatorial optimization problems, as well as optimal control problems. State space relaxation (SSR) considers the DP formulation of a combinatorial optimization problem, and modifies this formulation to obtain a different—and possibly more compact—DP formulation whose optimal solution is a lower bound for the original problem. Christofides et al. (1981) proposed that SSR has been successfully applied to constrained variants of routing problems (see, e.g. Mingozzi et al., 1997 and Focacci and Milano, 2001). Roughly speaking, SSR maps the original state space graph to a new state space graph having a smaller number of vertices, and whose shortest path represents a lower bound for the cost of the shortest path in the original state space graph. In this work, we enhance these known approaches with a novel strategy: we introduce a filtering procedure for the state space graph and an augmenting procedure that is able to build a reduced state space graph for the original problem starting from a filtered state space graph for the relaxed problem. The concept of state space augmentation (Boland et al., 2006) is known in the operations research literature. A dual approach to state space augmentation also exists and is known as decremental SSR (Righini and Salani, 2008). Nevertheless, the idea of filtering a relaxed state space graph is, to the best of our knowledge, a novel contribution. Our experimental results prove the effectiveness of such an approach for computing optimal (Rn, Sn) policy parameters. The paper is structured as follows. In Section 2 we introduce the problem definition and the modeling assumptions adopted in this work. In Section 3 we describe a DP reformulation for Tarim and Kingsman's model. An SSR for this reformulation is presented in Section 4. A procedure for filtering the relaxed state space graph is presented in Section 5. An augmenting procedure for the relaxed state space graph is described in Section 6. An example that demonstrates the algorithm proposed is given in Section 7. Our computational experience and a comparison with the state-of-the-art approaches for computing replenishment cycle policy parameters are discussed in Section 8. In Section 9 we draw conclusions.

We proposed a novel DP approach for computing (Rn,Sn) policy parameters. Our experimental results show that our approach, based on the described filtering algorithm for the state space graph and on the state space graph augmenting procedure, can solve instances over planning horizons comprising hundreds of periods. State space relaxation and state space augmentation are two known strategies in operations research, nevertheless, the idea of filtering a relaxed state space graph is, to the best of our knowledge, a novel contribution. As our computational experience shows, our DP reformulation performs significantly better than the original MIP approach proposed by Tarim and Kingsman and it also beats the state-of-the-art reformulations proposed by Tarim and Smith and Tarim et al. Furthermore our results are not affected by the magnitude of the demand considered in each period.