模組化建構多班別之學校排課問題

Applying modularity to construct the multi-class school timetabling problem

10.6840/cycu201600306

彭迺淳

排課系統 ； 整數規劃法 ； 模組化 ； 多班別之學校排課問題 ； Timetabling system ； Integer programming ； Modularity ； Multi-class school timetabling problem

中原大學工業與系統工程學系學位論文

2016年

碩士

陳平舜

繁體中文

本研究針對全國國民中學與國民小學之排課問題進行探討，經由訪談了解其學校排課規則與邏輯，發現目前各所學校所包含的班級類別組合皆不相同，因此本研究提出以模組化的概念進行多班級類別之分類，考慮班級類別排課組合之多變性，以滿足各所學校之排課需求。本研究研究方法是利用模組化將各班級類別限制式分類，蒐集相關排課資訊，並利用整數規劃法建立其數學模式，再藉由IBM ILOG CPLEX軟體進行求解可行解課表。最後，以個案學校為案例，做分析、驗證及討論，以驗證其模組化建構多班別概念的可行性及有效性。

This research studied a school timetabling problem on both the elementary schools and junior high schools. After interviewing with school staff, the researcher found that different schools had different combinations of classes. Therefore, this research applied the modularity concept to classify multiple classes into each corresponding category. Based on the combination of the multi-class school timetabling, this study collected the related class information and school timetabling rules, constructed a mathematical model by using integer programming, and used IBM ILOG CPLEX software to solve the proposed school timetabling problem. Finally, through a case school study, this research examined the proposed method, and analyzed and discussed the results of the school timetabling in order to justify the feasibility and effectiveness of the concept of applying modularity to construct multi-class school timetabling problems.

1. Al-Yakoob, S. M., & Sherali, H. D. (2015). Mathematical models and algorithms for a high school timetabling problem. Computers & Operations Research, 61, 56-68.
   連結：
2. Birbas, T., Daskalaki, S., & Housos, E. (2009). School timetabling for quality student and teacher schedules. Journal of Scheduling, 12(2), 177-197.
   連結：
3. Brailsford, S. C., Potts, C. N., & Smith, B. M. (1999). Constraint satisfaction problems: Algorithms and applications. European Journal of Operational Research, 119(3), 557-581.
   連結：
4. Caprette, D. R., Armstrong, S., & Beason, K. B. (2005). Modular laboratory courses - An alternative to a traditional laboratory program. Biochemistry and Molecular Biology Education, 33(5), 351-355.
   連結：
5. Domenech, B., & Lusa, A. (2016). A MILP model for the teacher assignment problem considering teachers' preferences. European Journal of Operational Research, 249(3), 1153-1160.
   連結：
6. Kamrani, A. K., & Salhieh, S. e. M. (2002). Product Design for Modularity. MA, USA: Kluwer Academic Publishers.
   連結：
7. Lawrie, N. L. (1969). An integer linear programming model of a school timetabling problem. Computer Journal, 12(4), 307-316.
   連結：
8. Muggy, L., & Easton, T. (2015). Generating class schedules within a complex modular environment with application to secondary schools. Journal of Scheduling, 18(4), 369-376.
   連結：
9. Pillay, N. (2014). A survey of school timetabling research. Annals of Operations Research, 218(1), 261-293.
   連結：
10. Sorensen, M., & Dahms, F. H. W. (2014). A two-stage decomposition of high school timetabling applied to cases in Denmark. Computers & Operations Research, 43, 36-49.
    連結：
11. Tassopoulos, I. X., & Beligiannis, G. N. (2012). A hybrid particle swarm optimization based algorithm for high school timetabling problems. Applied Soft Computing, 12(11), 3472-3489.
    連結：
12. 王江山，以多標規劃求解大學教師排課最佳化之研究，國立成功大學工業管理科學系專班，2004。
    連結：
13. 任書鳴，應用資料探勘技術於排課系統之研究，靜宜大學資訊管理學系研究所，2007。
    連結：
14. 梁定澎，資訊管理理論，新北市：前程文化事業股份有限公司，2012。
    連結：
