首頁‎ > ‎電子期刊‎ > ‎

多角調課演算法初探

摘要

  • 文章編號:2005003
  • 投稿日期:2005/04/24
  • 作者:董世尊、尤黎明、尤弘志、黃國豪、陳冠廷、陳雅鳳、廖韋傑
  • 備註:


摘要

由於資訊與網路科技的快速發展,愈來愈多的課程逐漸改用線上與課堂並重的混合式教學方式,同時學生的學習歷程與個人基本資料也納入自動化管理的範 疇;因此,如何有效率的進行教務自動化,已成為各級學校討論的重要議題。 本研究旨在描述排課中「多角調課」的情形及問題的產生;藉由手動調課模擬的方式,來了解其排課人員調課的方法及其概念。我們描述「同班級多角調課」及「多 班級多角調課」可能產生的情況,並舉例「同班級多角調課」及「多班級多角調課」手動調課的方法。分析出兩者之間的不同,做為將來發展「多角調課」研究的參 考,改善坊間多數排課系統於「調課」這部分的缺失,提供更完善的排課系統服務。

關鍵詞:多角調課、教務自動化、線上教學管理

1.前言

由於資訊與網路科技的快速發展,資訊科技與網路基礎建設運用趨勢下,愈來愈多的課程逐漸改用線上與課堂並重的混合式教學方式,同時學生的學習歷程與 個人基本資料也可納入自動化管理的範疇,例如利用多重表徵的地球科學網路課程,探討國中學生學習歷程和學習成效[1];因此,如果有效率的進行教務自動化 和建立學校行政e化措施,已成為各級學校討論的重要議題[2]。

課程排程問題,是每間學校每學期教務行政上的例行作業;在早期,排課作業大部份都是用人工的方式進行,資訊科技發達的今日,坊間因此也逐漸 產生多種排課系統,得以提供學校教務自動化的功能,期望來協助各學校排課人員的排課作業,減少排課人員的困擾,並得以配合學生相關學習機制、線上教學管 理…等,配合課程排程上的相互應用,以提升教學品質和教師滿意度。

但排課是一種複雜的排程問題,學術界稱之「NP – Complete」,其必需滿足多個限制條件,例如:符合既有的教學資源(實驗室、電腦教室…)、場地限制(甲、乙校地的通車來回時間…)、進修教師或兼 行政教師空堂的時間要求、某些課程需全年級或全校統一固定時段實施、不跨中午排課…等[3]。因此排課人員在系統排出課表後,往往不盡人意,還必須透過人 工方式來進行調課的動作,就效率、成果而言,都無法達到理想的境界。

因此本研究就目前排課所遇到的狀況,也就是排課中「多角調課」這一環進行說明,並於將來嘗試研擬多角調演算法理想的解決方式,使排課系統中能有更廣泛的應用。


2.文獻探討

回顧過去,探討排課系統發展之文獻相當多。民國八十九年,許武義提出一個以網際網路為作業環境的主從式電腦排課管理系統架構,讓每位老師都有參與的管道及表達排課期望的機會,使作業方式能公平進行,系統能提升行政效率[4]。

民國九十年,張家和、林金玲針對教室資源的問題,提出一個移山填海的演算法,來解決大專院校各間教室的使用率,使各間教室的使用率能更平均 [5]。葉耀明、王富民則以基因演算法來解決限制條件非常複雜的排課問題,並為了提昇基因演算法的執行效率,將基因演算法運算機制結合基因代理人計算的概 念,提出兩種基因代理人運算模式:Message Queue、Collection[6]。賴聯福、潘健一、劉佳灝、李允中於排課系統的自動化上,應用人工智慧技術與資料庫的方法,利用資料庫系統維設、 管理所有排課相關資料,並描述時間排程的種種限制條件,透過CLIPS的推理機制,自動推理出符合限制結構的可行解[7]。蔡佳吟、許蒞彥以滿足限制問題 為基礎來建構一系統發展架構於排課系統上。首先採用Dynamic fail-first經驗法則來選取變數策略,再以回溯搜尋演算法和Tabu search的搜尋方法來求解[8]。

