本論文的主要研究範圍於印刷電路板產業電子專案人力排程最佳化。在專業電子製造服務業（Electronics Manufacturing Services，EMS）的領域中，對於電子產品品質的考量通常將電子產品的工作流程以建置、檢查、驗證來確保正確性，在目前產業裡仍然以傳統方式來進行工作處理流程的排程規劃，這不僅增加了專案負責人（Project Manager，PM）的工作量，而且在沒有精確計算的安排下也可能導致專案處理流程的阻塞，所以專案處理流程的排程規劃低效率是目前待解決的嚴重問題。面對日益增長的EMS行業需求，傳統的排程規劃經常會引起一些問題，例如延遲交付，延遲批量生產，甚至公司的收入損失。實際上電子圖樣類型、工程師能力和交貨期相關的作業調度非常複雜，不適合以人工方式進行處理，欲解決此問題希望是可以揮別過去的作業方式。人工智慧在過去十年中，具有解決優化問題的巨大潛力，特別是基因演算法（GA）是優化作業調度的可行解決方案之一。然而傳統的基因演算法的染色體設計對於我們的排程問題並不適用在此次要解決的問題，因此在本研究中，運用以熵約束基因演算法，此方法具有下列特色：(1)由二維基因編碼的方式、(2)增加熵評估群體適應值組成、(3) 提出基因換種機制增加多樣性，以提高求解的效率和準確性。如果熵值降低，則啟動染色體群體換種機制。實驗結果進行分析之後，發現加入熵約束群體的多樣性來啟動群體染色體換種機制可以有效地降低演化世代迭代的次數，並將系統所搜尋出來的解的改善率降低10％。

The main scope of this research is to explore the job schedule of the electronic part manipulation. The part manipulations, including creation, checking, verification, are common in the Electronic Manufacture Service(EMS) industry. The traditional way still depends on manual scheduling which not only increases the workload of project managers(PM) but also causes production schedule jams without precise calculation arrangements. Low efficiency and reliability are the serious problems. It is hard to face the demand of EMS industry increasing day by day. The traditional scheduling often causes some problems, such as late delivery, delay the mass production, even revenue loss of the company. Actually, the job scheduling involved with part types, engineer capability and delivery due are very complicated and not suitable for PM to handle. In addition, artificial intelligence, in the last decade, demonstrates the charming potential to solve optimization problem. Especially, Genetic Algorithm(GA) is one of feasible solutions for the optimization of job scheduling. However, the chromosome designs of GA are not realistic for our scheduling problem. Therefore, in this study, the genetic algorithm constrained by entropy is used. This method has the following characteristics: (1) composed of two-dimensional gene coding, (2) increased entropy to assess the fitness value of the population, and (3) proposed a gene exchange mechanism to increase diversity to improve the efficiency and accuracy of the solution. If the entropy value is low, the exchange mechanism of chromosome is started. After analyzing the results of the experiment, we found that entropy-constrained to guarantee the chromosome diversity to start the major replacement mechanism(MRM) can reduce effectively generation times and reduce the solution improvement rate by 10%.

摘要 iv
Abstract v
誌謝 vii
表目錄 xi
圖目錄 xii
第一章 緒論 1
1.1 前言 1
1.2 研究動機 3
1.3 研究目的 6
1.4 論文架構 7
第二章 文獻探討 8
2.1 印刷電路板電子圖樣品質管理排程問題探討 8
2.2 Entropy 熵 9
2.2.1 Entropy 熵由來 9
2.2.2 多類熵介紹與特性 9
2.3 基因演算法 10
2.3.1 演化式運算介紹 10
2.3.2 基因演算法特點 11
2.3.3 基因演算法流程 11
2.3.4 運算初始編碼 12
2.3.5 產生初始群體 13
2.3.6 適應性函數定義 13
2.3.7 演化選擇機制、演化複製機制 14
2.3.8 演化交配機制 16
2.3.9 突變機制 17
2.4 小結 18
第三章 以熵約束多樣性二維基因演算法為基礎的異質工件人力排程最佳化技術 19
3.1 最佳化專案人力排程應用情境 19
3.2 系統架構 20
3.3 系統流程 21
3.4 資料編碼模組設計 23
3.4.1 專案電子圖樣處理階段編碼子模組設計 23
3.4.2 專案電子圖樣時間編碼子模組設計 26
3.4.3 基因編碼子模組設計 27
3.4.4 資料編碼染色體呈現方式 28
3.5 以熵約束群體多樣性與換種機制設計 29
3.6 最佳化目標適應值函數設計 31
3.7 世代最佳搜尋適應值評估設計 33
3.7.1 硬式懲罰函數設計 33
3.7.2 軟式懲罰函數設計 34
3.8 演化式選擇運算設計 35
3.9 演化式交配運算設計 37
3.10 演化式突變運算設計 39
3.11 停止原則機制 41
第四章 系統實作與分析 42
4.1 實驗目的 42
4.1.1 實驗環境介紹 42
4.2 實驗參數設計 43
4.2.1 實驗一懲罰函數權重設計 44
4.2.2 實驗二演化式交配機制參數設計 45
4.2.3 實驗三演化式突變機制參數設計 46
4.2.4 實驗四以熵約束多樣性評估觀察與參數設計 47
4.2.5 實驗五啟動換種機制群體擇優保留數量參數設計 48
4.3 系統基因演算法搜尋能力比較 49
4.3.1 調整專案電子圖樣顆數的系統搜尋能力 49
4.3.2 調整人員數量系統的搜尋能力 51
4.3.3 以熵值約束群體多樣性系統搜尋能力 53
第五章 結論與未來展望 56
5.1 結論 56
5.2 未來與展望 57
參考文獻 58
Turnutin系統比對報告 63
論文口試問題修訂 64

