臺灣博碩士論文加值系統

企業生產效率的良窳往往與排程息息相關，在生產規模經濟下，隨著工件數量的遽增與分工的複雜性提高，使得排程研究獲得更多的重視。早期學者多致力於單機問題的研究，然而實務上工作所涉及的往往不只是一個工作站，因此，雙機排程問題的研究便更顯得重要。
許多排程問題本質上為NP-hard，學者們時常利用探索式演算法來搜尋其近似最佳解，而過去學者在雙機單準則的特殊性質研究上，比如說：不同工件的處理時間之關係……等等，亦已累積不少成果，因此本研究針對雙機流程式單準則特殊性質之相關研究與基因演算法，試圖將兩者做一結合，用以改善基因演算法的演算效率，使其能更有效地解決雙機流程式單準則排程問題。
研究結果顯示出，不論在最佳值的改善率與收斂速度上，混合式基因演算法，的確可以有效改善以總流程時間、最大提前完工時間、最大延遲完工時間與平均延遲完工時間等為衡量準則之雙機流程式排程問題。

Efficiency of produce is relative with scheduling. In economy of scale, the scheduling gets more attention with the increase of jobs.
In actual, the work often needs more than one workshop. So that, the two-machine scheduling is important.
The nature of the many scheduling problems is NP-hard. Scholars had used genetic algorithms to search the approximate optimum solution and had studied the special case of two-machine flowshop. For example: the relationship of the processing time of the different jobs.
This thesis directs at special case of the single performance measure of the two-machine flowshop and genetic algorithms. We tried to combine with special case and genetic algorithms in order to improve the efficiency of genetic algorithms.
The result showed that hybrid genetic algorithms are better than tradition genetic algorithms whether in the improvement of the optimum solution or speed.

目錄
目錄…………………………………….………………………….…………………Ⅰ
圖目錄………………………………….………………………….…………………Ⅱ
表目錄………………………………….………………………….…………………Ⅳ
第一章 緒論…………………………….………………………….…………………1
一、 問題背景與研究動機……………………………………………………………1
二、 研究範圍與限制……………………………………………..…………………..4
三、 研究目的與問題……………………………………………..…………………..6
四、 研究流程…………………………………………………………………………8
第二章 文獻探討………………………………………………………………..……9
一、 雙機流程式排程問題…………………………………………………………....9
二、 基因演算法……………………………………………………………………..11
三、 基因演算法在排程之相關應用……………………….……………………….16
第三章 雙機流程式排程問題…………………………………………………..…18
一、 n/2/p/F問題之特殊性質………………………………………………………..18
二、 n/2/p/Emax問題之特殊性質……………...……………………………………..20
三、 n/2/p/Tmax問題之特殊性質……………………...……………………………..21
四、 n/2/p/ 問題之特殊性質………………………………...……………………...23
第四章 資料測試……………………………………………………………………24
一、參數設定……………………………………………….………………………...24
二、n/2/p/F問題……………………………………………..………………………..26
三、n/2/p/Emax問題………………………………………………………….………..29
四、n/2/p/Tmax問題………………………………………….……………………….36
五、n/2/p/ 問題………………………………………………………………….…...43
第五章 結論與建議…………………………………………………………………53
一、 研究結論………………………………………………………………………..53
二、 未來研究建議…………………………………………………………………..56
參考文獻…..…………………………………………………………………………59
一、中文文獻……………………………………………………………………..…59
二、英文文獻………………………………………………………………………..59

