跳到主要內容

臺灣博碩士論文加值系統

(216.73.217.99) 您好!臺灣時間:2026/11/04 21:49
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:康家豪
研究生(外文):Kang Chia-Hao
論文名稱:國小自動排課系統之研究─粒子群最佳化演算法的應用
論文名稱(外文):Elementary School Timetabling System Using Particle Swarm Optimization Algorithm
指導教授:李昆翰李昆翰引用關係
指導教授(外文):Li Kun-Han
學位類別:碩士
校院名稱:臺北市立大學
系所名稱:數學資訊教育學系數學資訊教育教學碩士學位班
學門:教育學門
學類:普通科目教育學類
論文種類:學術論文
論文出版年:2014
畢業學年度:102
語文別:中文
論文頁數:55
中文關鍵詞:國小、排課、系統、粒子群最佳化演算法
外文關鍵詞:Timetable、System、Particle swarm optimization、PHP
相關次數:
  • 被引用被引用:8
  • 點閱點閱:1617
  • 評分評分:
  • 下載下載:172
  • 收藏至我的研究室書目清單書目收藏:1
在國小校務行政工作中,排課問題向來是一個十分難解的問題,除了要滿足課程安排的種種限制之外,也要符合教師的各種需求。為了協助解決排課問題,各種排課系統相繼被提出,期望透過電腦的計算,來協助學校行政人員解決排課面臨的種種問題,但是排課問題屬於限制滿足問題(Constraint satisfaction problem),計算上是所謂的Nondeterministic polynomial time complete(NP-Complete)問題,無法在多項式時間內的計算中,得到最佳的排課結果,使得電腦排課系統仍然無法有效的解決排課問題。
本研究使用粒子群最佳化演算法(Particle swarm optimization),結合PHP、HTML 5和JavaScript等Web技術,建立一個排課系統,藉由粒子群最佳化演算法的計算,產生接近排課需求的最佳排課結果。研究結果顯示,粒子群最佳化演算法除了可產生正確的課表,並且可以改進排課結果,使課表盡量符合排課需求。而加入粒子毀滅機制,則是可以再進一步改善計算結果,讓排課的結果更精進,也節省了計算時間。藉由上述的研究過程,驗證粒子群最佳化演算法可以確實的改進課表,應用於排課系統上。

Scheduling the school timetable has been a difficulty of elementary administrative work. To match teacher’s expectation and timetabling restrictions, administrators of educational affair need to spend a lot of time to cope with the timetabling. Administrators are stressed since they cannot satisfy every teacher with the prerequisite. Nevertheless, the problem of timetabling is Nondeterministic polynomial time complete (NP-Complete) problem and those systems could not be verified in polynomial time. Therefore, these invented systems still have limitations. In this study, Particle swarm optimization, HTML 5, JavaScript (as Front-End) and PHP (as Back-End) are used to build a new timetabling system. The result of this study shows that the system could generate the right school timetable, and could be improved by Particle swarm optimization. And the school timetable could be conformed to the expectations and rules by modifying the algorithm. The feasibility and algorithm of the timetabling system in this study could be verified.
口試通過證明 I
謝 誌 II
中文摘要 III
英文摘要 IV
目 次 V
圖 次 VII
表 次 VIII
第一章 緒論 1
第一節 研究動機與目的 1
第二節 研究問題 3
第三節 名詞釋義 4
壹、 電腦輔助排課系統 4
貳、 排課需求 4
參、 排課限制 4
第四節 研究範圍與限制 5
第五節 研究流程 6
第二章 文獻探討 8
第一節 排課相關研究討論 8
第二節 粒子群最佳化演算法 11
壹、 最佳化演算法 11
貳、 粒子群最佳化演算法 13
第三章 研究方法 22
第一節 系統規劃與分析 22
壹、 需求與分析 22
貳、 系統設計 23
參、 單元測試 23
肆、 運作與維護 24
第二節 系統實作 25
壹、 設計架構 25
貳、 功能說明 28
第四章 系統評估與討論 35
第一節 系統功能說明 35
壹、 課表查詢 35
貳、 教師設定 38
參、 系統管理 38
第二節 計算結果分析 43
壹、 以粒子群最佳化演算法進行排課 43
貳、 加入粒子毀滅機制 46
第五章 結論與建議 49
第一節 研究結論 49
壹、 基本粒子群演算法可改進課表 49
貳、 改進粒子群演算法可提昇結果 49
第二節 研究建議 50
壹、 提昇計算效能 50
貳、 增加排課限制類型 50
參、 加入其他人工智慧演算法 51
中文參考文獻 52
英文參考文獻 53
英文網頁 55