[1]寶來證券, “EMS產業的過去與未來展望”, [Online]. Available: https://www.moneydj.com/kmdj/report/reportviewer.aspx?a=4ec17492-2d7d-418d-8fcf-5a07836809cc

[2]EPS News, “Global EMS Market Reaches $555 Billion in 2019”,[Online].Available: https://epsnews.com/2020/07/02/global-ems-market-reaches-555-billion-in-2019/

[3] Thu-Hua Liu, A. J. C. Trappey And Fu-Wei Chan, “A Scheduling System for Ic Packaging Industry Using Step Enabling Technology”, IEEE Transactions on Components Packaging and Manufacturing Technology: Part C, Vol. 20, pp. 256-267, 1997.

[4] Zimu Guo, Jia Di, Mark M. Tehranipoor, And Domenic Forte, “Obfuscation-Based Protection Framework Against Printed Circuit Boards Unauthorized Operation and Reverse Engineering” ACM Transactions on Design Automation of Electronic Systems, Vol. 22, pp. 1-54, 2017

[5] Korhonen, Heidi , Heikkilä, Jussi , Törnwall, “A Simulation Case Study of Production Planning and Control in Printed Wiring Board Manufacturing”, Proceedings of The 33nd Conference on Winter Simulation, VTT Technical Research Centre of Finland, pp. 844-847, 2001

[6] C. A-Da, C. Cheng-Bin, “An Efficient Solution to Cyclic Scheduling of A No-Wait Reentrant Serial-Parallel PCB Production Line”, 2007 International Conference on Management Science and Engineering, Harbin, pp. 746-751, 2007

[7] S. Lee, T. Lee, “Scheduling A Multi-Chip Package Assembly Line With Reentrant Processes and Unrelated Parallel Machines”, 2008 Winter Simulation Conference, Miami, FL, USA, pp. 2286-2291, 2008

[8] Zhihong Jin, Ying Liu, Shaoying Jing, “The Optimization of Printed Circuit Board Assembly Scheduling for A Large Parallel System”, 2008 IEEE International Conference on Service Operations and Logistics, and Informatics, Beijing, pp. 2651-2655, 2008

[9] J. Leung, Guoqing Zhang, “Optimal Cyclic Scheduling for Printed Circuit Board Production Lines with Multiple Hoists and General Processing Sequence”, in IEEE Transactions on Robotics and Automation, Vol. 19, No. 3, pp. 480-484, 2003

[10] A. J. Zaylaa, A. Harb, F. I. Khatib, Z. Nahas , F. N. Karameh, “Entropy Complexity Analysis of Electroencephalographic Signals During Pre-Ictal, Seizure and Post-Ictal Brain Events”, 2015 International Conference on Advances in Biomedical Engineering (ICABME), Beirut, pp. 134-137, 2015

[11] Y. Song, X. Tian, W. Bai, T. Liu And F. Meng, “The Inhibitive Effect of rTMS On Entropy Coding of Firing Neuron at Hippocampus for Temporal Lobe Epilepsy Rats”, 2008 Fourth International Conference on Natural Computation, Jinan, pp. 597-600, 2008

[12] C. Ahlstrom, K. Hoglund, P. Hult, J. Haggstrom, C. Kvart And P. Ask, “Assessing Aortic Stenosis Using Sample Entropy of The Phonocardiographic Signal in Dogs”, in IEEE Transactions on Biomedical Engineering, Vol. 55, No. 8, pp.2107-2109, 2008

