臺灣博碩士論文加值系統

及時生產系統(Just-in-Time)是以追求低存貨成本為目標的生產模式，但在一個動態需求的生產環境其批量生產決策卻有其困難之處，所謂的動態需求是指需求速率會隨時間而改變。本論文考慮動態需求環境下的多機台(multi-machine)產能批量排程問題(capacitated lots size scheduling)，以最小的存貨成本為目標，希望能找出符合即時生產系統概念的生產排程。本論文主要的做法乃是將生產決策分為「離散決策」與「連續決策」兩類。離散決策包含有各批量所欲生產的產品種類、各批量開始生產時期、各批量結束生產時期與在哪一台機台生產。連續決策則為各批量精確的開始生產時間點與結束生產時間點。求解方法為先利用塔布搜尋法或模擬退火法找出離散決策，再帶入一個以最小化總存貨成本為目標的數學規劃模式，以求解出連續決策的值與目標函數值。如此不斷地重複以上步驟，希望可得到總存貨成本較低的批量生產排程。
由實驗中得知，本演算法可以很有效率地針對每一種產品種類，找出一條很貼近需求曲線的生產曲線，降低總存貨成本，並避免缺貨情況的發生。至於搜尋法則的搜尋成效部分，塔布搜尋法在搜尋近似最優解的成效比模擬退火法快且有效率，因此，建議使用塔布搜尋法搜尋新的離散決策。

The goal of a Just-in-time production system is to minimize the inventory cost. However, it is difficulty to make lot size decisions under a dynamic demand environment, whose demands vary with time. To achieve the goal of JIT, this study considers multi-machine dynamic-demand capacitated lot size scheduling problem with the objective of minimizing the inventory cost. We divide the overall production decision into two kinds of decisions: “discrete decisions” and “continuous decisions”. Discrete decisions include the product type for each of the production runs, the beginning period of each run, the ending period of each run, and product on the machines. The continuous decisions suggest the precise beginning epoch and ending epoch of each run. We will utilize tabu search and simulated annealing to determine the discrete decisions. Then, by using the discrete decisions, a mathematical programming model, proposed herein, will be used to solve the continuous decisions. The above procedure will be iterated to solve our problem.
Experimental results indicate that such a methodology can effectively obtain a production schedule for each type of product to reduce total inventory costs and eliminate backorders. Experimental designs and statistical methods are used to evaluate and analyze the performance of tabu search and simulated annealing. As a result, tabu search performs significantly better than simulated annealing. Therefore, we suggest that tabu search is utilized to search for discrete decisions.

第1章 緒論 …………………………………………………………………1
1.1研究背景…………………………………………………………………1
1.2研究動機…………………………………………………………………2
1.3研究目的…………………………………………………………………3
1.4研究方法…………………………………………………………………4
1.5本文架構…………………………………………………………………5
第2章 文獻探討………………………………………………………… 7
2.1經濟批量排成問題………………………………………………………7
2.2搜尋法則…………………………………………………………………10
2.2.1簡介………………………………………………………………...10
2.2.2模擬退火法………………………………………………………...11
2.2.3塔布搜尋法………………………………………………………...12
第3章 方法建構…..………………………………………………………14
3.1問題之說明………………………………………………………………14
3.2起始解與鄰近解之建構…………………………………………………18
3.2.1起始解之建構……………………………………………………...18
3.2.2鄰近解之設計……………………………………………………...22
3.2.3解表示法之修正…………………………………………………...24
3.3模擬退火法與塔布搜尋法之建構………………………………………25
3.3.1模擬退火法………………………………………………………...25
3.3.2塔布搜尋法………………………………………………………...30
3.4經濟批量排成問題線性規劃模型………………………………………33
第4章 實驗設計與分析……………………………………………………39
4.1問題模式…………………………………………………………………39
4.2實驗設計…………………………………………………………………43
4.2.1反映變數…………………………………………………………...43
4.2.2實驗進行方式……………………………………………………...43
4.3實驗分析…………………………………………………………………43
4.3.1實例計算的結果…………………………………………………...43
4.3.2實驗因子的分析…………………………………………………...52
4.3.3搜尋法的解題趨勢………………………………………………...54
第5章 結論與未來研究建議………………………………………………58
參考文獻……………………………………………………………………59