民國九十一年,邱元泰將排課中所需條件,定義分為硬式限制和軟式限制,並建立遺傳演算法模式,利用遺傳演算法的特性,搜尋出最佳解以產生出 理想課表[3]。楊錦潭、歐文性也提出以多代理人協商規劃理念來設計智慧型排課系統,使教師的期望能獲得重視,以委託系統中的智慧型代理人向校方提出合理 的期望並進行處理,透過代理人的協商機制及利用所設定之優先權重值為考量,使教師得以在不違反公平、公正的原則下進行排課[9]。林文揚、蘇家輝實際建置 一套架構在全球資訊網上的線上排課系統,以群體決策的機制來完成排課的前置作業,將系統建置於Internet架構上,利用啟發式的排課方法在交談式的環 境迅速地產生課表[10]。

民國九十三年,楊錦潭、歐文性、蕭淳豐提出處理進修學校的調代課問題,並建立多元的代課教師篩選機制與彈性調整組合的推薦機制,能有效的處理調代課事宜[11]。

民國九十四年,鄧少華、吳少琳、曾靜宜、董正談、顏志平、蘇莞筑提出一個智慧型自動排課系統,分析排課方面的各種規定及條件限制,根據「排課優先原則」來解決排課過程中遇到的衝堂問題,使整體的平均滿意度達到最大[12]。

3.多角調課定義

課程的分配往往會受到課程性質、場地限制、教師偏好、課程學分數、教學資源或科目及其他相關資訊等諸多因素的影響而牽動整個課表的結果,因此以中等 學校的排課方面做考量,排課的先前預備動作,通常會根據每位教師排配的可授課科目、應授課時數、班級週時數、課程標準、相關法規、學理與排程慣例、校內議 定規則、行政上配合與成本考量、教師的個人偏好等,先確定各班級、各科目的授課教師名單、各科目的授課節數及學分資訊,配置好所有的排課相關資料,再進行 拆課並將資料建立至系統資料庫中作為排課準備資料。 而排課系統的目的即是為了要把所有的分課資料填入適合的日期與節次。初期課表完成時期,只是完成了初步的排課工作,後續課表調整的作業通常則需花費更多的 時間與人力,此時也產生了「多角調課」的問題。 由於大部份排課系統都未完整考慮到教師授課時段的衝突、偏好等因素,因此為了盡量滿足教師們對課表的期望及提升教學品質,「多角調課」的問題逐漸受到重 視;在此我們將說明二種「多角調課」的情況。


3.1同班級多角調課

舉例某中等學校的初步課表完成時,同一班級中,A教師想將(一,1)節次換至B教師的(二,3)節次時,(二,3)節次就必需協調空出節 次,但前提必需考慮B教師在(一,1)節次是否有其他課程,此時就產生最單純的一角調課動作。如果我們再嘗試把B教師在(一,1)節次調至C教師的 (四,3)節次,以便空出節次給A教師,就必需再考慮C教師是否在(一,1)節次另外有課程等,依此類推形成同班級多角調課問題,以圖1、圖2表示。


  • 圖1.一角調課



  • 圖2.同班級多角調課


3.2多班級多角調課

另外一種情況則是假設在不同班級中,班級一中,A 教師的(一,1)節次與B教師的(二,3)節次互調時,則必需考慮B教師在班級二中的(一,1)節次是否有課程;如果嘗試讓B教師在班級二中(一,1)節 次的課程與C教師(四,3)節次互調,以避免B教師在同一時間有班級一與班級二之間課程衝突,則又必需考慮C教師在其他班級是否有課程,以此類推形成第二 種多角調課問題,如圖3、圖4表示。


  • 圖3.班級一課表



  • 圖4.班級二課表

4.多角調課問題

目前許多排課系統中的多角調課問題,大部份還是以人工手動的方式去處理,因此本文利用「財團法人私立忠信工商學校」的排課資料及Sunset排課系統工具,來舉例手動調課時可能發生的情況、問題和處理方式,以了解其手動調課的概念。


4.1同班級多角調課