[13] Afsal S., Rafeeq Ahamed K., Jijo Jothykumar, S. Ahmed, F. Sayeed, “A Novel Approach for Palm Print Recognition Using Entropy Information Features”, Proceeding of International Conference on Wireless Communications, Signal Processing and Networking (Wispnet), Ssn College of Engineering, Thailan, Chenmei, pp.1439-1442, 2016

[14] Bing-Fei Wu, Hung-Hseng Hsu, “Entropy-Constrained Scalar Quantization and Minimum Entropy with Error Bound by Discrete Wavelet Transforms in Image Compression”, in IEEE Transactions on Signal Processing, Vol. 48, No. 4, pp.1133-1143, 2000

[15] J. Wang, J. Pan, X. Wu, “The Entropy Source Of Pseudo Random Number Generators: from Low Entropy to High Entropy”, 2019 IEEE International Conference on Intelligence and Security Informatics (ISI), Shenzhen, China, pp. 161-163, 2019

[16] G. Tian Et Al., “Adjustable Piecewise Entropy For Network Traffic Anomaly Detection”, 2015 IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), Hong Kong, pp. 59-60, 2015

[17] V. M. Elizondo, M. S. Derpich, “Maximum Expected Rates of Block-Fading Channels with Entropy-Constrained Channel State Feedback”, in IEEE Transactions on Communications, Vol. 61, No. 2, pp. 576-589, 2013

[18] H. Jegou, C. Guillemot, “Entropy Coding With Variable-Length Rewriting Systems”, in IEEE Transactions on Communications, Vol. 55, No. 3, pp. 444-452, 2007

[19] Li-Sheng Xu, Kuan-Quan Wang, Lu Wang, “Gaussian Kernel Approximate Entropy Algorithm for Analyzing Irregularity of Time-Series”, 2005 International Conference on Machine Learning And Cybernetics, Guangzhou, China, Vol. 9, pp. 5605-5608, 2005

[20] A. Fujino, N. Ueda And K. Saito, “Semisupervised Learning for A Hybrid Generative/Discriminative Classifier Based on The Maximum Entropy Principle”, In IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 30, No. 3, pp. 424-437, 2008

[21] F. Wan, P. Wei, Z. Han, J. Jiao And Q. Ye, "Min-Entropy Latent Model for Weakly Supervised Object Detection," in IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 41, No. 10, pp. 2395-2409, 2019

[22] Luis Serrano, “Shannon Entropy, Information Gain, and Picking Balls from Buckets”, [Online] Available: Https://Medium.Com/Udacity/Shannon-Entropy-Information-Gain-And-Picking-Balls-From-Buckets-5810d35d54b4

[23] A. Fatima, R. Maurya, M. K. Dutta, R. Burget, J. Masek, “Android Malware Detection Using Genetic Algorithm Based Optimized Feature Selection and Machine Learning”, 2019 42nd International Conference on Telecommunications and Signal Processing (TSP), Budapest, Hungary, pp. 220-223, 2019

[24] C. Zheng And Z. Guangming, “Application on Express Delivery of An Immune Genetic Algorithm Based on Machine Learning”, 2009 Second International Symposium on Computational Intelligence and Design, Changsha, pp. 165-167, 2009

[25] P. Surekha, P. M. Raajan And S. Sumathi, “Genetic Algorithm and Particle Swarm Optimization Approaches to Solve Combinatorial Job Shop Scheduling Problems”, 2010 IEEE International Conference on Computational Intelligence and Computing Research, Coimbatore, pp. 1-5, 2010

[26] Y. Wang, H. Li And H. Liu, “Multi-Agent and Hybrid Genetic Algorithm Approach for Distributed Jobshop Scheduling”, 2008 International Conference on Apperceiving Computing and Intelligence Analysis, Chengdu, pp. 404-407, 2008

[27] Y. M. Wang, G. Z. Zhao, H. L. Yin, “Genetic Algorithm with Three Dimensional Chromosome for Large Scale Scheduling Problems”, Proceedings of The 10th World Congress on Intelligent Control and Automation, Beijing, pp. 362-367, 2012

[28] K. Nazarpour, S. Ebadi, S. Sanei, “Fetal Electrocardiogram Signal Modelling Using Genetic Algorithm”, 2007 IEEE International Workshop on Medical Measurement and Applications, Warsaw, pp. 1-4, 2007

[29] S. Wu, C. Chou, C. Wu And T. Lee, “Inference of Genetic Network of Xenopus Frog Egg : Improved Genetic Algorithm”, 2006 International Conference of The IEEE Engineering in Medicine and Biology Society, New York, pp. 4147-4150, 2006

[30] John Mccall, “Genetic Algorithms for Modelling and Optimization”, [Online]. Available:https://www.sciencedirect.com/ccience/article/pii/s0377042705000774