臺灣博碩士論文加值系統

經濟批量排程問題（economic lot scheduling problem；ELSP）的最佳化求解已被證明是一個具NP-hard複雜度的問題。在過去一般的ELSP模式中，大都假設存貨可以無限期的儲存，並未考慮產品具有損耗性。但是在現實生活中，常見產品具有損耗性；本研究在此前提假設下，使用循環週期法找出損耗品ELSP模式下的最佳解。在探討損耗品ELSP模式，本研究推導出在若干現實生活中可能發生的特定條件下，運用循環週期法的封閉解(closed-form solution)即為該模式之最佳解。同時，本研究亦對於所推導之特定條件進行敏感度分析，探討特定條件被寬鬆後，循環週期法所得之解與最佳解間誤差之上限。另外，本研究延伸上述損耗品ELSP模式的推導，以「可運用於整備的機台時間」定義機台產能限制，並允許擁有延遲的訂單；依此，本研究亦推導出在何種特定條件下，使用循環週期法亦可得到最佳解。而且，我們探討循環週期法在於群組技術問題的實務應用。而在捨棄特定條件的假設下，本研究則藉由遺傳演算法(GA)多點平行搜尋的優點，迅速求取損耗性ELSP可能的最佳解。再運用經濟批量排程問題之可行解測試法(Feasibility Testing Procedure for the ELSP；Proc FT)，來判斷GA所求得的解是否可行。

The Economic Lot Scheduling Problem (ELSP) is concerned with the lot sizing and scheduling decision of n items. It has been proved that the ELSP is an NP-hard problem. In the conventional ELSP model, it does not consider the product stock could deteriorate over time. The focus of this study is to employ the rotation cycle (RC) approach to solve the ELSP with deteriorating items. The RC approach secures a feasible production schedule in which each item share the same replenishment cycle. We show that the RC approach’s schedule is optimal for in many realistic situations. Importantly, we give upper bounds for the maximum percentage that the RC approach’s schedule deviates from optimality. On the other hand, we extend our theoretical analysis to the case that includes the machine capacity constraint by considering the long run proportion of time available for setups. We also show how these results can be used when backorders are allowed. An implication for Group Technology is discussed. The proposed algorithm was tested by real data for electronic industry, and this approach can be applied to most constraint-satisfaction problems. If these situations mentioned-aboved does not exist, we derive a hybrid genetic algorithm (HGA) that utilizes the advantage of multi-directional search in GA and employs an efficient heuristic, namely, Proc FT, to test feasibility of the solutions found.

中文摘要 III
英文摘要 IV
致謝 VI
目錄 VI
圖目錄 X
表目錄 XI
第一章 緒論 1
1.1研究背景與動機 1
1.2 研究目的 2
1.3研究方法與步驟 3
1.3.1獨立解法 5
1.3.2循環週期法(The Rotation Cycle Approach ; RC) 5
1.3.3基本週期(basic period ; BP)法 6
1.3.4延伸基本週期(extended basic period ; EBP)的方法 6
1.4研究工具 7
1.5論文架構 7
第二章 文獻探討 10
2.1經濟批量排程問題之背景(economic lot scheduling problem ; ELSP) 10
2.1.1經濟批量排程問題之探討 10
2.2損耗品相關文獻探討 11
2.3基因演算法在批量排程問題上的探討 12
2.4過去文獻缺口 12
第三章 使用循環週期法求解帶損耗之ELSP模式 14
3.1兩種基本解法(帶損耗性) 14
3.1.1獨立解法(The Independent Solution ; IS) 14
3.1.2循環週期法(The Rotation Cycle Approach ; RC) 16
3.2以循環週期法求解損耗品ELSP模式的理論分析 18
3.2.1循環週期法可得損耗品ELSP模式最佳解的特定條件 18
3.2.2敏感度分析 20
3.3延伸模式與實務應用之探討 24
3.3.1延伸模式的探討 25
3.3.2循環週期法在群組技術實務之應用 28
3.4數值範例 28
第四章 損耗品延伸基本週期模式探討 31
4.1 基本週期法模式(basic period ; BP) 31
4.2延伸基本週期法模式(extended basic period ; EBP) 32
4.2.1二冪次策略(Power of Two;PoT)下之損耗性ELSP(EBP)模式 32
4.2.2一般整數策略(General integer;GI)下之損耗性ELSP(EBP)模式 35
4.3合理解測試（Proc FT）的演算程序 36
4.3.1初始排程程序（Proc IS） 38
4.3.2產品排程程序（Proc PS） 40
4.3.3排程撫平程序（Proc SS） 40
4.3.4 ELSP的合理解測試程序（Proc FT） 41
第五章 使用基因演算法求解損耗性ELSP(EBP) 44
5.1基因演算法則 45
5.1.1基因演算法則流程 45
5.1.2基因演算法之基本運算子(operators) 48
5.2以GA求解損耗性ELSP(EBP)的模式設計與相關說明 50
5.2.1適應性函數說明（fitness function） 50
5.2.2限制式說明(Constraints) 51
5.2.3染色體表示方式 52
5.2.4延伸週期模式之基因演算流程 54
5.2.5修正基本週期程序 57
5.3以GA求解具損耗性之延伸週期法的參數設定討論 58
5.4 數值範例 63
5.5以GA求解具損耗性ELSP(EBP,GI)的困難點 64
第六章 結論與建議 67
6.1結論及建議 67
6.2未來研究方向 69
參考文獻 70
附錄A 75
A.1損耗品ELSP模式獨立解法之推導 75
A.2損耗品ELSP模式循環週期法之推導 76
A.3輔助定理1之證明 77
A.4考慮機台產能之損耗品ELSP模式的Ti*推導 78
A.5考慮機台產能且允許延遲訂單之損耗品ELSP模式的 推導 79
附錄B 80
B.1初始排程程序（Proc IS） 80
B.2產品排程程序（Proc PS） 80
B.3排程撫平程序（Proc SS） 83
附錄C 91
C.1 和 上界之推導 91
C.2六組損耗ELSP基本資料及參數設定表 92
C.3 MPI及Run-Time假設檢定 95
C.4六組數據在兩種策略下的排程結果 97

