混合圖形著色與限制條件為基礎之排課系統-以台灣職業訓練中心為例

School Timetabling using Graph Coloring and Constraint Based Approaches — for Taiwan’s Job Training School

袁仲明(Chung-Ming Yuan)

指導教授 ： 劉俞志

元智大學/資訊學院/資訊管理學系/碩士(2003年)

摘要

[摘要]
台灣專業的職業訓練中心，為配合企業界各行業人力的訓練需求，而開設不同訓練職類及班級課程。由於擬定訓練計劃時，課表內所安排的訓練時數、課程內涵等要求程度無法歸類統一，以及共同課程的安排、外聘教師指定的授課時間不固定，所以，以往高中的排課系統並不適用。學校的排課系統，係以安排一學期二十週固定不變動的週課表為主，而台灣職業訓練中心其排課方式有別於一般高中（職）以上學校，須依循各班級不同的訓練課程內容與時數，來安排每週複雜且動態的課表，本研究計劃運用視窗作業平台、下拉導引清單式的操作環境，混合圖形著色與限制條件為理論的基礎，考慮列出避免課程衝堂所有的可能限制條件，降低人為錯誤的狀況與正確性，減少人工時間提昇效率為訴求目的，設計一套適合台灣職業訓練中心使用的班級自動排課雛形系統，解決職業訓練中心的排課問題。

關鍵字

排課系統 ； 圖形著色

並列摘要

[Abstract]
In order to satisfy the training need of human resource in every kinds of business, the professional vocational training centers in Taiwan offer many different kinds of careers and class courses. When setting the training plan, the requests for hours and contents of course have not to be coordinated, and setting the common courses and course hours that lecturer assign are not fixed so that it is not suitable to use the past arranging course system of high schools or colleges.
In general, timetabling in high schools is to assign fixed courses in twenty weeks a semester. However, the ways of vocational training centers in Taiwan to arrange courses are different from the ways in high schools or education above. Vocational training centers in Taiwan must systematize complicated training courses and dynamic school timetables for each week, depending on the diversified course contents and hours for each class. This research depends on the base theory of window platform, pull down menu, mixed the graphic coloring and restrict constrains, then lists all possible restrict constrains of avoiding conflict of courses, man-made errors and incorrectness. Our goals is to design a proper automatic prototype of arranging course system which can reduce the working-hours and sure be more efficiency to solve the problems in the vocational training centers in Taiwan.

並列關鍵字

Timetabling System ； Graph Coloring

參考文獻

【14】沈正慈， "電腦排課" 元智大學，電機與資訊工程研究所，碩士論文(1998 年).

【1】J.P.Caldeira and A.C.Rosa, "School Timetabling using Genetic Search". PATAT 97(1997)115-122.

【4】Carlos Caldeira Fernandes, Joao Paulo Melicio and A.C.Rosa "High School Weekly Timetabling by Evolutionary Algorithms". To appear in SAC 99 San Antonio(1999) 344-350.

【5】D.E.Goldberg, "Genetic Algorithms in search, optimization and machine Learning", Addison-Wesley.

【6】J.Allen Lima, N.Gracias, H.Pereira, and A.C.Rosa, "Fitness Function Design for Genetic Algorithms in Cost Evaluation Based Problems", Proc. IEEE - Int. Conf. Evolutionary Computation, ICEC’96(1996)207-212.