翁民賢, (2001), 動態需求環境下之產能批量排程，清華大學碩士論文。
Anthony, R. N. (1965), Planning and Control System：A Framework for Analysis, Havard University Press, Cambridge,Mass.
Bahl, H. C., Ritzman, L. P., Gupta, J. N. D. (1987), “Determining Lot Size and Resource Requirements: A Review”, Operations Research, Vol. 35, No. 3, pp. 329-345
Baker, J. (1987), Adaptive Selection Methods for Genetic Algorithms, Proceedings of the Second International Conference on Genetic Algorithms, Lawrence Erlbaum Associates, Hillsdale, NJ, pp. 100-111
Bomberger, E. (1966), “A dynamic Programming Approach to a Lot Size Scheduling Problem”, Management Science, Vol. 12, No. 11, pp. 778-784
Dobson, G. (1987), “The Economic Lot-Scheduling Problem: Achieving Feasibility Using Time-Varying Lot Size”, Management Science, Vol. 35, No. 5, pp. 764-771
Dobson, G. (1992), “The Cyclic Lot Scheduling Problem with Sequence-Dependent Setups”, Operations Research, Vol. 40, No. 4, pp. 736-749
Doll, C. L. and Whybark, D. C. (1973), “An Iterative Procedure for the Single-Machine Multi-Product Lot Scheduling Problem”, Management Science, Vol. 20, No. 1, pp. 50-55
Eglese, R.W.(1990), “Simulated Annealing: A tool for Operational Research”, European Journal of Operation Research, Vol. 46, pp. 271-281
Elmaghraby, S.E. (1978), “The economic lot scheduling problem (ELSP): Review and extensions”, Management Science, No. 24, pp. 587-598
Gallego, G. (1990), “Scheduling the Production of Several Items with Random Demands in a Single Facility”, Management Science, Vol. 36, No. 12, pp. 1579-1592
Gallego, G. and Roundy R. (1992), “The Economic Lot Scheduling Problem with Finite Backorder Costs”, Naval Research Logistics, Vol. 39, pp. 729-739
Glover, F. (1989), “Tabu search-Part I”, ORSA journal of computing, Vol. 1, No. 3, pp.191-206
Glover, F. and Lagura, M. (1997), Tabu search, Kluwer academic publishers.
Goncalves, J. F. and Leachman, R. C. (1998), “A Hybrid Heuristic and Linear Programming Approach to Multi-Product Machine Scheduling”, European Journal of Operational Research, Vol. 110, No. 3, pp. 548-563
Hanssman, Fred. (1962), Operations Research in Production and Inventory, John Wiley and Sons, New York City, pp. 158-160
Kirkpatrick, S., Gelatt, C.D., and Vecchi, M.P. (1983), “Optimization by Simulated Annealing”, Science, Vol. 220, No. 4598, pp. 671-680
Kuik, R., Salomon, M., Wassenhove, N. (1994), “Batching Decisions: Structure and Models”, European Journal of Operational Research, Vol. 75, pp. 243-263
Leachman, R. C. and Gascon A. (1988), “A Heuristic Scheduling Policy for Multi-item, Single-Machine Production Systems with Time-Varying, Stochastic Demands”, Management Science, Vol. 34, No. 3, pp. 377-390
Madigan, J. C. (1968), “Scheduling a Multi-Product Single-Machine System for an Infinite Planning Period”, Management Science, Vol. 14, No. 11, pp. 713-719
Maes, J., McClain, J. O., and Van Wassenhove, L. N. (1991), "Multilevel Capacitated Lotsizing Complexity and LP-Based Heuristics", European Journal of Operational Research, Vol. 53, pp. 131-148
Pinedo, M., and Chao, X. (1999), Operations Scheduling with Applications in Manufacturing and Services, McGRAW-HILL, New York, U.S.A..
Rogers, J. (1958), “A computational approach to the lot scheduling problem”, Management Science, Vol. 3, No. 3, pp. 264-291
Schweitzer, P. J. and Silver, E. A. (1983), “Mathematical Pitfalls in the One Machine Multi-Product Economic Lot Scheduling Problem”, Operations Research, Vol. 31, No. 2, pp. 401-405
Standkard, M. F. and Gupta, S. K. (1969), “A Note on Bomberger’s Approach to Lot Size Scheduling: Heuristic Proposed”, Management Science, Vol. 15, No. 7, pp. 449-452