臺灣博碩士論文加值系統

近年來人工智慧的方法已經廣泛且有效被應用在生產排程的問題上，其中包含了模糊理論（Fuzzy theory）、遺傳演算法（Evolutionary Algorithms）、類神經網路（Neural Network）等，而這些以人工智慧為基礎的方法，最困難的工作便是要具備對於問題相當深入了解的專家知識，另外在面對較大或較複雜的排程問題時，也會使得系統難以執行。本研究結合案例式推理和基因演算法，提出以案例式推理為基礎的基因演算法，透過案例式推理的技術來找出與目前問題相似的案例，並將這些過去解決過的案例中所得到的資訊，應用到基因演算法上以解決目前的問題，最後再將目前的問題儲存起來變成案例以便未來使用。經實驗結果可發現，以案例式推理為基礎的基因演算法，不僅可以得到一組很好的起始母體，而且可以很快達到收斂的效果，最後也可得到很好的最終解。

In this research, case-based reasoning and genetic algorithms are integrated into the case-based genetic algorithm in order to minimize the total weighted completion time for a single-machine scheduling problem with considering release times. This algorithm first retrieves the analogical cases from the case base then incorporates these analogies into the genetic algorithm to deal with the problem at hand. Finally, case-based genetic algorithm stores the solved problem in the case base for the future use. Extensive experimental results show that this approach outperforms the other three algorithms considered in the paper in both the computation time and the quality of solutions.

目錄
中文摘要 I
英文摘要 II
誌謝 III
目錄 IV
表目錄 VII
圖目錄 VIII
第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 2
1.3 研究方法 2
1.4 研究架構 3
第二章 文獻探討 5
2.1 動態排程 5
2.2 案例式推理 6
2.2.1 案例式推理應用之相關文獻 8
2.2.2 案例式推理應用於生產排程 9
2.3 基因演算法之介紹 10
2.3.1 基因演算法的相關名詞 10
2.3.2 基因演算法的演算流程 10
2.4 結合案例式推理與基因演算法之相關文獻 18
2.5 結語 20
第三章 問題定義 21
3.1 問題定義 21
3.2 模式之建構 22
3.2.1 符號說明 22
3.2.2 模式之限制與假設 23
3.2.3 績效衡量準則 23
第四章 研究方法 25
4.1 案例式推理架構 25
4.2 基因演算法架構 30
4.2.1 基因演算法相關符號說明 30
4.2.2 一般基因演算法之演算流程 30
4.2.3 以案例做為起始解的基因演算法之演算流程 34
4.2.4 以案例式推理為基礎的基因演算法之演算流程 38
第五章 實驗結果與分析 42
5.1 實驗問題產生 42
5.2 實驗方法 42
5.3 實驗結果分析 43
5.2.1 以案例做為起始解的基因演算法之實例驗證（a） 43
5.2.2 以案例做為起始解的基因演算法之實例驗證（b） 47
5.2.3 以案例式推理為基礎的基因演算法之實例驗證 49
第六章 結論與未來展望 55
6.1 結論 55
6.2 未來展望 56
參考文獻 57

