經濟批量排程問題(ELSP)已確認是一個非多項式時間演算法可解(NP-hard)的存貨問題，一般求解ELSP的問題，大都使用分析式方法或啟發式方法。分析式方法如動態規劃及整數規劃，它在解決10種產品以上的ELSP問題時，會花費很多的演算時間。而啟發式方法所得到的解，都會傾向於區域的最小值，因此不能保證所求的解是全面的最佳解。為解決上述求解ELSP的缺點，本研究希望藉由遺傳演算法(GA)多點平行搜尋的優點，迅速求取ELSP可能的最佳解。再運用經濟批量排程問題之可行解測試法(Feasibility Testing Procedure for the ELSP；Proc FT)，來判斷GA所求得的解是否可行。本研究先以文獻範例進行測試與修訂所提出的解法(即GA + Proc FT)，再依機器不同的產能利用率隨機產生共80組的數據，來驗證本研究所得到最佳解的品質及演算法的時間。在單台機器生產10種產品及產能利用率小於 0.70時，利用本研究所建構的方法平均約2分鐘(Pentium 266 PC with 64M RAM)，即可找到與成本下限值平均差距1.12%以內的可行解，足見其解法優異的效率，故此解法可作為決策者生產排程上的參考。

The Economic Lot Scheduling Problem (ELSP) is an NP-hard inventory problem. The solution approaches for the ELSP may be classified into two categories, i.e., analytic approaches and heuristic approaches. However, the analytic approaches, for example, dynamic programming and integer programming, usually take extremely long run time to secure an optimal solution. On the other hand, the heuristic approaches often lead to a local minimum, and there is no guarantee for the quality of the solution. In order to efficiently solve the ELSP, 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. We pilot-run our HGA using the benchmark examples in literature, and then fine-tune the parameters of HGA by the testing results. Also, we generate random experiments to verify the performance of our HGA and to show that HGA secures excellent-quality solutions within a reasonably short run time. Especially, when the utilization rate of the production facility is less than 70%, the average deviation of HGA’s solutions from a lower bound is within 1.12%. Therefore, we conclude that our HGA is able to efficiently solve the ELSP, and it may provide important decision support for production managers.

