近年來，我們可見到排程的觀念被普遍廣泛應用於不同的領域上，如何得到一個適當的排程，對決策管理者而言顯得格外重要。且大多數的排程(scheduling)問題已被歸類為NP-complete問題，因此現今有許多研究方法被提出來探討各種不同的排程問題，像是模糊理論(fuzzy logic)、類神經網路(neural networks, NN)、基因演算法(genetic algorithm, GA)、螞蟻演算法(ant colony optimization, ACO)和粒子群演算法(particle swarm optimization, PSO)。或者是各種整合技術，如Fuzzy+GA、GA+Fuzzy和Fuzzy+NN等等，其中關於分類的fuzzy c-means 與Hopfield neural network的整合被公認為最有效率的分類方法，然後大部分的應用都侷限於二維的應用問題。
在本篇論文中，我們將二維的模糊霍普菲爾類神經網路(fuzzy Hopfield neural network, FHNN)擴展至三維的網路，這種處理方法就是將排程問題視為分類問題並且利用叢集(clustering)技術來求解排程問題。亦即在某時間上的工作當作我們所要分類的資料樣本(data sample)以及機器類比於一群聚(cluster)。另外，本文應用了三種解模糊化的策略，分別為競爭式學習法則、輪盤法以及虛擬化比例式隨機規則，並且也針對各個實驗進行模擬與比較。
此研究應用在一個多處理器之排程問題，且必須滿足工作不可遷徙和其時間條件(執行時間和時間限制)之下。模擬結果說明了整合模糊分群演算法和霍普菲爾類神經網路用於求解多維度排程問題的可行性及未來展望。

In recent years, the concept of scheduling has been widely applied to various applications. How to get a proper scheduling; in terms of decision-making managers has become more and more important. Most of the scheduling application problems are confirmed to be the NP-complete problems. Therefore, a variety of research methods are introduced in solving these scheduling problems, such as fuzzy logic, neural network (NN), genetic algorithm (GA), ant colony optimization (ACO) algorithm and particle swarm optimization (PSO) algorithm. Moreover, many integrations of above stated schemes are also proposed to improve the efficiency. Among them, fuzzy Hopfield neural network which integrated fuzzy c-means into Hopfield neural network to become a famous clustering method. However, most applications using FHNN are limited in solving two dimensional problems.
In this work, a 2-D fuzzy Hopfield neural network (FHNN) is expanded into a three dimensional (3-D) network for solving the scheduling problems of multiprocessor scheduling problems. Restated, a processor is regarded as a cluster in multivariable scheduling problem. Moreover, three defuzzification strategies are applied and simulated; they are competition rule, roulette wheel selection rule (random-proportional rule) and pseudo-random-proportional rule.
This investigation employs the suggested approach to resolve multiprocessor scheduling problems with time constrains (execution time and deadline) and no migration allowed. Simulation results illustrate that the proposed 3-D fuzzy Hopfield neural network involving proposed defuzzification strategies provides an appropriate approach for solving this class of scheduling problems effectively.

摘要 III
ABSTRACT IV
誌謝 V
目錄 VI
表目錄 VIII
圖目錄 IX
1 緒論 1
1.1 研究背景 1
1.2 研究動機 2
1.3 研究方法 3
1.4 研究架構與流程 4
2 文獻探討 7
2.1 排程問題 7
2.2 文獻回顧與探討 8
2.2.1 求解最佳化問題方法的整理 8
2.2.2 多處理器排程問題文獻整理 14
3 三維模糊霍普菲爾類神經網路 19
3.1 類神經網路 19
3.1.1 生物神經元模型(biological neuron) 21
3.1.2 人工神經元模型(artificial neuron) 22
3.1.3 類神經網路模式的分類 24
3.1.4 類神經網路的特性 25
3.2 霍普菲爾類神經網路 27
3.2.1 網路架構與觀念 28
3.2.2 數學公式表示法 29
3.3 模糊分群(fuzzy clustering) 30
3.3.1 模糊理論(fuzzy theory) 30
3.3.2 模糊分群法 32
3.4 結合三維霍普菲爾類神經網路與模糊分群法 36
3.4.1 簡介 36
3.4.2 架構與演算法 37
4 3D FHNN求解排程問題 41
4.1 排程問題敘述 41
4.2 變數定義與說明 42
4.3 數學模式之建構 44
4.4 解模糊化過程 62
5 實驗結果與比較 66
5.1 實驗問題描述與假設 66
5.2 實驗模擬結果 68
5.2.1 實驗一:四個工作，二部機器 68
5.2.2 實驗二:五個工作，二部機器 69
5.2.3 實驗三:十個工作，二部機器 71
5.2.4 實驗四:十個工作，三部機器 72
5.2.5 實驗五:二十個工作，二部機器 74
5.2.6 實驗六:三十個工作，二部機器 75
5.2.7 實驗七:五十個工作，二部機器 77
6 結論、未來工作 83
參考文獻 85
個人簡歷 91

