臺灣博碩士論文加值系統

課表的時間安排一直是各個學校每學期都會遇到的問題，除了排課的時段受到教室等資源的限制，本研究要面對的問題乃是如何找出一張讓教師與學生都滿意，並且沒有違反教室重複使用的限制條件的課表。
本論文將課表模擬為粒子群之粒子以搜尋最佳滿意度之課表，為避免族群搜尋過程中落入局部最佳解及改善PSO於搜尋末期粒子相似度過高的缺陷，乃利用具隨機粒子與微調機制之粒子群演算法，以提高演算法於最佳區域局部搜尋的能力，並動態加入可隨使用者訂定之限制條件，以搜尋最佳滿意度的課表。本文提出之方法，經模擬結果確可在廣大的解空間中，利用有限的搜尋粒子即可得到極高滿意度的課表。

Scheduling and course planning in any kind of school and university require tremendous efforts to fulfill many constraints without conflicts. In course timetabling, the scheduler determines the day and time to offer each section of each course. The objective is normally to find a course timetable that minimizes the number of (potential) student conflicts while respecting teacher, room and equipment restrictions.
The problem of developing schedules for course timetabling has been modeled as a particle swarm group optimization problem. To avoid cluster searching procedure falls into a local optimum and improves optimum local area search ability, Particle Swarm Optimization with Random Particles and Fine-Tuning Mechanism, PSO-RPFT, was proposed in the thesis with dynamic user constraining rules. The simulation of PSO-RPFT has shown high level satisfactory results in a large range of solutions with finite search particles.

目錄
中文摘要 i
Abstract ii
符號對照表 iii
目錄 v
表目錄 vii
圖目錄 viii
第一章 緒論 1
1.1前言 1
1.2 文獻回顧 2
1.3 研究動機與目標 5
1.4 論文架構 6
第二章 粒子群最佳化演算法 7
2.1最佳化問題形式 7
2.2粒子群最佳化 10
2.2.1粒子群最佳化發展背景 10
2.2.2基礎理論 11
2.2.3 PSO執行程序 12
2.2.4 PSO運算流程與演算法流程圖 14
2.3慣性權重式粒子群最佳化(Particles Swarm Optimization with Inertia Weighted，PSO-IW) 16
2.4限制因子式粒子群最佳化(Particles Swarm Optimization with Constriction Factor，PSO-CF) 17
第三章 具隨機粒子與微調機制式粒子群最佳化演算法 19
3.1隨機粒子 19
3.1.1基本概念 19
3.1.2隨機粒子速度更新法則 22
3.2微調機制 22
3.2.1基本概念 23
3.2.2微調機制執行法則 24
3.2.3微調運算方式 27
3.3具隨機粒子與微調機制式粒子群最佳化演算法執行程序 29
第四章 模型建立及適應函數 34
4.1 模型建立 34
4.2適應函數 37
第五章 模擬結果與討論 40
5.1課表最佳化之模擬程序 40
5.2 模擬結果 42
5.2.1 進行「自動調整時段」之模擬結果 42
5.2.2 賦與「整體懲罰」之模擬結果 45
5.2.3 賦與「個別懲罰」之模擬結果 47
5.3 增加限制條件 49
5.3.1 增加「教室群」為限制條件 49
5.3.2增加「同年級必修不衝堂」之限制條件 55
5.3.3 增加「同年級必修不擋選修」之限制條件 57
第六章 結論與未來之展望 61
6.1 結論 61
6.2 未來展望 64
參考文獻 65

參考文獻