中文摘要 I
英文摘要 II
誌謝 III
目 錄 IV
表 目 錄 VII
圖 目 錄 IX
第一章 緒論 1
1.1 研究背景 1
1.2 研究目的 2
1.3 研究方法與步驟 3
1.4 研究範圍與限制 3
1.5 研究工具 4
1.6 論文架構 5
第二章 文獻探討 6
2.1 經濟批量排程問題 6
2.2 經濟批量排程問題之模式 7
2.2.1 分析式解法 8
2.2.1.1 獨立解法(the Independent Solution; IS) 8
2.2.1.2 共同週期法(the Common Cycle; CC) 9
2.2.1.3 基本週期(Basic Period; BP)法 10
2.2.1.4 基本延伸週期(Extended Basic Period; EBP)法 13
2.2.2 啟發式解法 16
2.2.2.1 Park & Yun之解法 16
2.2.2.2 Boctor之解法 17
2.2.2.3 Geng & Vickson之解法 18
2.3 遺傳演算法(Genetic Algorithm; GA) 21
2.4 Proc FT可行解的判斷 26
2.4.1 設定初始條件 26
2.4.2 產品初步排程(Proc.IS) 26
2.4.3 調整週期的方式 29
2.4.3.1 移出(The Smooth-Out Routine) 29
2.4.3.2 1對1互換(The Pair-Exchange Routine) 31
2.4.3.3 2對1互換(The Two-to-One Exchange Routine) 32
2.4.3.4 隨機選取[n/2]個產品 34
2.4.4 輸出 34
2.5 本章小節 34
第三章 以遺傳演算法及Proc FT求解ELSP之規劃 36
3.1 數學模式 36
3.2 資料結構 37
3.3 遺傳演算法參數及上下界之設定 37
3.4 整體求解流程規劃 38
3.4.1 輸入產品資料 38
3.4.2 用GA程式求可能的最佳解 39
3.4.3 LCM排序程式 41
3.4.4 Proc FT可行解的判斷 42
3.4.4 記錄結果 44
3.4.5 資料驗證 44
第四章 文獻範例驗證 48
4.1 文獻範例資料（一） 48
4.2 文獻範例資料（二） 51
4.3 遺傳演算法的改進 53
4.4 驗證結果與比較 54
4.5 本章小節 54
第五章 不同的排序方式對求解ELSP之影響 70
5.1 不同的排序方式 70
5.2 測試資料 71
5.3 比較項目 71
5.4 整體比較流程規劃 71
5.4.1 加權重的GA程式 72
5.4.2 LCM程式 73
5.4.3 Proc FT程式 73
5.5 實驗結果 74
5.6 本章小結 79
第六章 數據實驗 81
6.1 隨機產生資料 81
6.2 門檻值的設定 82
6.3 整體驗證流程 83
6.4 驗證結果 87
6.5 本章小結 87
第七章 結論與建議 92
7.1 結論 92
7.2 建議 92
參考文獻 95
附錄A 四種啟發式ELSP可行解判斷方法的比較 97
A.1 比較項目規劃 97
A.2 結果比較 103
附錄B 求Fujita第六組可行解之曲線圖 106
B.1 求解流程 106
B.2 求解結果 110
附錄C 遺傳演算法之改進（增加權重） 123
C.1 分析原因 123
C.2 GA的改進 125
C.3 改進後之結果 127
C.4 小結 128
附錄D Fujita六組數據最佳可行解之排程 141
簡歷 167
表 目 錄
表2.1 BP之生產排程範例 12
表2.2 EBP之生產排程範例 15
表2.3 Park & Yun解法之範例 17
表2.4 Boctor解法之範例 18
表2.5 Geng 及 Vickson解法之範例 19
表3.1 驗證資料範例（以Fujita第一組為例） 47
表4.1 Fujita第一組數據 48
表4.2 Fujita第二組數據 49
表4.3 Fujita第三組數據 49
表4.4 Fujita第四組數據 50
表4.5 Fujita第五組數據 50
表4.6 Fujita第六組數據 51
表4.7 Bomberger數據(a =1) 52
表4.8 Bomberger數據(a =2) 52
表4.9 Bomberger數據(a=3) 53
表4.10 驗證結果(一) 55
表4.11文獻中Fujita數據最佳解之比較表 56
表4.12 Fujita第一組基本資料及驗證資料 60
表4.13 Fujita第二組基本資料及驗證資料 61
表4.14 Fujita第三組基本資料及驗證資料 62
表4.15 Fujita第四組基本資料及驗證資料 63
表4.16 Fujita第五組基本資料及驗證資料 64
表4.17 Fujita第六組基本資料及驗證資料 65
表4.18驗證結果（二） 66
表4.19文獻中Bomberger數據最佳解之比較表 66
表4.20 Bomberger資料( a=1)及驗證資料 67
表4.21 Bomberger資料( a=2)及驗證資料 68
表4.22 Bomberger資料( a=3)及驗證資料 69
表5.1 不同的排序方式 71
表5.2 第五組依各種排序方式找到可行解的比較 75
表5.3 第六組依各種排序方式找到可行解的比較 75
表5.4 第六組依各種排序方式找到比21327小的比較 75
表5.5 第五組依各種排序方式找到可行解的詳細資料 76
表5.6 第六組依各種排序方式找到可行解的詳細資料 77
表5.7 第六組依各種排序方式找到比21327小的詳細資料 78
表6.1 產品資料範圍 82
表6.2 驗證隨機產生資料之範例 84
表6.3 不同產能利用率解的比較 87
表6.4 產能利用率 0.50-0.55之結果 88
表6.5 產能利用率 0.55-0.60之結果 88
表6.6 產能利用率 0.60-0.65之結果 89
表6.7 產能利用率 0.65-0.70之結果 89
表6.8 產能利用率 0.70-0.75之結果 90
表6.9 產能利用率0.75-0.80之結果 90
表6.10 產能利用率 0.80-0.85之結果 91
表6.11 產能利用率 0.85-0.90之結果 91
表A.1 隨機機率與ki的對應表 98
表A.2 不同B值隨機產生資料之命名表 99
表A.3 不同稼動率之命名表 103
表A.4 從1000組隨機資料中利用各種方法求可行解數目之比較 104
表A.5 利用各種方法測試Proc FT 100組可行解之比較 104
表A.6 不同稼動率100組Proc FT可行解利用各種方法求可行解數目之比較 105
表B.1 Fujita 第六組B與門檻值的設定 108
表B.2 在B固定之下與其他學者所求得的最佳解之比較 110
表B.3 Fujita第六組可行解資料 112
表C.1 Fujita第六組不加權重之機率 124
表C.2 -f +M取3位數(M值取小一點)之機率 125
表C.3 Fujita第六組加權重之機率 126
表C.4權重的設定 128
表C.5 加權重與不加權重之平均比較表 129
表C.6 第一組加權重與不加權重之結果 133
表C.7 第二組加權重與不加權重之結果 134
表C.8 第三組加權重與不加權重之結果 135
表C.9 第四組加權重與不加權重之結果 136
表C.10 第五組加權重與不加權重之結果 137
表C.11 第六組加權重與不加權重之結果 138
表C.12 Fujita 六組數據加權重執行150代之結果 139
表D.1 Fujita第一組最佳可行解之排程 142
表D.2 Fujita第二組最佳可行解之排程 143
表D.3 Fujita第三組最佳可行解之排程 145
表D.4 Fujita第四組最佳可行解之排程 146
表D.5 Fujita第五組最佳可行解之排程 148
表D.6 Fujita第六組最佳可行解之排程 166
圖 目 錄
圖2.1 BP排程範例 12
圖2.2 EBP排程範例 15
圖2.3 GA之演算流程 20
圖2.4單點交配方式 23
圖2.5 兩點交配方式 23
圖2.6 Proc FT流程圖 25
圖3.1 整體求解流程規劃 40
圖3.2 LCM排序流程 43
圖3.3 Excel驗證資料流程 46
圖4.1 Fujita第一組最佳解之排程圖 57
圖4.2 Fujita第二組最佳解之排程圖 57
圖4.3 Fujita第三組最佳解之排程圖 58
圖4.4 Fujita第四組最佳解之排程圖 58
圖4.5 Fujita第五組最佳解之排程圖 59
圖4.6 Fujita第六組最佳解之排程圖 59
圖5.1 整體比較流程 72
圖6.1整體數據實驗流程 86
圖A.2 不同稼動率產生100組Proc FT可行解之流程 102
圖B.1 求解Fujita第六組可行解曲線圖之流程 107
圖B.2初步結果之曲線圖 111
圖B.3 Fujita第六組可行解之曲線圖 111
圖C.1 不加權重之機率 124
圖C.2 取3位數不加權重之機率 125
圖C.3 加權重之機率 127
圖C.4 第一組加權重及不加權重與最小值之關係圖 130
圖C.5 第二組加權重及不加權重與最小值之關係圖 130
圖C.6 第三組加權重及不加權重與最小值之關係圖 131
圖C.7 第四組加權重及不加權重與最小值之關係圖 131
圖C.8 第五組加權重及不加權重與最小值之關係圖 132
圖C.9 第六組加權重及不加權重與最小值之關係圖 132

