A Backward Approach LPC-Based Constructive Heuristic

後向式之短週期成本爲基礎之建構式啓發式演算法

10.29977/JCIIE.200807.0002

Johnny C. Ho；Tzu-Liang Bill Tseng；Alex J. Ruiz-Torres；Francisco J. López

批量大小 ； 啓發式演算法 ； 物料需求計劃 ； 實證結果 ； lot-sizing ； heuristics ； material requirements planning ； empirical results

工業工程學刊

25卷4期（2008 / 07 / 01）

275 - 286

英文

在本論文中，我們建議用一個啟發式演算法來求解一個非常出台的單一階段無產能限制的動態批量問題。所發展之演算法係基於Silver and Meal [18]所提出之平均期間成本準則，也就是眾所皆知的最短週期成本(Least Period Cost, LPC)。所提出之演算法具有二個令人滿意的特徵，那就是簡單性及能有效率地解決互補最短週期成本。我們藉由使用20 個由Baker [2] 和 Berry [3]所產生之標竿問題，來檢視所發展之演算法之效率。更進一步地，我們執行大模規之模擬，此一模擬中包含了80,000個亂數產生的問題，來比較所發展之演算法興數個在文獻中非常流行的演算法。我們的計算結果顯示所建議之啟發式演算法能夠取得高的競爭結果。

In this paper, we propose a heuristic for the well-known single-level un-capacitated dynamic lot-sizing problem. The proposed heuristic is based on the average period cost criterion introduced by the heuristic from Silver and Meal [18], also known as Least Period Cost (LPC). Two desirable features of the proposed heuristic are simplicity and the heuristic's ability to complement LPC effectively. We examine the effectiveness of the proposed heuristic by using a set of 20 benchmarking test problems attributed to Baker [2] and Berry [3]. Furthermore, we perform a large-scale simulation involving 80,000 randomly generated problems to evaluate the proposed heuristic against several popular heuristics in the literature. Our computational results show that the proposed heuristic is able to achieve highly competitive results.

1. Axsater, S.(1986).Evaluation of lot-sizing techniques.International Journal of Production Research,24,51-57.
2. Baker, K. R.(1989).Lot-sizing procedures and a standard data set: A reconciliation of the literature.Journal of Manufacturing and Operations Management,2,199-221.
3. Berry, W. L.(1972).Lot sizing procedures for requirements planning system: a framework for analysis.Production and Inventory Management,13,19-34.
4. Blackburn, J.,R. Millen(1979).Selecting a lot-sizing for a single-level assembly process: part I-analytical results.Production and Inventory Management,20,42-47.
5. Blackburn, J.,R. Millen(1980).Heuristic lot-sizing performance in a rolling-schedule environment.Decision Sciences,11,691-701.
6. Chen, J. M.,L. T. Chen(2006).Market-driven production lot-size and scheduling with finite capacity for a deteriorating item.Production Planning & Control,17,44-53.
7. DeMatteis, J. J.(1968).An economic lot-sizing technique: the part-period algorithm.IBM Systems Journal,7,30-38.
8. Eftekharzadeh, R.(1993).A comprehensive review of production lot-sizing.International Journal of Physical Distribution & Logistics Management,23,30-44.
9. Evans, J. R.(1997).Production/Operations Management: Quality, Performance, and Value.Minneapolis, MN:West.
10. Gorham, T.(1968).Dynamic order quantities.Production and Inventory Management,9,75-81.
11. Haddock, J.,D. E. Hubicki(1989).Which lot-sizing techniques are used in material requirements planning?.Production and Inventory Management,30,53-56.
12. Ho, J. C.,Y. L. Chang,A. O. Solis(2006).Two modifications of the least cost per period heuristic for dynamic lot-sizing.Journal of the Operational Research Society,57,1005-1013.
13. Hu, J.,C. L. Munson(2002).Dynamic demand lot-sizing rules for incremental quantity discounts.Journal of the Operational Research Society,53,855-863.
14. Kaimann, R. A.(1969).EOQ vs. dynamic programming-which one to use for inventory ordering.Production and Inventory Management,10,66-74.
15. Nahmias, S.(2005).Production and Operations Analysis.New York, NY:McGraw-Hill.
16. Pan, C-H.(1994).Sensitivity analysis of dynamic lot-sizing heuristics.Omega,22,251-261.
17. Saydam, C.,J. R. Evans(1990).A comparative performance analysis of the Wagner-Whitin algorithm and lot-sizing heuristics.Computers & Industrial Engineering,18,91-93.
18. Silver, E. A.,D. F. Pyke,R. Peterson(1998).Inventory Management and Production Planning and Scheduling.New York, NY:John Wiley & Sons.
19. Silver, E. A.,H. C. Meal(1973).A heuristic for selecting lot size quantities for the case of deterministic time varying demand rate and discrete opportunities for replenishment.Production and Inventory Management,14,64-74.
20. Sipper, D.,R. L. Bulfin(1997).Planning: Planning, Control and Integration.New York, NY:McGraw-Hill.
21. Wagner, H. M.,T. M. Whitin(1958).Dynamic version of the economic lot size model.Management Science,10,89-96.