物料規劃與配置為供應鏈規劃主要功能之一，目的在於各種規劃條件的限制之下，如何將各種可行的供給配置到各個獨立的需求，達成企業的需求目標。TFT-LCD傳統物料配置的做法，主要將個別的供給與需求進行優先權排序，進而進行配置的工作，但此舉往往只能求得有效解，而不是最佳解，不能完全達成企業的需求目標，降低更多的製造成本。
由於，基因演算法求解問題時，需花費大量的計算及時間的成本，當問題領域愈大，求解時間也將成指數成長，有鑑於此，本研究使用限制式基因演算，結合推理機制向前檢查 (Forward Checking)的概念，應用在TFT-LCD產業，解決物料規劃與配置最佳化的問題，求取產量最大化。

Material planning and allocation are main parts of supply chain management. It aims to locate various supplies to individual demand to satisfy enterprise’s goal under a lot of constraints of planning condition. The method of traditional TFT-LCD material planning is sorting individual supply and demand first, and then locating them. The solution produced by this method is just feasible, not optimal. It can not satisfy enterprise’s demand goal at all to decrease productive cost.
Due to, Genetic Algoritgm is needed a lot of computing time and cost to search solution. The computing time will increase exponentially by the size of problem, so we can not find the optimum quickly and efficiently. In this research, we will use constraint-based genetic algorithm that hybrid genetic algorithm and forward checking
to apply for material planning problem in TFT-LCD industrial to maximize productivity.

目錄
書名頁 i
論文口試委員審定書 ii
教育部授權書 iii
國科會授權書 iv
中文摘要 v
英文摘要 vi
誌謝 vii
目錄 viii
表目錄 x
圖目錄 xi

1. 緒論 1
1.1 研究背景與動機 1
1.2 研究目的與範圍 3
1.3 研究方法與步驟 4
1.4 論文架構 6
2. 文獻探討 7
2.1 供應鏈管理 7
2.2 物料規劃與配置之意義 8
2.3 限制條件滿足問題 9
2.4 向前檢索 (FORWARD CHECKING) 10
2.5 基因演算法 11
2.6 限制式基因演算法 13
3. 建立物料規劃與配置模式 15
3.1 物料規劃與配置問題描述 15
3.2 研究限制與假設 18
3.3 模式設計與相關說明 19
3.3.1. 代號及參數說明 19
3.3.2. 決策變數說明 20
3.3.3. 目標函數 20
3.3.4. 限制式說明 21
4. 研究方法 24
4.1 應用範例 24
4.2 限制式基因演算法 25
4.3 TFT-LCD之編碼/解碼 25
4.4 限制式推理機制 27
4.4.1. 限制式推理之日期限制 28
4.4.2. 限制式推理之替代料限制 30
4.5 適應值評估 35
4.6 基因運算元運作 36
5. 限制式基因演算法之應用及驗證 39
5.1 實驗流程 39
5.2 資料來源設計 40
5.3 資料產生 40
5.4 實驗設計 41
5.5 實驗結果與比較 43
5.6 實驗結果與探討 57
6. 結論與未來發展 61
6.1 結論 61
6.2 未來發展 62
參考文獻 63

中文文獻
[1]謝仲為，「先進規劃與排程系統應用於TFT-LCD 產業之研究」，民國九十一年，東海大學碩士論文。
[2]楊依倫，「以基因演算法為基礎之供應鏈物料配置決策系統」，民國九十年，東海大學碩士論文。
[3]黎漢林，「供應鏈管理與決策-最佳化方法之應用」，民國九十三年，儒林圖書公司。
[4]洪振創、湯玲郎，「物料管理」，民國九十二年，高立圖書公司。
[5]王淑珍，「台灣邁向液晶王國之秘」，民國九十二年，中國生產力中心出版。