[1] Boctor, F.F., “The G-group Heuristic for Single Machine Lot scheduling,” International Journal of Production Research, 25, 363-379 (1987).
[2] Bomberger, E., “A Dynamic Programming Approach to a Lot Size Scheduling Problem,” Management Science, 12, 778-784 (1966)
[3] Carreno, J.J., “Economic Lot Scheduling for Multiple Products on Parallel Identical Processors,” Management Science, 36, 348-358 (1990).
[4] Davis, S.G., “Scheduling Economic Lot Size Production Runs,” Management Science, 36, 985-998 (1990).
[5] Elmaghraby, S.E., “ The Economic Lot Scheduling Problem (ELSP): Review and Extension,” Management Science, 24, 587-597 (1978).
[6] Fujita, S., “The Application of Marginal Analysis to the Economic Lot Size Scheduling Problem,” AIIE Transactions, 10,354-361 (1978).
[7] Garey, M.R. and D.S. Johnson, “Strong NP-Completeness Results: Motivation, Examples and implications,” Journal of the Association for Computing Machinery, 25, 499-508 (1978).
[8] Geng, P.C. and R.G. Vickson, “Two Heuristics for the Economic Lot Scheduling Problem: An Experimental Study,” Naval Research Logistics, 35, 605-617 (1988).
[9] Haessler, R. and S. Hogue, “A Note on the Single Machine Multi-Product Lot Scheduling Problem,” Management Science, 22, 909-912 (1976).
[10] Hanssmann, F., “Operation Research in Production and Inventory Control, ” Wiley, New York, 1962.
[11] Holland, J.H., “Adaptation in Natural and Artificial Systems, ” University of Michigan Press, Ann Arbor, MI, 1975.
[12] Hsu, W.L., “On the General Feasibility Test of Scheduling Lot Size for Several Products on One Machine,” Management Science, 29, 93-105 (1983).
[13] Jones, P. C. and R. R. Inman, “When Is The Economic Lot Scheduling Problem Easy?,” IIE Transactions, 21, 11-20 (1989).
[14] 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).
[15] Lopez, M.A. and B.G. Kingsman, “The Economic Lot Scheduling Problem: Theory and Practice,” International Journal of Production Economics, 23, 147-164 (1991).
[16] Moon, I., E.A. Silver, and S. Choi, “Hybrid Genetic Algorithm for the Economic Lot-Scheduling Problem, ” International Journal of Production Research, 40, 809-824 (2002).
[17] Park, K.S. and D.K. Yun, “A Stepwise Partial Enumeration Algorithm for the Economic Lot Scheduling Problem,” IIE Transactions, 16, 363-370 (1984).
[18] Park, K.S. and D.K. Yun, “Feasibility Test for Multi-Product Lot Size Scheduling on One Machine,” Policy and Information, 11, 101-108 (1987).
[19] Pino, M. and X., Chao, Operation Scheduling with Application in Manufacturing and Services, McGraw-Hill, Singapore, 1999.
[20] Sule D.R., Industrial Scheduling, PWS, Boston, MA, 1997.
[21] Yao, M.J., “The Economic Lot Scheduling Problem with Extension to Multiple Resource Constraints,” Unpublished Ph.D. Dissertation, (1999) North Carolina State University, Raleigh, North Carolina USA.
[22] Yao, M.J., “On the Feasibility Testing Problem for the Economic Lot Scheduling Problem, ” Proceeding of the 8th Bellman Continuum Conference, Hsinchu, Taiwan, 307-315(2000).
[23] Yao, M.J., “The Economic Lot Scheduling Problem under Power-Of-Two Policy,” Computers and Mathematics with Applications, 41, 1379-1393 (2001).
[24] Yao, M.J., “The Peak Load Minimization Problem in Cyclic Production,” Computers and Operations Research, 28, 1441-1460 (2001).
[25] 姚銘忠，存貨控制上課講義，東海大學工業工程與經營資訊研究所，台中，2001。
[26] 姚銘忠，最佳化專題上課講義，東海大學工業工程與經營資訊研究所，台中，2000。
[27] 洪國勝，Visual Basic專業版入門大補貼，松崗，臺北市，1996。
[28] 張智星，MATLAB 程式設計與應用，清蔚科技，新竹市，2000。
[29] 黃士芬，「遺傳演算法應用於模糊需求之經濟批量排程問題」，碩士論文，私立東海大學工業工程研究所，2001。
[30] 賴阿福，Visual Basic 5.0入門與進階，松崗，臺北市，1997。
[31] 鐘怡理，電腦概論與程式設計，松崗，臺北市，1997。