手動調課概念,往往會根據不同排課人員的想法,產生不同的結果。因此,假設進行手動調課時,初步會查詢同班級是否有節次可以相互調動,然後 進行調課作業;範例中,「資二仁」班進行週一的3、4節「國文」調動時,首先按照A教師的條件設定下,不希望排課於1、2節,所以週一至週五的1、2節課 程,全部不考慮調動,其次開始尋找與週一的國文Ⅲ一樣二節之課程,以便較好調動(表1、圖5)。

教師

任教資二仁班之科目

限制條件

A教師

國文

節次>2,可跨中午

B教師

法律生活、試算表、計算機原理

不可重複排課

C教師

經濟學

可跨中午

D教師

應用數學

不可跨中午,不可重複排課

E教師

電腦軟體應檢定

不可跨中午,不可重複排課

F教師

英文

不可跨中午,不可重複排課

G教師

數學

可重複排課

  • 表1.各教師之限制條件

  • 圖5.資二仁班進行調課


依照上述作業注意事項,查詢到的是週一A教師的「法律與生活」,如果做互調,學生將從第一節到第四節都是同一個老師的課,可能會感到無趣,老師也會覺得 累,所以不考慮「法律與生活」這個課程。週四的3、4節「計算原理Ⅰ」,同理暫時不考慮做調課動作。做相關資料查詢後,發現A教師的「國文」可與週二6、 7節的「電腦軟體應用檢定Ⅰ」做調課動作,因此A教師的「國文」課調動完成(圖5、圖6)。


  • 圖6.查看A教師課表


由於星期一的1至4節忠微電教室有班級「訊二義」班在使用,在查詢E教師的分課表後,將「電腦軟體應用檢定Ⅰ」暫時排定在週二第3、4節(圖7、圖8), 並查詢C教師、D教師的分課表是否可以調動課程;因此原本的C教師週二4、5節的「經濟學」調至週一的第3、4節,原本的D教師週二第3節「應用數學」, 調至星期二的第5節(圖9、圖10);此時完成了資二仁班的調課作業(圖11)。


圖7.查看E教師課表


  • 圖8.查看忠微教師使用課表


  • 圖9.查看C教師課表



  • 圖10.查看D教師分課表課



  • 圖11.資二仁班調課後新課表
2多班級多角調課

在同一個班級之中,如果各科教師,節次無法互相調動時,就可能產生多班級多角調課的作業方式;以範例中的情況下,「資二仁」班週一的3、4 節「國文」假如無法與同班級的其他科目或節次互調時,所模擬採用的方法是一步驟、一步驟的方式進行搜尋,因為欲調動之「國文」共兩節,所以搜尋以兩節或兩 節以上的課程為主,並參考A教師與可能會調動之B教師與C教師資料所設定的限制條件(該課不希望排至早上1、2節…等),以此規則進行調課(表1)。

在進行查詢動作時,首先碰到為兩節課程的是B教師週一6、7節的「法律與生活」,因此我們查看B教師的分課表資料,發現該教師在週一的3、 4節還有其他班的課程,調動上可能較麻煩,因此暫時不考慮,繼續進行查詢,此時碰到週二的1、2節次課程,雖為兩節課之課程,但因為A教師資料上的限制條 件不希望排課於1、2節,因此也不考慮該節次之調動;直接跳過1、2節後(圖12、圖13),查詢到的是C教師週二4、5節的「經濟學」,查看該教師的分 課表後,發現可與欲調動之「國文」的A教師做互調(圖13),但因A教師在週二的3、4節已有「訊二義」班的課,因此我們進入A教師在週二的3、4節課程 暫時抽出擱置,並把C教師週二4、5節的課程調至A教師的週一3、4節的課程調至週二原本為「經濟學」的4、5節(圖14、圖15)。

