Solving the Joint Replenishment Problem with Warehouse-Space Restrictions Using a Genetic Algorithm

運用遺傳演算法求解倉儲空間限制之合併補貨問題

10.29977/JCIIE.200703.0004

姚銘忠(Ming-Jong Yao)

存貨 ； 合併補貨問題 ； 排程 ； 遺傳演算法 ； 倉儲空間 ； Inventory ； joint replenishment problem ； scheduling ； genetic algorithm ； warehouse space

工業工程學刊

24卷2期（2007 / 03 / 01）

128 - 141

英文

本研究為合併補貨問題的延伸，其增加倉儲空間限制的考量。這個問題主要關切的是在所謂的二冪策略(power-of-two policy)下，決定各種產品的補貨批量，在可以產生一個（不超越倉儲空間限制的）可行補貨排程的前提下，使得平均總成本達到最小。為了有效求解本問題，本研究提出一個複合式的遺傳演算法(hybrid genetic algorithm)。我們運用遺傳演算法多維度搜尋的能力找尋候選解答，並運用一個啓發式演算程序測試候選解答是否可以產生可行的補貨排程。經由我們的數據實驗顯示，本研究所提出的複合式的遺傳演算法，可以迅速地求解考量倉儲空間限制之合併補貨問題，故其可以作為運籌經理人員有效的決策輔助工具。

This study is an extension of the Joint Replenishment Problem (JRP) that takes into accounts warehouse-space restrictions. The focus of this study is to determine the lot size of each product under power-of-two policy to minimize the total cost per unit time and to generate a feasible replenishment schedule of multiple products without exceeding the available warehouse-space. In order to solve this problem, we propose a hybrid genetic algorithm (HGA). We utilize the ability of multi-dimensional search of GA to obtain candidates in the solution space, and test the feasibility of any candidate using the proposed heuristics. By our numerical experiments, we demonstrate that the proposed HGA could effectively solve the JRP with warehouse-space restrictions. Therefore, it could serve as an effective decision-support tool for the logistic managers.

1. Yao, M.J.,S.E. Elmaghraby,I.C. Chen(2003).On the feasibility testing of the economic lot scheduling problem using the extended basic period approach.Journal of the Chinese Institute of Industrial Engineering,20,435-448.
   連結：
2. Aksoy, Y.,S. Erenguc(1988).Multi-item inventory models with coordinated replenishments: a survey.International Journal of Production Management,8,63-73.
3. Arkin, E.,D. Joneja,R. Roundy(1989).Computational complexity of uncapacitated multi-echelon production planning problems.Operations Research Letters,8,61-66.
4. Bean, J.C.(1994).Genetic algorithm and random keys for sequencing and optimization.ORSA Journal on Computing,6,154-160.
5. Boesel, J.,B.L. Nelson,N. Ishii(2003).A framework for simulation-optimization software.IIE Transactions,35,221-229.
6. Cormen, T.H.,C.S. Leiserson,R.L. Rivest(1993).Introduction to Algorithms.New York City:McGraw-Hill.
7. Dellaert, N.,J. Jeunet,N. Jonard(2000).Genetic algorithm to solve the general multi-level lot-sizing problem with time-varying costs.International Journal of Production Economics,68,241-257.
8. Fujita, S.(1978).The application of marginal analysis to the economic lot size scheduling Problem.AIIE Transactions,10,354-361.
9. Geng, P.C.,R.G. Vickson(1988).WRLSP: A single-machine, warehouse restricted lot scheduling problem.IIE Transactions,20,354-359.
10. Goyal, S.K.(1974).Determination of optimum packaging frequency of items jointly replenished.Management Science,21,436-443.
11. Goyal, S.K.(1973).Economic packaging frequency for items jointly replenished.Operations Research,21,644-647.
12. Goyal, S.K.,A.T. Satir,(1989).Joint replenishment inventory control: deterministic and stochastic models.European Journal of Operational Research,38,2-13.
13. Graham, R.L.(1969).Bounds on multiprocessing timing anomalies.SIAM Journal on Applied Mathematics,17,416-429.
14. Haji, R.,M. Mansuri(1995).Optimal common cycle for scheduling a single-machine multiproduct system with a budgetary constraint.Production Planning Control,6,151-156.
15. Hall, N.(1988).A multi-item EOQ model with inventory cycle balancing.Naval Research Logistics,35,319-325.
16. Hunter, A.(1998).Crossing over genetic algorithms: the Sugal generalized GA.Journal of Heuristics,4,179-192.
17. Jackson, P.,W. Maxwell,J. Muckstadt(1985).The joint replenishment problem with a powers-of-two restrictions.IIE Transactions,17(1),25-32.
18. Johnson, D.S.,C.R. Aragon,L.A. McGeoch,C. Schevon(1989).Optimization by simulated annealing: an experimental evaluation|part I: graph partitioning.Operations Research,37(6),865-892.
19. Khouja M.,Z. Michalewicz,M. Wilmot(1998).The use of genetic algorithms to solve the economic lot size scheduling problem.European Journal of Operational Research,110,509-524.
20. Kimms, A.(1999).Genetic algorithm for multi-level, multi-machine lot sizing and scheduling.Computers and Operations Research,26,829-848.
21. Lee, F.C.,M.J. Yao(2003).A global optimum search algorithm for the joint replenishment problem under power-of-two policy.Computers and Operations Research,30,1319-1333.
22. Lin, Y.F.,M.J. Yao(2004).the 33rd International Conference on Computers and Industrial Engineering.Korea:Jeju Island.
23. Marzouk, M.,O. Moselhi(2003).Constraint-based genetic algorithm for earthmoving fleet selection.Canadian Journal of Civil Engineering,30,673-683.
24. Murthy, N.N.,W.C. Benton,P.A. Rubin(2003).Offsetting inventory cycles of items sharing storage.European Journal of Operational Research,150,304-319.
25. Park, K.S.,D.K. Yun(1985).Optimal scheduling of periodic activities.Operations Research,33,690-695.
26. Pinedo, M.(1993).Scheduling: Theory, Algorithms, and Systems.Englewood Cliffs, NJ:Prentice-Hall.
27. Sarker, R.,C. Newton(2002).A genetic algorithm for solving the economic lot size scheduling problem.Computers and Industrial Engineering,42,189-198.
28. Syswerda, G.(1989).Proceedings of the Third International Conference on Genetic Algorithms.Fairfax, VA, USA:George Mason University.
29. van Eijs, M.J.G.(1993).A note on the joint replenishment problem under constant demand.Journal of the Operational Research Society,44,185-191.
30. Viswanathan, S.(1996).A new optimal algorithm for the joint replenishment problem.Journal of the Operational Research Society,47,936-944.
31. Wildeman, R.E.,J.B.G. Frenk,R. Dekker(1997).An efficient optimal solution method for the joint replenishment problem.European Journal of Operational Research,99,433-444.
32. Yao, M.J.(2001).The peak load minimization problem in cyclic production.Computers and Operations Research,28,1441-1460.
33. Zoller, K.(1977).Deterministic multi-item inventory system with limited capacity.Management Science,24,451-455.

1. Yao, Ming-Jong,Chang, Yu-Jen(2008).SOLVING THE ECONOMIC LOT SCHEDULING PROBLEM WITH IDENTICAL FACILITIES IN PARALLEL USING GENETIC ALGORITHMS.工業工程學刊,25(2),91-104.
2. (2012).Solving the Economic Lot and Inspection Scheduling Problem using the Extended Basic Period approach under Power-of-Two policy.工業工程學刊,29(1),43-60.