圖目錄
圖1.1 研究流程圖…………………………………………..………………………8
圖2.1 基因演算法流程圖………………………………………..………………..12
圖4.1 10/2/p/F測試結果………………………………………………………..…27
圖4.2 30/2/p/F測試結果……………………………………………………..……27
圖4.3 50/2/p/F測試結果……………………………………………………..……27
圖4.4 100/2/p/F測試結果…………………………………………………………27
圖4.5 10/2/p/Emax(TypeⅠ)測試結果………………………………...……………29
圖4.6 10/2/p/Emax(TypeⅡ)測試結果……………………...………………………30
圖4.7 10/2/p/Emax(TypeⅢ)測試結果………………………...……………………30
圖4.8 10/2/p/Emax(TypeⅣ)測試結果…………………………...…………………30
圖4.9 10/2/p/Emax(TypeⅤ)測試結果…………………………….………………..30
圖4.10 30/2/p/Emax(TypeⅠ)測試結果……………………………...…..…………31
圖4.11 30/2/p/Emax(TypeⅡ)測試結果…………………………………………….31
圖4.12 30/2/p/Emax(TypeⅢ)測試結果………………………………...………..…31
圖4.13 30/2/p/Emax(TypeⅣ)測試結果…………………………………...……..…31
圖4.14 30/2/p/Emax(TypeⅤ)測試結果……………………………………...…..…32
圖4.15 50/2/p/Emax(TypeⅠ)測試結果……………………………………….....…32
圖4.16 50/2/p/Emax(TypeⅡ)測試結果………………………………………….....32
圖4.17 50/2/p/Emax(TypeⅢ)測試結果………………………………………….…32
圖4.18 50/2/p/Emax(TypeⅣ)測試結果…………………………………………….33
圖4.19 60/2/p/Emax(TypeⅤ)測試結果…………………………………………….33
圖4.20 100/2/p/Emax(TypeⅠ)測試結果…………………………………………...33
圖4.21 100/2/p/Emax(TypeⅡ)測試結果…………………………………………...33
圖4.22 100/2/p/Emax(TypeⅢ)測試結果…………………………………………...34
圖4.23 100/2/p/Emax(TypeⅣ)測試結果………………………………………...…34
圖4.24 100/2/p/Emax(TypeⅤ)測試結果…………………………………………...34
圖4.25 10/2/p/Tmax(TypeⅠ)測試結果………………………………………….…37
圖4.26 10/2/p/Tmax(TypeⅡ)測試結果………………………………………….....37
圖4.27 10/2/p/Tmax(TypeⅢ)測試結果…………………………………………….38
圖4.28 10/2/p/Tmax(TypeⅣ)測試結果…………………………………………….38
圖4.29 10/2/p/Tmax(TypeⅤ)測試結果………………………………………..…...38
圖4.30 30/2/p/Tmax(TypeⅠ)測試結果…………………………………………….38
圖4.31 30/2/p/Tmax(TypeⅡ)測試結果…………………………………………….39
圖4.32 30/2/p/Tmax(TypeⅢ)測試結果…………………………………………….39
圖4.33 30/2/p/Tmax(TypeⅣ)測試結果…………………………………………….39
圖4.34 30/2/p/Tmax(TypeⅤ)測試結果…………………………………………….39
圖4.35 50/2/p/Tmax(TypeⅠ)測試結果…..………………………………………...40
圖4.36 50/2/p/Tmax(TypeⅡ)測試結果………………………………………..…...40
圖4.37 50/2/p/Tmax(TypeⅢ)測試結果…………………………………………….40
圖4.38 50/2/p/Tmax(TypeⅣ)測試結果………………………………………….…40
圖4.39 50/2/p/Tmax(TypeⅤ)測試結果…………………………………………….41
圖4.40 100/2/p/Tmax(TypeⅠ)測試結果…………………………………………...41
圖4.41 100/2/p/Tmax(TypeⅡ)測試結果…………………………………………...41
圖4.42 100/2/p/Tmax(TypeⅢ)測試結果…………………………………………...41
圖4.43 100/2/p/Tmax(TypeⅣ)測試結果…………………………………………...42
圖4.44 100/2/p/Tmax(TypeⅤ)測試結果…………………………………………...42
圖4.45 10/2/p/ (TypeⅠ)測試結果…………………………………………..…...45
圖4.46 10/2/p/ (TypeⅡ)測試結果……………………………………………….45
圖4.47 10/2/p/ (TypeⅢ)測試結果……………………………………………….46
圖4.48 10/2/p/ (TypeⅣ)測試結果……………………………………………….46
圖4.49 10/2/p/ (TypeⅤ)測試結果……………………………………………….46
圖4.50 30/2/p/ (TypeⅠ)測試結果……………………………………………….46
圖4.51 30/2/p/ (TypeⅡ)測試結果……………………………………………….47
圖4.52 30/2/p/ (TypeⅢ)測試結果……………………………………………….47
圖4.53 30/2/p/ (TypeⅣ)測試結果……………………………………………….47
圖4.54 30/2/p/ (TypeⅤ)測試結果……………………………………………….47
圖4.55 50/2/p/ (TypeⅠ)測試結果……………………………………………….48
圖4.56 50/2/p/ (TypeⅡ)測試結果……………………………………………….48
圖4.57 50/2/p/ (TypeⅢ)測試結果……………………………………………….48
圖4.58 50/2/p/ (TypeⅣ)測試結果……………………………………………….48
圖4.59 50/2/p/ (TypeⅤ)測試結果……………………………………………….49
圖4.60 100/2/p/ (TypeⅠ)測試結果……………………………………………...49
圖4.61 100/2/p/ (TypeⅡ)測試結果……………………………………………...49
圖4.62 100/2/p/ (TypeⅢ)測試結果……………………………………………...49
圖4.63 100/2/p/ (TypeⅣ)測試結果……………………………………………...50
圖4.64 100/2/p/ (TypeⅤ)測試結果…………………………………….……......50