[1] J. Kennedy and R. C. Eberhart, "Particle swarm optimization, " in Proc. IEEE Int. Conf. Neural Network., Perth, Australia, vol. 4, pp. 1942–1948., 1995.
[2] R. C. Eberhart and J. Kennedy, "A new optimizer using particle swarm theory, " in Proc. 6th Int. Symp. Micromachine Human Sci., Nagoya, Japan, pp. 39–43., 1995.
[3] J. Kennedy, R. C. Eberhart, and Y. H. Shi, "Swarm intelligence. san mateo," CA: Morgan Kaufmann, 2001.
[4] R. C. Eberhart and Y. H. Shi, "Particle swarm optimization: Developments, applications and resources, " in Proc. IEEE Congr. Evol. Comput., Seoul, Korea,pp. 81–86.,2001.
[5] X. D. Li and A. P. Engelbrecht, "Particle swarm optimization: An introduction and its recent developments, " in Proc. Genetic Evol. Comput. Conf.,pp. 3391–3414., 2007.
[6] R. A. Krohling and L. dos Santos Coelho, "Coevolutionary particle swarm optimization using Gaussian distribution for solving constrained optimization problems, " IEEE Trans. Syst., Man, Cybern. B, Cybern., vol. 36, no. 6, pp. 1407–1416,Dec. 2006., Dec. 2006.
[7] N. Franken and A. P. Engelbrecht, "Particle swarm optimization approaches to coevolve strategies for the iterated prisoner’s dilemma, " IEEE Trans. Evol. Comput., vol. 9, no. 6, pp. 562–579, Dec. 2005.
[8] S.-Y. Ho, H.-S. Lin, W.-H. Liauh, and S.-J. Ho, "OPSO: orthogonal particle swarm optimization and its application to task assignment problems, " IEEE Trans. Syst., Man, Cybern. A, Syst., Humans, vol. 38, no. 2, pp. 288–298, Mar. 2008.
[9] B. Liu, L. Wang, and Y. H. Jin, "An effective PSO-based memetic algorithm for flow shop scheduling, " IEEE Trans. Syst., Man, Cybern. B, Cybern., vol. 37, no. 1, pp. 18–27, Feb. 2007.
[10] R. C. Eberhart and Y. Shi, "Guest editorial, " IEEE Trans. Evol. Comput.—Special Issue Particle Swarm Optimization, vol. 8, no. 3, pp. 201–203, Jun. 2004.
[11] 邱元泰，「遺傳演算法在排課問題之應用」，國立中正大學數學研究所，碩士論文，民國91 年。
[12] 熊雅意，楊馥豪，李育儒，陳星儒，張自豪，「應用基因演算法於大專學校教師派課問題」，2006 數位科技與創新管理國際研討會，臺北，華筑大學，民國95 年4 月。
[13] 謝正瑜，楊俊傑，「利用遺傳基因演算法提高教學排課滿意度之研究」，電腦與網路科技在教育上的應用研討會，新竹，民國91 年11 月。
[14] Blum, C., Correia, S., Dorigo, M., Paechter, B., Rossi-Doria, O., and Snoek. M., "A GA evolving instructions for a timetable builder", Proceedings of the 4thInternational Conference on Practice and Theory of Automated Timetabling, 2002.
[15] Edmund, B., David, E., and Rupert, W., "A Genetic Algorithm for University Timetabling", Department of Computer Science University of Nottingham, 1994.
[16] 鄭惟中，「電腦化自動排課系統之研究」，逢甲大學工業工程學系，碩士論文，民國92 年。
[17] 許武義，「網頁式排課管理系統」，暨南大學資訊管理所，碩士論文，民國89年。
[18] 林文揚，蘇家輝，「群體決策線上排課系統之建置」，資訊管理展望，第四卷，第一期，81-96 頁，民國91 年3 月。
[19] 吳正宇，「點著色在課程排程問題之研究─以淡江大學研究所為例」，淡江大學運輸管理學系，碩士論文，民國92 年。
[20] 李麗華，邱永祥，「智慧型線上教學課程推薦機制」，第七屆人工智慧與應用研討會，朝陽科大，C3-4，612-618 頁，民國91 年11 月。
[21] 蕭榮亭，「應用多代理人系統於大學排課問題之研究」，中原大學資訊管理學系，碩士論文，民國94 年。
[22] 任書鳴，「應用資料探勘技術於排課系統之研究」，靜宜大學資訊管理系，碩士論文，民國96 年。
[23] 包冬意，賴永進與吳智暉，「大專院校排課自動化之研究，智慧型大專院校自動化排課系統」，電腦應用研討會，蕙蓀林場，100-104 頁，民國83 年。
[24] 沈正慈，「電腦排課」，元智大學電機與資訊工程研究所，碩士論文，民國87 年。
[25] 張獻文，「運用哈普費爾德－譚克類神經網路開發自動化排課系統」，大葉大學資訊管理學系，碩士論文，民國86 年。
[26] 楊錦潭，歐文性，「以代理人為基礎的中學排課系統」，全球華人計算機應用大會，北京市，北京師範大學，345-351 頁，民國93 年。
[27] 潘麗珍，「行動多重代理人技術於排課系統之應用」，國立中央大學資訊管理所，碩士論文，民國92 年。
[28] 蔡旻璇，「序列樣式分析應用於課程規劃支援系統」，靜宜大學資訊管理系，碩士論文，民國93 年。
[29] Burke, E. K., and Newall, J. P., "A multistage evolutionary algorithm for thetimetable problem", IEEE Transactions on Evolutionary Computation, Vol. 3, No. 1, pp.63-74, 1999.
[30] Eley, M., "Ant algorithms for the exam timetabling problem", Aschaffenburg University of Applied Science Logistics Laboratory (LIAb), Germany, pp.167-180, 2006.
[31] Ferland, J. A., and Fleurent C., "A decision support system for course scheduling", Interfaces, Vol. 24, No. 2, pp.105-115, 1997.
[32] Haase, K., Latteier, J., and Schirmer, A., "The course scheduling problem at Lufthansa Technical Training", European Journal of Operational Research 110, pp.441-456, 1998.
[33] Hertz, A., and Robert, V., "Constructing a course schedule by solving a series of assignment type problems", European Journal of Operational Research , p108, 1998.
[34] Marte, M., "Models and Algorithms for School Timetabling - A Constraint Pro-gramming Approach", Doctoral Dissertation at the Faculty of Mathematics, Computer Sci-ence and Statistics of the Ludwig-Maximilian-University of Munich, 2002.
[35] Schaerf, A., "Tabu Search Techniques for Large High-School Timetabling Problems", Report of National Research Institute for Mathematics and Computer Science, 1996.
[36] Socha, K., Sampels, M., and Manfrin, M., "Ant Algorithms for the University Course Timetabling Problem with Regard to the State-of-the-Art", Applications of Evolutionary Computing-Lecture Notes in Computer Science, Vol. 2740. Springer-Verlag, Berlin, pp.334-345, 2003.
[37] 宋子康，「資料串流中尋找關聯法則之研究」，台灣大學資訊管理學系，碩士論文，民國95 年。
[38] Venkataraman P., Applied optimization with MATLAB Programming. U.S.A.: A Wiley-Interscience publication.,2001.
[39] Kennedy, J., Eberhart, R.C. and Shi, Y., Swarm intelligence San Francisco: Morgan Kaufmann Publishers.,2001.
[40] Eberhart, R.C. and Kennedy, J., A new optimizer using particle swarm theory. Proceedings of the 6th International Symposium on Micro Machine and Human Science, 39-43, Nagoya, Japan, IEEE, Piscataway, NJ, USA., 1995.
[41] Shi, Y. and Eberhart, R.,A modified particle swarm optimizer. Proceedings of the IEEE International Conference on Evolutionary Computation, 69-73, Anchorage, AK, USA, IEEE, Piscataway, NJ, USA., 1998.
[42] Shi, Y. and Eberhart, R., Empirical study of particle swarm optimization. Proceedings of the 1999 Congress on Evolutionary Computation, Vol. 3, 1945-1950, Washington, DC, IEEE, Piscataway, NJ, USA.,1999.
[43] Clerc, M., and Kennedy, J., The particle swarm: Explosion, stability, and convergence in a multimodal complex space. Proceedings of the Congress of Evolutionary Computation, Vol. 6, 58-73, Washington DC, IEEE, Piscataway, NJ, USA.,2000.