15. 陳珈惠，開放式課程之再利用及模組化－以微積分課程為例，國立交通大學應用數學系所，2013。
    連結：
16. Baldwin, C. Y., & Clark, K. B. (2003). Managing in an Age of Modularity: Architectures, Networks, and Organizations. MA, USA: Blackwell Publishing.
17. Even, S., Itai, A., & Shamir, A. (1975). On the complexity of time table and multi-commodity flow problems. Paper presented at the Foundations of Computer Science, 1975., 16th Annual Symposium on IEEE.
18. Pahl, G., & Beitz, W. (1996). Engineering Design: A Systematic Approach. NY, USA: Springer.
19. Schaerf, A. (1999). A survey of automated timetabling. Artificial Intelligence Review, 13(2), 87-127.
20. Ulrich, K. T., & Tung, K. (1991). Fundamentals of product modularity. Paper presented at the 1991 ASME Winter Annual Meeting Symposium.
21. 全國法規資料庫: 國民小學及國民中學常態編班及分組學習準則. 2009. Source: http://law.moj.gov.tw/LawClass/LawAll.aspx?PCode=H0070026
22. 全國法規資料庫: 高級中等以下學校藝術才能班設立標準. 2010. Source: http://law.moj.gov.tw/LawClass/LawAll.aspx?PCode=H0060026
23. 全國法規資料庫: 特殊教育法. 2014. Source: http://law.moj.gov.tw/LawClass/LawAll.aspx?PCode=H0080027
24. 全國法規資料庫: 藝術教育法. 2015. Source: http://law.moj.gov.tw/LawClass/LawAll.aspx?PCode=H0170037
25. 全國法規資料庫: 國民教育法. 2016a. Source: http://law.moj.gov.tw/LawClass/LawContent.aspx?PCODE=H0070001
26. 全國法規資料庫: 國民體育法. 2016b. Source: http://law.moj.gov.tw/LawClass/LawAll.aspx?PCode=H0120001
27. 李艾玲，模組化設計應用於音樂性電台數位音樂資料庫之分析，世新大學傳播管理學研究所(含碩專班)，2005。
28. 林達偉，人力指派最佳化模式之研究-以軍事院校排課系統為例，崑山科技大學資訊管理研究所，2015。
29. 翁得榮，排課問題之研究－以高雄第一科技大學運籌管理系為例，國立高雄第一科技大學運籌管理所，2007。
30. 國家教育研究院: 十二年國民基本教育課程綱要. 2014. Source: http://www.naer.edu.tw/files/15-1000-7944,c639-1.php?Lang=zh-tw
31. 康家豪，國小自動排課系統之研究─粒子群最佳化演算法的應用，臺北市立大學數學資訊教育學系數學資訊教育教學碩士學位班，2014。
32. 陳奕憲，基因演算法在國民中學排課問題之最佳化研究，南華大學資訊管理學系碩士班，2011。
33. 陳思銘，啟發式演算法於大學排課之研究，國防大學管理學院運籌管理學系，2012。
34. 新竹縣政府教育處: 新竹縣國民小學教師每週授課節數實施要點. 2012a. Source: http://hclaw.hsinchu.gov.tw/law/LawContent.aspx?id=GL000174
35. 新竹縣政府教育處: 新竹縣國民中學教師每週授課節數實施要點. 2012b. Source: http://hclaw.hsinchu.gov.tw/law/LawContent.aspx?id=FL027004
36. 楊迺聲，軍事院校班隊排課最佳化之研究，國立中央大學土木工程學系碩士在職專班，2005。
37. 廖聖揚，應用限制規劃方法求解軍事院校排課問題，國立高雄第一科技大學資訊管理所，2005。
38. 歐芝岑，模組產品創新策略類型之研究─台灣機械業的實證研究，東海大學工業工程學系，2001。

1. 曾智揚(2017)。建構啟發式演算法求解有軟硬限制之最佳化問題：以醫護人員排班問題為例。中原大學工業與系統工程學系學位論文。2017。1-41。