表目錄
表4.1 測試資料型態表…………………………………………………………..…25
表4.2 n/2/p/F 測試結果彙整表…………………………………………………...28
表4.3 n/2/p/Emax測試結果彙整表………………………...…………………….…35
表4.4 n/2/p/Tmax測試結果彙整表……………………...…………………….……43
表4.5 n/2/p/ 測試結果彙整表……………………………………………………51

一、中文文獻
1. 官長輝（2003）。「基因演算法於國道客運最適車輛數及排程之整合研究」，輔仁大學管理學研究所。

二、英文文獻
1. Allahverdi, A. (1999). “Stochastically minimizing total flowtime in flowshops with no waiting space”, European Journal of Operational Research. 113, pp. 101-112.
2. Cheng, T. C. E. & Wang, G. (1999). “Two-machine flowshop scheduling with consecutive availability constraints”, Information Processing Letters. 71, pp.49-54.
3. Cepek, O., Okada, M. & Vlach, M. (2002). “Nonpreemptive flowshop scheduling with machine dominance”, European Journal of Operational Research. 139, pp. 245-261.
4. David, L. (1996). “Application of a hybrid genetic algorithms to airline crew scheduling”, Computers Ops Res. Vol. 23, No. 6, pp. 547-558.
5. French, S., B. A., M. A. & Phil, D. (1982). Sequencing and Scheduling: An Introduction to the Mathematics of the Job-Shop. Ellis Horwood Ltd.
6. Gupta, J. N. D., Neppalli, V. R. & Werner, F. (2001). “Minimizing total flow time in a two-machine flowshop problem with minimum makespan”, International Journal of Production economics. 69, pp. 323-338.
7. Holland J. (1975). “Adaptation in Natural and Artificial Systems”, University of Michigan Press: Michigan.
8. Ho, J. C. & Gupta, J. N. D. (1995). “Flowshop scheduling with dominant machines”, Computers Ops Res. Vol. 22, No. 2, pp. 237-246.
9. Huang, R. H. & Yang, C. L. (2005) “Genetic algorithm for scheduling maintenance of a mass rapid transit train system”, International Journal of Industrial Engineering, 12, pp.227-233.
10. Johnson, S. M. (1954) “Optimal two and three-stage production schedules with set-up times include”, Nav. Res. Logist. Q., 1, pp. 61-68.
11. Koulamas, C. (1998). “On the complexity of two-machine flowshop problems with due date related objectives”, European Journal of Operational Research. 106, pp.95-100.
12. Koksalan, M., Azizoglu, M. & Kondakci, S. K. (1998). “Minimizing flowtime and maximum earliness on a single machine”, IIE Transactions. 30, pp.192-200.
13. Liaw, C. F. (2000). “A hybrid genetic algorithm for the open shop scheduling problem”, European Journal of Operational Research, 124, pp.28-42.
14. Lin, B. M. T. (2001). “Scheduling in the two-machine flowshop with due date constraints”, International Journal of Production Economics. 70, pp. 117-123.
15.Murata, T., Ishibuchi, H. & Tanaka, H. (1996). “Genetic algorithms for flowshop scheduling problems”, Computers ind. Engng, Vol. 30, No. 4, pp. 1061-1071.
16. Park, B. J., Choi, H. R. & Kim, H. S. (2003). “A hybrid genetic algorithm for the job shop scheduling problems”, Computers & Industrial Engineering, 45, pp. 597-613.
17. Rodolfo, D. L., Jose, L. B. A. (2005). “Design and control strategies of PV-Diesel systems using genetic algorithms”, Solar Energy, 79, pp. 33-46.
18. Smith M. L., Panwalkar S. S. & Dudek R. A.(1975) “Flowshop sequencing problem with ordered processing time matrices”, Management Science, 21, pp. 544-549.
20. Toktas, B., Azizoglu, M. & Koksalan, S. K. (2004). “Two-machine flow shop scheduling with two criteria: Maximum earliness and makespan”, European Journal of Operational Research. 157, pp. 286-295.
21. Yang, D. L. & Chern, M. S. (1995). “A two-machine flowshop sequencing problem with limited waiting time constraints”, Computers ind. Engng. Vol. 28, No. 1, pp. 63-70.
22. Ying, K. C. & Liao, C. J. (2004). “An ant colony system for permutation flow-shop sequencing”, Computers & Operations Research. 31, pp.791-801.