[1] L. A. Zadeh, “Fuzzy sets,” Information and Control, Vol. 8, No.3, pp. 338–353, 1965.
[2] J. H. Holland, “Adaptation in natural and artificial systems, Ann Arbor,” MI: The University of Michigan Press, 1975.
[3] S. Kirkpatrick, C. D. Gelatt and M. P. Vecchi., “Optimization by simulated annealing”, Science, Vol.220, No.4598, pp. 671-80, 1983.
[4] F. Glover, “Tabu search-PartⅠ,” ORSA Journal on Computing ,Vol. 1, pp. 4-32, 1990.
[5] F. Glover, “Tabu search-PartⅡ,” ORSA Journal on Computing ,Vol. 1, pp. 4-32, 1990.
[6] A. Colorni, M. Dorigo, and V. Maniezzo, “Distributed optimization by ant colonies,” in Proceedings of the First European Conference on Artificial Life, pp.134-142, MIP Press, Cambridge, MA, 1991.
[7] M. Dorigo, “Optimization, learning and natural algorithms,” Ph.D. Thesis, Italy, 1992.
[8] J. Kennedy and R. Eberhart, “Particle swarm optimization,” IEEE International Conference on, Vol.4, pp. 1942-1948, 1995.
[9] S. C. Cheng and Y. M. Huang, “Scheduling Multi-Processor Tasks with Resource and Timing Constraints Using Genetic Algorithm,” The 5th IEEE International Symposium on Computational Intelligence in Robotics and Automation, Japan, July 2003.
[10] M. Golub and S. Kasapovic, “Scheduling multiprocessor tasks with genetic algorithms” Proceedings of the IASTED International Conference Applied Informatics, Innsbruck, Austria, pp. 273-278, February 2002.
[11] E. S. H. Hou, N. Ansari and H. Ren, “A Genetic Algorithm for Multiprocessor Scheduling”, IEEE Transactions on Parallel and Distributed Systems, Vol. 5 No. 2, pp. 113-120, Feb. 1994.
[12] M. Bohler, F. Moore and Y. Pan, “Improved Multiprocessor Task Scheduling Using Genetic Algorithms” Proceedings of the Twelfth International FLAIRS Conference, pp. 140 - 146 ,1999.
[13] M. S. Jelodar, S. N. Fakhraie, F. Montazeri, S. M. Fakhraie and M. N. Ahmadabadi, “A representation for genetic-algorithm-based multiprocessor task scheduling,” IEEE Congress on Evolutionary Computation Sheraton Vancouver Wall Centre Hotel, Vancouver, BC, Canada, July 16-21, 2006.
[14] A. M. Rahmani and M. A. Vahedi, “A novel task scheduling in multiprocessor systems with genetic algorithm by using elitism stepping method,” INFOCOMP – Journal of Computer Science, Vol. 7, No 2, pp.58-64, 2008.
[15] S. Jin, G. Schiavone and D. Turgut, “A performance study of multiprocessor task scheduling algorithms,” J. Supercomputer., Vol. 43, No.1, pp.77–97, 2008.
[16] O. H. Ibarra and C. E. Kim, “Heuristic algorithms for scheduling independent tasks on non-identical processors,” Journal of the ACM, Vol. 24, No.2, pp. 280–289, 1997.
[17] G. L. Djordjevic and M. B. Tosic, “Heuristic for scheduling task graphs with communication delays onto multiprocessors,” Parallel Compute, Vol. 22, No.9, pp.1197–1214, 1996.
[18] S. Russell and P. Norvig, “Artificial intelligence, a modern approach,” Pearson Education, Ch 5, pp 139–172, 2003.
[19] R. D. Chamberlain, M. N. Edelman, M. A. Franklin and E. E. Witte, “Simulated annealing on a multiprocessor,” Computer Design: VLSI in Computers and Processors, pp 540–544, 1988.
[20] Y. T. Nobuo , N. Sannomiya and Y. Xu, “A tabu search with a new neighborhood search technique applied to flow shop scheduling problems,” Decision and Control, Vol.5, pp 4606–4611,2000.
[21] B. S. Macey and A. Y. Zomaya , “A performance evaluation of CP list scheduling heuristics for communication intensive task graphs,” Parallel Processing Symposium, pp. 538–541 ,1998.
[22] T. L. Adam, K. M. Chandy and J. R. Dickson, “A comparison of list schedules for parallel processing systems,” Communications of the ACM, Vol. 17, No. 12, pp.685–690, 1974.
[23] B. Kruatrachue and T. Lewis, “Duplication scheduling heuristic DSH: A new precedence task scheduler for parallel processing systems,” PhD thesis, Oregon State University, Corvallis, OR, 1987.
[24] B. Kruatrachue and T. Lewis, “Grain size determination for parallel processing, “ IEEE Software ,Vol. 5,No. 1, pp.23–32, 1998.
[25] A. Basu and S. Funk, “An Optimal Scheme for Multiprocessor Task Scheduling: a Machine Learning Approach,” The 30th IEEE Real-Time Systems Symposium, December 4, 2009.
[26] K. Dahal, A. Hossain, B. Varghese, A. Abraham, F. Xhafa, and A. Daradoumis, “Scheduling in Multiprocessor System Using Genetic Algorithms,” In Proceedings of the Genetic Engineering and Evolutionary Computation Conference, June 2005.
[27] S. Funk and V. Nadadur, “LRE-TL: An Optimal Multiprocessor Scheduling Algorithm for Sporadic Task Sets,” 17th International Conference on Real-Time and Network Systems, Paris, France, pp. 159-168, October 2009.
[28] A. Agarwal, “A NeuroGenetic Approach for Multiprocessor Scheduling,” Multiprocessor Scheduling, Theory and Applications, I-Tech Education and Publishing, Vienna, Austria, pp.436, December 2007.
[29] S. N. Sivanandam and P. Visalakshi “Multiprocessor Scheduling Using Hybrid Particle Swarm Optimization with Dynamically Varying Inertia,” International Journal of Computer Science & Applications, Vol. 4, No. 3, pp 95-106 ,2007.
[30] H. Chen and A. M. K. Cheng, “Applying Ant Colony Optimization to the Partitioned Scheduling Problem for Heterogeneous Multiprocessors,” ACM, Vol.2, No, 2, pp.11-14, 2005.
[31] P. Switalski and F. Seredynski, “Generalized Extremal Optimization for Solving Multiprocessor Task Scheduling Problem” in Proceedings of the 7th International Conference on Simulated Evolution and Learning, Vol. 5361, pp.161-169, 2008.
[32] P. Switalski and F. Seredynski, “Multiprocessor task scheduling based on GEO metaheuristic,” 2009 IEEE International Symposium on Parallel & Distributed Processing, May 2009.
[33] G. Ritchie, “Multi-processor Scheduling with Ant Colony Optimization & Local Search,” Master of Science thesis, University of Edinburgh, 2003.
[34] R. M. Chen, S. T. Lo and Y. M. Huang, “Combining competitive scheme with slack neurons to solve real-time job scheduling problem,” Expert Systems with Applications, Vol. 33, No. 1, pp.75-85, July 2007.
[35] Y. M. Huang and R. M. Chen, “Scheduling multiprocessor job with resource and timing constraints using neural networks,” IEEE Trans. On Systems, Vol. 29, No.4, pp. 490-502, August 1999.
[36] R. M. Chen, Y. M. Huang, “Competitive neural network to solve scheduling problems,” Neurocomputing, Vol. 37 pp. 177-196, April 2001.
[37] T. C. Chiang, P. Y. Chang and Y. M. Huang, “Multiprocessor tasks with resource and timing constraints using particle swarm optimization,” International Journal of Computer Science and Network Security, Vol. 6, No. 4, April 2006.
[38] R. C. Correa, A. Ferreira and P. Rebreyend, “Scheduling multiprocessor tasks with genetic algorithms” Parallel and Distributed Systems,Vol.10, No.8, pp. 825-837,1999.
[39] A. S. Wu, H. Yu, S. Jin, K.C. Lin, and G. Schiavone, “An Incremental Genetic Algorithm Approach to Multiprocessor Scheduling,” IEEE Transactions on parallel and distributed systems, Vol. 15, No. 9, September 2004.
[40] B. Kruatrachue and T.G. Lewis, “Duplication Scheduling Heuristic, a New Precedence Task Scheduler for Parallel Systems,” Technical Report 87-60-3, Oregon State Univ., 1987.
[41] I. Ahmad and Y. Kwok, “On Exploiting Task Duplication in Parallel Program Scheduling,” IEEE Trans. Parallel and Distributed Systems, vol. 9, no. 9, pp. 872-892, 1998.
[42] S. T. Lo , R. M. Chen , Y. M. Huang and C. L. Wu, “Multiprocessor system scheduling with precedence and resource constraints using an enhanced ant colony system” Expert Systems with Applications, Vol34,pp. 2071–2081,2008.
[43] 王進德、蕭大全，類神經網路與模糊控制理論入門，全華科技圖書，2003。
[44] 葉怡成，類神經網路模式應用與實作，儒林圖書有限公司，2004年。
[45] J. J. Hopfield, “Neural networks and physical systems with emergent collective computational abilities,” PNAS, Vol. 79, No. 8, pp. 2554-2558, 1982.
[46] J. J. Hopfield and D. W. Tank, “Neural computation of decision in optimization problems,” Biological Cybernetics, Vol. 52, pp. 141-152, 1985.
[47] J. J. Hopfield and D. W. Tank, “Computing with neural circuits: A model,” Science, pp. 625-633, 1986.
[48] J. B. MacQueen , “Some Methods for classification and Analysis of Multivariate Observations,” Proceedings of 5-th Berkeley Symposium on Mathematical Statistics and Probability, Berkeley, University of California Press, Vol. 1,pp. 281-297, 1967.
[49] J. C. Dunn, “A Fuzzy Relative of the ISODATA Process and Its Use in Detecting Compact Well-Separated Clusters,” Journal of Cybernetics, Vol.3, pp. 32-57, 1974.
[50] J. C. Bezdek, “Pattern Recognition with Fuzzy Objective Function Algorithms,” Plenum Press, New York, 1981.
[51] J. S. Lin, “Image vector quantization using an annealed Hopfield neural network,” Optical Engineering,” Vol. 38, No.4, pp. 599-605, 1999.
[52] J. S. Lin, K. S. Cheng and C.W. Mao, “The application of competitive Hopfield neural network to medical image segmentation,” IEEE Transactions on Medical Imaging, Vol.15, pp. 560-567, 1996.
[53] J. S. Lin, K. S. Cheng and C.W. Mao, “Multispectral magnetic resonance image segmentation using fuzzy Hopfield neural network,” International Journal of Bio-Medical Computing, Vol.42, pp.205-214, 1996.
[54] J. S. Lin, K. S. Cheng and C. W. Mao, “A fuzzy Hopfield neural network for medical image segmentation,” IEEE Trans. On Nuclear Science, Vol. 43, No. 4, August 1996.
[55] Chang and Y. T. Ching, “Fuzzy Hopfield neural network with fixed weight for medical image segmentation,” Optical Engineering, Vol. 41, pp.351-358, 2002.
[56] M. Kaya, “A new image clustering and compression method based on fuzzy Hopfield neural network,” IJCI Proceedings of International Conference on Signal Processing, Vol.1, No.2, pp.11-16, 2003.
[57] R. M. Chen, Y. M. Huang, “Multiprocessor task assignment with fuzzy Hopfield neural network clustering technique,” Neural computing and applications, pp. 12-21, 2001.
[58] Y. J. Shen and M. S. Wang, “New resource management strategy for wireless cellular networks,” Computers and electrical engineering, pp.135-146, 2006.
[59] Y. J. Shen and M. S. Wang, “Broadcast scheduling in wireless sensor networks using fuzzy Hopfield neural network,” Expert systems with applications, pp.900-907, 2008.
[60] P. Campadelli, “Color image segmentation using Hopfield networks,” Image and Vision Computing, Vol.15, No.3, pp.161-166, March 1997.
[61] R. Sammouda and M. Sammouda, “Improving the performance of Hopfield Neural Network to segment pathological liver color images,” International Congress Series, Vol.1256, pp.232-239, June 2003.
[62] G. Pajares, “A Hopfield Neural Network for Image Change Detection.” Neural network, Vol.17, No.5, pp.1250-1264, Sept. 2006.
[63] K. A. Smith, “Hopfield neural networks for timetabling : formulations, methods and comparative result,” Computers and Industrial Engineering, Vol. 44, No. 2, pp. 283-305, February 2003.
[64] C. Douligeris and G. Feng, “Using Hopfield networks to solve assignment problem and N-Queen problem: An application of guided trial and Error technique.” Lecture Notes in Computer Science, Vol.2308, pp.325-336, 2002.
[65] J. Homberger and H. Gehring, “A two-phase hybrid meta-heuristic for the vehicle routing problem with time windows.” European Journal of Operational Research, Vol.162, No.1, pp.220-238, April 2005.
[66] M. V. Paul and G. A. Jespers, “An Analog VLSI Implementation of Hopfield's Neural Network.” IEEE Micro, Vol.9, No.6, pp.46-55, November 1989.
[67] H. P. Graf, L. D. Jackel and W. E. Hubbard, “VLSI Implementation of a Neural Network Model,” Computer, Vol.21, No.3, pp.41-49, March 1988.
[68] C. H. Lin and J. F. Wang, “Solving the mobile agent planning problem with a Hopfield-Tank neural network,” Proceedings of the International MultiConference of Engineers and Computer Scientists, pp. 104-114, June, 2006.
[69] C. H. Lin and J. F. Wang., “The Hopfield-Tank neural network applied to the mobile agent planning problem,” Applied Intelligence, Vol. 27, No. 2, pp.167-187, October 2006.
[70] S. Y. Foo, Y. Takefuji and H. Szu, “Job-shop scheduling based on modified Tank-Hopfield linear programming networks ,”Engineering Applications of Artificial Intelligence,Vol.7,No.3,pp.321-327,June 1994.
[71] W. W. Liang, X. X. Li and W. Q. Di, “Hopfield Neural Networks Approach for Job Shop Scheduling Problems” Intelligent Control, pp. 935-940, October 2003.
[72] X. L. Wang and T. H. Wu, “Scheduling multiprocessor job using Hopfield neural network,” Systems Engineering and Electronics, Vol. 24, No. 8, pp.13-16, 2002.
[73] K. C. Lee and Y. Takefuji, “ Finding Knight’s Tours on an M x N Chessboard with O(MN) hysteresis McCulloch-Pitts neurons.”, IEEE transactions on systems, man, and cybernetics,Vol.24,No.2,pp.300-306, February 1994.