中文參考文獻
林文揚、蘇家輝(2002)。群體決策線上排課系統之建置。資訊管理展望,第四卷,第一期,81-96頁。
邱元泰(2002)。遺傳演算法在排課問題之應用。國立中正大學數學研究所碩士論文,未出版,嘉義縣。
徐育良(2003)。以粒子群最佳化為基礎之電腦遊戲角色設計之研究。私立東海大學資訊工程與科學研究所碩士論文,未出版,台中市。
張哲維(2006)。修正禁忌搜尋法求解週期性車輛途程問題。國立東華大學企業管理學系碩士班碩士論文,未出版,花蓮縣。
張獻文(1997)。運用哈普費爾德-譚克類神經網路開發自動化排課系統。私立大業大學資訊管理研究所碩士論文。
陳介力(2008)。粒子尋優法效能改進及其在旅行商問題之應用。國立成功大學航空太空工程研究所碩士論文,未出版,台南市。
陳威甫(2011)。應用類免疫演算法於國民中學排課問題。國立臺北教育大學資訊科學系碩士班碩士論文,未出版,台北市。
陳思銘(2012)。啟發式演算法於大學排課之研究。國立國防大學運籌管理學系碩士論文,未出版,桃園縣。
黃郁授(2007)。自適應慣性權重改良粒子群演算法之研究。私立中原大學資訊管理研究所碩士論文,未出版,桃園縣。
黃家榮(2009)。應用演化式動態粒子群最佳化法於資料分群。私立天主教輔仁大學資訊工程研究所碩士論文,未出版,新北市。
蔡宇宗(2008)。運用模糊理論於排課預處理作業-以遠東科技大學資管系為例。私立樹德科技大學資訊工程系研究所碩士論文,未出版,高雄市。
盧坤勇(1994)。電腦化排課系統指派法則探討。聯合學報,第十二期,107-116頁。
賴永進(1994)。結合人工智慧技術與全體決策支援環境的大專院校自動化排課系統-排課群體協商。私立大業工學院電機工程研究所碩士論文,未出版,彰化縣。
英文參考文獻
A. Colorni, M.Dorigo, and V. Maniezzo. (1999). Genetic algorithms and highly constrained problems: The timetable case. Proceedings of the First International Workshop on Parallel Problem Solving from Nature, 55-59.
A.Hertz. (1991). Tabu search for large scale timetabling problems. European Journal of Operational Research. vol. 54, 39-47.
B. Edmund, E. David and W. Rupert. (1994). A Genetic Algorithm for University Timetabling. Department of Computer Science, University of Nottingham.
C.C. Gotlieb. (1962). The Construction of Class— Teacher Timetables. IFIP Congress, 73-77.
C.K. Kong and G.M. Maris. (1993). Intelligent Timetabling Using a Microcomputer. International Journal of Educational Management, Vol. 7, No. 5, 9 -17.
C.W. Reynolds. (1987). Flocks, Herds, and Schools: A Distributed Behavioral Model. Computer Graphics, 21(4):25-34
D. Abramson. (1991). Constructing school timetables using simulated annealing: sequential and parallel algorithms. Management Science, Vol. 37, No. 1. 98-113.
D.C. Wood. (1969). A Technique for Coloring a Graph Application to Large Scale Timetabling Problem. The Computer Journal, Vol. 12.
E. K. Burke and J. P. Newall. (1999). A multistage evolutionary algorithm for the timetable problem. IEEE Transactions on Evolutionary Computation, vol. 3, No. 1. 63-74.
H. Fan and Y. Shi. (2001). Study on Vmax of particle swarm optimization. Workshop on Particle Swarm Optimization, Purdue School of Engineering and Technology.
J. Kennedy and R. Mendes. (2003). Neighborhood Topologies in Fully-Informed and Best-of Neighborhood Particle Swarm. In Proceedings of the IEEE International Workshop on soft Computing in Industrial Applications, 45-50.
J. Kennedy and R.C. Eberhart. (1995). Particle Swarm Optimization. In Proceedings of the IEEE International Joint Conference on Neural Networks, 1942-1948.
 
J. Kennedy and R.C. Eberhart. (1997). A Discrete Binary Version of the Particle Swarm Algorithm. In Proceedings of the World Multiconference on Systemics, Cybernetics and Informatics, 4104-4109.
J.H. Holland. (1975). Adaptation in Natural and Artificial Systems. University of Michigan.
M. Eley. (2006). Ant algorithms for the exam timetabling problem. Aschaffenburg University of Applied Science Logistics Laboratory. 167-180.
R. Eberhart, Y. Shi, and J. Kennedy. (2001). Swarm Intelligence. San Mateo, CA: Morgan Kaufmann.
R.J. Aust. (1976). An improvement algorithm for school timetabling. The Computer Journal, Vol. 19, No. 4, 339-343.
Robertus J. Willemen. (2002). School timetable construction, Algorithms and complexity.
S. Kirkpatrick. (1984). Optimization by Simulated Annealing - Quantitative Studies. Journal of Statistical Physics, 34:975-986.
T. Back. (1996). Evolutionary Algorithm Theory and Practice: Evolutionary Strategies, Evolutionary Programming, Genetic Algorithm. Oxford University.
W.R. Harden and M.T. Tcheng. (1972). A Linear Programming Approach to Class Room Utilization Planning. Bulletin of the Operation Research Society of America, Vol. 20, Suppl. 2.
Y. Shi and R.C. Eberhart. (1998). A Modified Particle Swarm Optimizer. Proceedings of the IEEE Congress on Evolutionary Computation, 69-73.
Y. Zheng, L. Ma, L. Zhang, and J. Qian. (2003). Empirical study of particle swarm optimizer with an increasing inertia weigh. Proceedings of the IEEE Congress Evolutionary Computation, 221-226. 

英文網頁
bcrypt - Wikipedia, the free encyclopedia. (2014). Retrieved March 5, 2014, from http://en.wikipedia.org/wiki/Bcrypt
Boids. (1986). Retrieved April 10, 2014, from http://www.red3d.com/cwr/boids/
HHVM. (2014). Retrieved March 8, 2014, from http://hhvm.com/
Laravel instruction. (2014). Retrieved April 20, 2014, from http://laravel.com/docs/
introduction
PHP: OPcache. (2014). Retrieved March 5, 2014, from http://www.php.net/manual/
en/book.opcache.php
W3C. (2012). Retrieved March 5, 2014, from http://www.w3.org/TR/2012/CR-html5-
20121217/
W3Techs. (2013). Retrieved March 5, 2013, from http://w3techs.com/technologies/
overview/programming_language/all

連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top