以遗传演算法解决课程排课的问题.doc

《以遗传演算法解决课程排课的问题.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、以遺傳演算法解決課程排課的問題指導老師：謝佳琳老師專題小組組員：施竣卬、周士瑋、許勝富、曾昭國、陳嘉穎梁心怡、郭佳慧、蘇哲民、湯肇文、許輝洋摘要攸關學校、老師與學生權益的排課問題，是各級學校每學期都必須會面對的問題，所以本組想藉由研究相關的排課問題，來探討其重要性及改進的可能性。排課問題是一項複雜又困難的工作，傳統人工的排課方式，既浪費時間亦浪費成本，所得到的成果卻不一定會使人滿意，常常會引起抱怨。本小組利用國內較為人知的「遺傳演算法」，並使用電腦程式語言撰寫其模型，將排課的相關資料轉換為染色體，在追求〝可

2、行解〞的目標下，把排課的相關限制條件一一考量，求得最後想要的排課結果。我們依照排課的目的，將排課方式(傳統人工排課、電腦排課)分為實驗組與對照組，並各自加以比較。我們以真理大學工業管理學系為參考對象，以實際課表所提供的資料，配合本組的排課模型，模擬出最後的排課結果。對排課人員而言，在思考如何加強其排課方式之時，本研究應可提供另一個參考的層面。雖然本專題尚屬初期的研究，但是擁有其獨特、可行的排課方法，值得讓有興趣的人繼續加以研究探討。關鍵詞：排課問題、遺傳演算法壹、前言排課作業問題相當繁雜，一旦發生失誤，會浪

3、費許多的時間與人力。如何在排課中，儘可能滿足老師與學生對課表的需求，那就要有一套「公正」且「聰明」的排課制度，至少是透明的且結果是全校師生共同可以接受的，這是一般的排課不易做到的。所以若能建立一套自動化排課系統，進而可以創造校方、老師與學生三方面三贏的局面。「排課問題」在各級學校的教務行政上是一件很重要的課題。進行排課時需考慮的因素包括老師的專長、興趣、行政兼職、個人意願、授課基本鐘點、兼課節數上限、課程性質與授課時段配合、人性化的考量….等等。然而，學校行政上的相關排課人員，通常都是在極有限的時間內需考量

4、各方面的限制，再排出全校的課表，常弄得排課人員心力交瘁而無暇顧及老師個人意願，更遑論去評估排課結果是否符合人性化的原則，導致很多老師會有對「排課結果」不滿意，使部分老師自覺受到不公平現象發生。貳、文獻探討排課的問題是指針對於每一課程給予一個時段和教室，每位老師有數門教授課程，而每個課程根據其學分數有不同的時數，同時每位老師可以提出哪些時段為希望排課時段或不願意排課時段。簡單的說就是把各式各樣的限制式加入排課問題中。以往使用傳統人工方式來進行排課時，排課人員需不斷地對所排定的課表進行檢核及修正，以避免一切可能

5、不符現制式的情形，如此不僅浪費大量的時間、人力，且排定的課表須加以變動時，便得重新安排整張課表，使課務工作的效率大打折扣；根據上述理由，在近年來有許多自動化的方法或模型被提出來處理不同的排課問題。排課問題是在滿足所有必要限制條件下，將各種資源（時間、空間、人力、設備）分配給多個活動與課程。同時所有的限制式可以分成兩種，硬性限制式和軟性限制式兩種，所謂硬性限制式是指限制必須被滿足，軟性限制式則是最好能被滿足，一個排課問題的可行解必須要能滿足所有硬性限制式，並儘量的滿足越多的軟性限制式越好；目前各種排課問題的解

6、決方法大致分為作業研究（OperationsResearch）和人工智慧（ArtificialIntelligence）兩種領域。早期的研究大多是使用作業研究的方法來處理。D.deWerra將排課問題表示成圖形著色問題，並以由弧與節點所構成網路模型來表示，藉由找出滿足相鄰節點不同顏色的方式來求出答案。Hertz使用tabusearch(搜尋法)得方法來解決排課問題。但是作業研究的方法只適合來處理小型問題，當問題之限制式增多且使問題相對複雜時，求解過程就會變的非常困難。排課問題就是針對教學對象，安排所需上課的

7、時間與地點所面臨的問題。從管理者的觀點而言，目標是希望所有課程都能排到適當的時段和教室，並且儘可能的滿足越多的條件限制越好。從教師的觀點而言，目標是希望所排課的時間都在自己所喜好的時段中。從學生的觀點而言，目標是希望所有的課程都能排在自己所喜歡的時段，並且越少衝堂越好才能更彈性的選課。所以我們根據對教師、學生的需求了解後，收集了可能影響排課問題的限制式，如下列所示：在硬性限制式方面l已排好的課不能再排入同時段l一個班級不能在同時段上兩堂課l一位老師不能在同時段上兩堂課l一間教室不能在同時段被兩個班級所使用l

8、某時段排給某特定科目不容再變在軟性限制式方面l教師1.最低上課時數2.任教專長3.是否喜歡連堂上課4.中午(12:00)儘量不要排課5.星期六儘量不要排課Ø上午盡量不要排課Ø下午盡量不要排課Ø禮拜一一早盡量不要排課6.教師上課的合適時段7.教師喜歡的上課時段l學生1.中午(12:00)盡量不要排課2.星期六儘量不要排課3.體育課完儘量不要排課4.共同科目同班級一起上以遺傳演算法解決課程排課的問題5.選修科目各班級