英文文獻
[1]Ahmet, U., Adnan, A., “An Evolutionary Constraint Satisfaction Solution for Over the Cell Channel Routing,” Integration, the VLSI Journal, Vol. 37, Issue. 2, pp. 121-133, 2004.
[2]Banier, N., Brisset, P., “Optimization by Hybridization of a Genetic Algorithm and Constraint Satisfaction Techniques,” Proceeding of Evolutionary Computation, The 1998 IEEE World Congress on Computational Intelligence, pp. 645-649, 1998.
[3]Brailsford, S. C., Potts, C. N., and Smith, B. M., “Constraint Satisfaction Problems: Algorithms and Application,” European Journal of Operational Research, Vol. 119, No. 3, pp. 557-581, 1999.
[4]Bowen, J., Dozier, G., “Solving Constraint Satisfaction Problems Using a Genetic/Systematic Search Hybrid that Realized When to Quit,” Proceedings of the Sixth International Conference on Genetic Algorithms, pp. 122-129, 1995.
[5]Chen, J. F., “Component Allocation in Multi-echelon Assembly System with Linked Substitutes,” Computers and Industrial Engineering, Vol. 45, No. 5, pp. 43-60, 2003.
[6]Chiu, C. C., Hsu, P. L., “A Constraint-Based Genetic Algorithm Approach for Mining Classification Rules,” IEEE Transaction on Systems, Man, and Cybernetics, Vol. 35, No. 2, pp. 205-220, 2005.
[7]Clark, A. R., “Optimization Approximations for Capacity Constrained Material Requirements Planning,” International Journal of Production Economics, Vol. 84, No. 2, pp. 115-131, 2003.
[8]Craenen, B. G. W., “An Experimental Comparison of Three Different Heuristic Gas for Solving Constraint Satisfaction,” Internal Report 98-21, Department of Computer Science, Leiden University, pp. 1-22, 1999.
[9]Dechter, R., Pearl, J., “Network-Based Heuristic for Constraint Satisfaction Problem,” Artificial Intelligence, Vol. 34, No. 1, pp. 1-38, 1988.
[10]Deris, S., Omatu, S., Ohta, H., Kutar, C. S., and Samat, P. A., “Ship Maintenance Scheduling by Genetic Algorithm and Constraint-Based Reasoning,” European Journal of Operational Research, Vol. 112, No. 3, pp. 489-502, 1999.
[11]Dozier, G., Bowen, J., and Homaifar, A. A., “Solving Constraint Satisfaction Problems Using Hybrid Evolutionary Search,” Evolutionary Computation, IEEE Transactions on, Vol. 2, No. 1, pp. 23-33, 1998.
[12]Dozier, G., Bowen, J., and Bahler, D., “Solving Small and Large Constraint Satisfaction Problems Using a Heuristic-Based Micro-Genetic Algorithms,” Proceedings of the 2nd IEEE Conference on Evolutionary Computation, pp. 306-311, 1995.

[13]Eiben, A. E., Raue, P. E., and Ruttkay Z., “Solving Constraint Satisfaction Problems Using Ggenetic Algorithms,” Proceedings of the 1st International Conference on Evolutionary Computation, Vol. 2, pp. 542-547, 1995.
[14]Eiben, A. E., Raue, P. E., and Ruttkay, Z., Constraint Problems, Practical Handbook of Genetic Algorithms, CRC Press, pp. 307-365, 1995.
[15]Farley, G. A., “Discovering Supply Chain Management: A Roundtable Discussion,” American Production and Inventory Control Society- The Performance Advantage, Vol. 7, No. 1, pp. 38-39, 1997.
[16]Gen, M., Cheng, R., Genetic Algorithms and Engineering Design, John Wiley and Sons, Inc., 1997.
[17]Goldberg, D. E., Lingl, J. R., “Alleles, Loci and the Traveling Salesman Problem,” Proceedings of the International Conference on Genetic Algorithms and their Applications, pp. 154-159, 1985.
[18]Goldberg, D. E., Genetic Algorithms in Search, Optimization and Machine Learning, Addison Wesley, 1989.
[19]Gong, D., Yamazaki, G., and Gen, M., “Evolutionary Program for Optimal Design of Material Distribution System,” Evolutionary Computation, Proceedings of IEEE International Conference on, pp.139-143, 1996.
[20]Holland, J. H., “Adaptation in Natural and Artificial Systems,” Ann Arbor, The University of Michigan Press, 1975.
[21]Hung, Y. F., “A New Formulation Technique for Alternative Material Planning-An Approach for Semiconductor Bin Allocation Planning,” Computers and Industrial Engineering, Vol. 32, No. 2, pp. 281-297, 1997.