[1] Abad, P.L., " Optimal lot size for a perishable good under conditions of finite production and partial backordering and lost sale," Computers and Industrial Engineering, 38, 457-465 (2000).
[2] Axsäter, S., “Alternative dynamic programming approaches to obtain upper bounds for the economic lot scheduling problem,” Eng Costs and prod Econ 6, 179-189, 1982.
[3] Boctor, F. F., “The G-group Heuristic for single machine lot scheduling,” International Journal of Production Research, 25, 3, 363-379, 1987.
[4] Bomberger, E. E., “A dynamic programming approach to a lot size scheduling problem,” Management Science 12, 778-784, 1966.
[5] Davis, S.G., “Scheduling economic lot scheduling problem runs,” Management Science 36, 985-998, 1990.
[6] Doll C.L. and Whybark DC. Thomas, “An interactive procedure for the single-machine multi-product lot scheduling problem,” Management Science, 20, 50-55, 1973.
[7] Elmaghraby, S.E., “The economic lot scheduling problem: review and extensions,” Report 112, pp.587-598, 1976.
[8] Elmaghraby, S.E., “The economic lot scheduling problem: review and extensions,” Management Science, 24, 587-598, 1978.
[9] Elsayed, E.A., & Teresi, C. " Analysis of inventory system with deteriorating items," International Journal of Production Research, 21, 449-460, 1983.
[10] Fujita, S., “The Application of Marginal Analysis to the Economic Lot Scheduling Problem,” AIIE Transactions 10, 4, 1978.
[11] Gallego, G., “An Extension to the class of easy Economic lot scheduling problems,” IIE Transactions, 22, 189-190, 1990.
[12] Gallego, G. and I. Moon, “The effect of externalizing setups in the economic lot scheduling problem,” Operations Research, 40, 614-619, 1992.
[13] Gallego, G., “Reduced production rates in the economic lot scheduling problem,” International Journal of Production Research, 31, 1035-1046, 1993.
[14] Gallego, G. and I. Moon, “Strategic investment to reduce setups times in the economic lot scheduling problem,” Naval research logistics, . 42, 773-790, 1995.
[15] Geng, P.C. & Vickson, R.G., “Two Heuristics for the economic lot scheduling problem: an experimental study,” Noval Res Logist 35, 605-617, 1988.
[16] Glass, C.A., “Feasibility of scheduling lot sizes of three products on one machine,” Management Science, 38, 1482-1494, 1992.
[17] Ghare, P.M., and G.F. Schrader, “A model for an expontentially decaying inventory,” Journal of Industrial Engineering, 14, 238-243, 1963.
[18] Goldberg, D. E., “Genetic and evolutionary algorithm come of age,” Communications of the ACM, 37, 113 — 119, 1994.
[19] Goyal, S.K., “Scheduling a multi-product single-machine system,” Operations Research, 24, 261-266, 1973.
[20] Graham, R.L., “Bounds on Multiprocessing Timing Anomalies,” SIAM Journal on Applied Mathematics, 17, 416-429, 1969.
[21] Haessler, R. and Hogue., “A Note on the Single Machine Multi-Product Lot Scheduling Problem,” Management Science 22, 8, 909-912, 1976.
[22] Ham, I.; Hitomi, K. & Yoshida, T., GroupTechnology:Applications to Production Management, Kluwer-Nijhoff Publishing, Boston, 2, 1985.
[23] Hanssmann, F., Operation Research in Production and Inventory, New York City 158-160, 1962.
[24] Harris, F. W., “How many parts to make at once,” Operational Research 38, 947-950, 1990.
[25] Heng, K.J. , Labban, J., & Linn, R.J. " An order-level lot-size inventory model for deteriorating items with finite replenishment rate," Computers and Industrial Engineering, 20, 187-197, 1991.
[26] Hsu, W. L., “On the general feasibility test of scheduling lot sizes for several products on one machine,” Management Science 29, 93-105, 1983.
[27] Khouja, M., “The economic lot scheduling problem under volume flexibility, forthcoming,” The International Journal of Production Economics, 48, 73-86, 1997.
[28] Khouja, M., Z. Michalewicz, and M. Wilmot, “The Use of Genetic Algorithms to Solve the Economic Lot Size Scheduling Problem,” European Journal of Operation Research, 110, 509-524, 1998.
[29] Kim, S. L., J. C. Hayya, and J. Hong, “Setup reduction and machine availability,” Production and Operations Management, 4, 76-90, 1995.
[30] Lopez, M.A. and B.G. Kingsman, “ The Economic Lot Scheduling Problem: Theory and Practice,” International Journal of Production Economics, 23, 147-164, 1991.
[31] Madigan, J.C., “Scheduling a multi-product single machine system for an infinite planning period,” Management Science, 14, 713-719, 1968.
[32] Misra, R.B. " Optimal production lot size model for a system with deteriorating items," International Journal of Production Research, 13, 495-505, 1975.
[33] Nahmias, S., “Perishable inventory theory: a Review, ”Operations Research, 30, 680-708, 1978
[34] Park, K. and D. Yun, “A Stepwise Partial Enumeration Algorithm for the Economic Lot Scheduling Problem”, IIE Transactions, 16, 363-370, 1984.
[35] Philip, C. and Robert R., "When is the economic lot scheduling problem easy," European Journal of Operational Research, 110, 509-524, 1998.
[36] Pinedo, M., Scheduling: Theory, Algorithms, and Systems. (Englewood Cliffs, NJ: Prentice-Hall), 1993.
[37] Raafat, F. " Survey of literature on continuously deteriorating inventory models," Journal of Operational Research Society, 42, 27-37, 1991.
[38] Rogers, J., “A computational approach to the economic lot scheduling problem,” Management Science 4, 264-291, 1958.
[39] Silver, E., “Deliberately slowing down output in a family production context,” International Journal of Production Research, 29, 17-27. 1990.
[40] Yao, M. J., “The economic lot scheduling problem with extension to multiple resource constraints,” Unpublished Ph.D. Dissertation, North Carolina State University, Raleigh, North Carolina USA, 1999.
[41] Yao, M.J., “On the Feasibility Testing Problem for the Economic Lot Scheduling Problem,” Proceedings of the 8th Bellman Continuum Conference, Hsinchu, Taiwan, 307-315 2000.
[42] Yao, M.J., “The Peak Load Minimization Problem in Cyclic Production,” Computers and Operations Research, 28, 1441-1460 (2001).
[43] 王立志，系統化運籌與供應鏈管理，滄海書局，1999。
[44] 黃士芬， “遺傳演算法應用於模糊需求之經濟批量排程問題”，私立東海大學工業工程研究所碩士論文，2001。
[45] 陳英欽， “單台機器之經濟批量排程問題”，私立東海大學工業工程研究所碩士論文，2002。
[46] 張皓傑，C++ Builder 4.0 程式設計聖經，和碩，臺北市，1999。
[47] http://cindy.cis.nctu.edu.tw/ 交通大學資訊科學研究所。