上述作業結束後,「資二仁」班的課表則暫時為完成狀態;其次我們要來看的是被牽扯到的「訊二義」班課表,由於「訊二義」班週二3、4節的 「國文」在「資二仁」班調課時,被暫時抽出擱置,因此我們進行將此課程排至適當的節次中;在「訊二義」班的課表中顯示出週一的課程是無法更動的,其原因可 能牽扯到場地問題,因此直接照上述的作業方式進行調課,查詢週二是否有適當節次,其中發現第2節G教師的「數學」可調至第4節,此時週二之2、3節為無課 狀態,由於「國文」之A教師資料所設定的條件下,因此不參考2、3節的空堂,尋找至週二6、7節的F教師「英文」,並查詢E教師的分課表,藉由大致相同之 作業模式,將E教師週二6、7節的「英文」調動至當天2、3節的空堂,則之前被擱置的「國文」可順利的放置於週二6、7節。由於在「英文」調動時,有牽扯 到「訊二忠」班週二的3、4、5節課程(圖15、圖16),因此也利用同樣的作業方式進行調課,經過上述步驟、方法,手動調課則陸續的完成各班的課表(圖 17、圖18、圖19)。


  • 圖12.資二仁班進行調課


  • 圖13.查看B教師分課表



  • 圖14.查看C教師分課表



  • 圖15.查看A教師分課表



  • 圖16.資二義班進行調課



  • 圖17.資二仁班調課後新課表



  • 圖18.訊二義班調課後新課表



  • 圖19.訊二忠班調課後新課表

5.結論

手動調課作業模擬完成後,發現到不管是同班級多角調課;或是多班級多角調課,除了要從班級課表著手以外,還必需查詢教師的限制條件、教師的分課表、 場地限制等因素,進行考量而調課,所查詢之資料的確非常龐大與複雜,並且可能牽扯出許多不公平因素,由於手動調課也因為不同排課人員的因素而產生、完成多 種可能的調課後課表,其操作、調動方式,往往有著不確定;或不知為何的想法在其中,較不易完整的解決調課問題。

而同班級多角調課中,牽扯相關資料的範圍較小,僅侷限於同班級之授課教師相關資料的查詢、特殊教室使用查詢;而多班級多角調課,則會牽扯到 更大範圍的調課動作,產生一連串班級課堂調動,這樣的情況可能會引起別班教師的不滿,影響教師教學品質,而且也可能調課的作業會產生永無止盡的調動動作, 找不出一個適當的結果;因此,期望接下來能找出合適的演算法,可以彌補人工調課所引發的缺陷,且有範圍、有一定規則的幫助排課人員搜尋調課可能結果,而非 漫無目的的尋找、查詢,有效的調動出較理想的課表。


6.參考文獻

[1]蔡松輝。“線上地球科學網路教學課程對學生學習的影響”。國立台灣師範大學地球科學研究所碩士論文。2004。 [2]李呈奇。“大學推動校園e化之探討”。國立中山大學人力資源管理研究所碩士論文。2002。 [3]邱元泰。“遺傳演算法在排課問題之應用”。國立中正大學數學研究所碩士論文。 2002。 [4]許武義。“網頁式排課管理系統”。國立暨南國際大學資訊管理研究所碩士論文。2000。 [5]張家和,林金玲。“大專院校解決最小教室數目的一個智慧型排課系統”。第六屆人工智慧與應用研討會。2001。 [6]葉耀明,王富民。“基因演算法於排課問題上之研究”。九十年全國計算機會議。 2001。 [7]賴聯福,潘健一,劉佳灝,李允中。“應用人工智慧與資料庫方法於排課系統之自動化”。電腦學刊:頁1-8。2001。 [8]蔡佳吟,許蒞彥。“大學排課系統的硬性與軟性限制條件之探討”。第八屆國際資訊管理研究暨實務研討會。2001。 [9]楊錦潭,歐文性。“以代理人為基礎的中學排課系統研究”。第六屆全球華人計算機教育應用大會。北京師範大學。北京市。2002。 [10]林文揚,蘇家輝 。“群體決策線上排課系統之建置”。資訊管理展望第4卷第1期。2002。 [11]楊錦潭,歐文性、蕭淳豊。“運用教師代理人在高中進修學校調代課人選推薦系統之研究”。第九屆人工智慧與應用研討會。2004。 [12]鄧少華,吳少琳,曾靜宜,董正談,顏志平,蘇莞筑。“智慧型排課系統”。 ECDL2005電子商務與數位生活研討會。2005。

Comments