[22]Juite, W., “Constraint-Based Schedule Repair for Product Development Projects with Time-Limited Constraints,” International Journal of Production, Vol. 95, No. 3, pp. 399-414, 2005.
[23]Kennerley, M., Neely, A. D., “Enterprise Resource Planning: Analyzing the Impact,” Integrated Manufacturing System, Vol. 12, No. 2, pp. 103-113, 2001.
[24]Khoo, L. P., Ng, T. K., “A Genetic Algorithm-Based Planning System for PCB Component Placement,” International Journal of Production Economic, Vol. 54, No. 3, pp. 321-332, 1998.
[25]Kowalczyk, R., “Using Constraint Satisfaction in Genetic Algorithm,” Intelligent Information Systems, Australian and New Zealand Conference on, pp. 272-275, 1996.
[26]Kowalczyk, R., “Constraint Consistent Genetic Algorithms,” IEEE international Conference, pp. 343-348, 1997.
[27]Lee, H. L., Billington, C., “The Evolution of Supply Chain Management Models and Practice at Hewlett-Packard,” Interface, Vol. 25, No. 5, pp. 42-63, 1995.
[28]Riff, M. C., “Evolutionary Algorithm for Constraint Satisfaction,” Computer Science, XVIII International Conference of the Chilean Society of, pp. 158-165, 1998.
[29]Robinson, A. G., Dilts, D. M., “OR and ERP: Can Operation Research Play a Role in Fast-Growing, Enterprise-Wide Information System,” OR/MS Today, Vol. 26, No. 3, pp. 30-37, 1999.
[30]Sait, S. K., Youssef, H., Iterative Computer Algorithms with Applications in Engineering, IEEE book, 1999.


[31]Stadtler, H., “Supply Chain Management and Advanced Planning-Basic, Overview and Challenge,” European Journal of Operational Research, Vol. 163, No. 3, pp. 575-588, 2005.
[32]Tam, V., Stuckey, P., “An Efficient Heuristic-Based Evolutionary Algorithm for Solving Constraint Satisfaction Problem,” Intelligence and Systems, Proceedings, IEEE International Joint Symposia on, pp. 75-82, 1998.
[33]Thorntot, A. C., “The Use of Constraint-Based Design Knowledge to Improve the Search for Feasible Designs,” Engineering Applications of Artificial Intelligence, Vol. 9, No. 4, pp. 393-402, 1996.
[34]Tiwari, M. K., Tiwari, S. K., Roy, D., Vidyarthi, N. K., and Kamushwaran, S., “A Genetic Algorithm Based Approach to Solve Process Plan Selection Problem,” Proceedings of the Second International Conference on, Vol. 1, pp. 281-284, 1999.
[35]Tsang, E., Foundation of Constraint Satisfaction, Academic Press, 1993.
[36]Vidal, T., Archimede, B., and Coudert, T., “Distributed Forward Checking for Scheduling in Flexible Manufacturing,” Proceedings of 8th IEEE International Conference, Vol. 1, pp. 567-574, 2001.
[37]Wei, Y. M., Hu, Q. H., and Fan, Y., “Mathematical Model for the Optimization of the Allocation of Nonferrous Raw Materials in China,” Computers and Industrial Engineering, Vol. 46, No. 2, pp. 293-303, 2004.
[38]Yang, C. C., Yang, M. H., “Constraint Networks: A Survey,” IEEE International Conference on System, pp. 1930-1935, 1997.
[39]Zhou, G., Min, H., and Gen, M., “The Balanced Allocation of Customers to Multiple Distribution Centers in the Supply Chain Network: A Genetic Algorithm Approach,” Computers and Industrial Engineering, Vol. 43, No. 1-2, pp. 251-261, 2002.
[40]Zhang, J. Y., Sun, J. G., “A Hybrid Constraint Propagation Mechanism for Resource-Constrained Scheduling,” Proceedings of the Third Internattional Conference on Machine Learning and Cybernetic, Vol. 1, pp. 26-29, 2004.