參考文獻
[1] Aamodt, A., E. Plaza, “Case-Based Reasoning: Foundational Issues, Methodological Variations, and System Approaches,” Artificial Intelligence Communications, Vol. 7:1, pp.39-59, 1994.
[2] Madureira, A., C. Ramos, and S.C. Silva, “A Genetic Approach to Dynamic Scheduling for Total Weighted Tardiness Problem,” PLANSIG’99 (18th Workshop of the UK Planning and Scheduling Special Interest Group), Manchester (UK), 1999.
[3] Madureira, A., C. Ramos, and S.C. Silva, “A Genetic Approach for Dynamic Job-Shop Scheduling Problem,” 4th Metaheuristics International Conference, 2001.
[4] Break, K. R., Introduction to Sequencing and Scheduling, John Wiley, New Youk, 1974.
[5] Suresh, C., R. Traub, R. Uzsoy, “An iterative heuristic for the single machine dynamic total completion time scheduling problem,” Computers and Operations Research, Vol.23, No.7, pp.641-651, 1996.
[6] Chandra, R., “On n/1/F Dynamic Deterministic System,” Naval Research Logistics Quarterly, Vol. 26, pp.537-544, 1979.
[7] Deogun, J. S., “On shcduling with Ready Time to Minimize Mean Flow Time,” The Computer Journal, Vol. 26, No 4, pp.320-328, 1983.
[8] Dessouky, M. I., and J. S. Deogun, “Sequencing jobs with unequal ready times to minimize mean flow times,” SIAM Journal Computing, Vol. 10, pp.192-202, 1981.
[9] Hariri, A. M. A., and C. N. Potts, “An Algorithm for Single Machine Sequencing with Release Dates to Minimize Total Weighted Completion Time,” Discrete Applied Mathematics, Vol 5, pp. 99-103, 1983.
[10] Igor, J., J. Mylopoulos, J. Glasgow, H. Shapiro, and R. F. Casper, “Case-Based Reasoning in IVF: Prediction and Knowledge Mining,” Artificial Intelligence in Medicine, pp.1-14, 1998.
[11] Job, D., V. Shankararaman, and J. Miller, “Combining CBR and GA for Designing FPGAs,” Third International Conference on Computational Intelligence and Multimedia Applications, New Delhi, India, pp. 133, 1999.
[12] Kempf, K. G., C. L. Pape, S. F. Smith, and B. Fox, “Issues in the design of AI-based schedulers: Workshop report,” Artificial Intelligence Magazing, pp.37-46, 1991.
[13] Kotono, P., “SMART plan: A case-based resource allocation and scheduling system,” Proceedings of the Case-Based Reasoning Workshop, Pensacola, FL, pp. 285-294, 1989.
[14] Leake, D. B., Case-Based Reasoning: experiences, lessons, and future directions, MIT Press, Massachusetts Institute of Technology, Cambridge, Massachusetts and London, England, 1996.
[15] Lenstra, K. J., A. H. G. Rinnooy, and P. Brucker, “Complexity of Machine Scheduling Problems,” Annals of Discrete Mathematics, pp. 343-362, 1977.
[16] Liu, J., and B. L. MacCarthy, “Effective heuristic for the single machine sequencing problem with ready times,” International Journal of Production Research, Vol. 29, pp.1521-1533, 1991.
[17] Louis, S. J., and Z. Xu, “Genetic Algorithms for Open Shop Scheduling and Re-Scheduling,” In Proceedings of the ISCA 11th International Conference on Computers and Their Applications, pp. 99-102, 1996.
[18] Louis, S. J. and L. Gong, ” Genetic Algorithms with Memory for Traveling Salesman Problems”, 1997.
[19] Miyashita, K., “Case-based knowledge acquisition for schedule optimization,” Artificial Intelligence in Engineering, 1995.
[20] Munoz, A., H., J. A. Hendler, and D. W. Aha, “Conversational Case-based Planning,” Review of Applied Expert Systems 5, pp.163-174, 1999.
[21] Murata, T. and H., Ishibuchi, and H., Tanaka, “Genetic Algorithm for Flowshop Scheduling Problem,” International Journal of Computers and Industrial Engineering, 30, pp.1061-1071, 1996.
[22] Oman, S. and P. Cunningham, “Using Case Retrieval to Seed Genetic Algorithms”, International Journal of Computational Intelligence and Applications, Vol. 1, No. 1, 2001, pp71-82.
[23] Ramsey, C., and J. Grefensttete, “Case-based initialization of genetic algorithms,” Proceeding of the Fifth International Conference on Genetic Algorithms, San Mateo, California, 1993.
[24] Schank, R., Dynamic Memory: A Theory of Learning in Computers and People, New York: Cambridge University Press, 1982.
[25] Schmidt, G., “Case-based reasoning for production scheduling,” International Journal of Production Economics, 1998.
[26] Sheppard, J. W., and S. L. Sakzburg, “Combining genetic algorithms with memory based reasoning,” Proceedings of the Sixth International Conference on Genetic Algorithms, San Mateo, California, 1995.
[27] Suh, M. S., W. C. Jhee, Y. K. Ko, and A. Lee, “A case-based expert system approach for quality design,” Expert Systems With Applications 15, pp.181-190, 1998.
[28] Symth, B., “Constructing Competent Case based Reasoners: Theories, Tools and Techniques,” Proceedings of the Workshop on Automating the Construction of Case Based Reasoners, Stockholm, Sweden, 1999.
[29] Ting, C. K., S. T. Li, and C. N. Lee, “TGA: A New Integrated Approach to Evolutionary Algorithms”, Congress on Evolutionary Computation (CEC2001), pp.917-924, 2001.
[30] Watson, I., and F. Marir, “Case-Based Reasoning: A Review,” Knowledge Engineering Review, Vol.9, No.4, 1994.
[31] Xu, L. D., “An integrated rule- and case-based approach to AIDS initial assessment,” International Journal of Bio-Medical Computing, 1996.
[32] 邱竣鋒，「利用模擬退火法及塔布搜尋法求解工件非同時到達之單機排程問題」，私立元智大學工業工程與管理研究所，碩士論文，民國八十七年。
[33] 徐慧君，「應用案例式推理於顧客關係管理之行銷研究-以化妝品業為例」，私立元智大學工業工程與管理研究所，碩士論文，民國九十一年。
[34] 陳振男，「非同時到達工件之單機排程-以總加權完工時間最小為目標」，私立元智大學工業工程與管理研究所，碩士論文，民國八十三年。
[35] 謝日章，「柔性計算於生產管理之應用」，私立元智大學工業工程與管理研究所，博士論文，民國九十一年。