排課系統(tǒng)的開發(fā)和實(shí)現(xiàn).doc

上海交通大學(xué)學(xué)士論文 網(wǎng)絡(luò)學(xué)院排課系統(tǒng)的實(shí)現(xiàn)10:41排課系統(tǒng)的開發(fā)和實(shí)現(xiàn)摘要要完成一所大學(xué)或者一個(gè)學(xué)院的課程安排是一件非常復(fù)雜的問題，如果用人手工進(jìn)行安排的話，需要極大的精力和時(shí)間。而在排課的時(shí)候，需要考慮的范圍，涉及到教師、課程、教室還有班級情況等等。而在現(xiàn)今的大學(xué)排課過程中，整個(gè)學(xué)校需要考慮的教師，課程信息是成百上千，排課問題由此變?yōu)橐粋€(gè)異常復(fù)雜的組合問題。所以在現(xiàn)實(shí)世界的應(yīng)用中，排課問題的所有排列組合對于人類來說幾乎可以被認(rèn)為是一個(gè)天文數(shù)字。而一個(gè)可以被接受的排課方案是一個(gè)滿足排課所有制約性要求的方案。在此基礎(chǔ)上，如果有人希望能通過一些啟發(fā)性的設(shè)定而得到一個(gè)更為優(yōu)化（更為合理，美觀，更為符合人的習(xí)慣）的排課方案的話，則這個(gè)問題就會變得超乎尋常的困難。所以迄今為止，為了能夠用計(jì)算機(jī)自動完成排課任務(wù)已經(jīng)進(jìn)行了非常多的嘗試。排課的本質(zhì)問題是將大量的課程安排進(jìn)有限的上課時(shí)間和教室中，與此同時(shí)還會涉及到任課老師和學(xué)生班級等各種因素互相制約的影響。通常來說，排課中涉及的變量越多，則排課問題就會越復(fù)雜。而本課題的排課研究涉及的排課環(huán)境是上海交通大學(xué)的網(wǎng)絡(luò)學(xué)院。網(wǎng)絡(luò)學(xué)院的排課是排課問題中的一個(gè)全新的領(lǐng)域。因?yàn)?，在網(wǎng)絡(luò)學(xué)院中，教室有了多媒體，視聽等各種新的屬性，而這在傳統(tǒng)的排課問題中是沒有的。而且，網(wǎng)絡(luò)學(xué)院的上課時(shí)間也更具多樣性。不同的專業(yè)，有的每天上午最多只能排4節(jié)課，而有的專業(yè)卻可以安排5節(jié)課。時(shí)間標(biāo)準(zhǔn)的多樣性，教室屬性的多樣性，使得網(wǎng)絡(luò)學(xué)院的排課問題需要考慮更多的因素，從而給排課提出了更高的要求。本文所做的研究工作先是比較了一下當(dāng)今比較流行的集中排課算法，如線性算法、遺傳算法、限制邏輯(CLP)編程等等算法各自的優(yōu)缺點(diǎn)和適用性。并且，在此基礎(chǔ)上，本文針對網(wǎng)絡(luò)學(xué)院排課更為特殊的要求，提出了一個(gè)新的算法。最終，基于本文所提出的這個(gè)算法，開發(fā)出了一個(gè)全新的排課模型，使其不但能適應(yīng)普通的排課環(huán)境，還能夠很好地滿足網(wǎng)絡(luò)學(xué)院更為特殊的排課要求。關(guān)鍵詞： 遠(yuǎn)程教育， 排課， 人工智能， 遺傳算法，限制邏輯編程 THE CONSTRUCTION OF TIMETABLES FOR SCHOOL COURSESAbstractThe construction of timetables for universities or schools is an extremely complex problem, whose manual solution requires much effort. The set of all possible solutions, that is the space of the problem, is very large, at least in the real world examples. An acceptable solution is one who satisfies all the problem constraints. The problem goes even more difficult if someone wants to generate an optimum timetable according to some heuristic criteria. Various attempts have been made so far on the automatic solving of the timetabling problem by a computer. The course-timetabling problem essentially involves the assignment of weekly lectures to time periods and lecture rooms. And generally speaking, the more variable the timetabling has, the more complex it is. Because there are quite a lot of versions of the timetabling problem, differing from one school to the next, we focus on constructing course timetables at our own long-learning school.The timetabling for our network school is a brand new in the TTP area. In this problem, the classrooms have attributes such as Multimedia, Video that we never encountered before. Some obstacles like that make the timetabling for the network school a more complex problem and bring a lot of new challenges.In this paper, some popular TTP algorithms such as Linear, genetic algorithms have been introduced. And according to the especially high demand of the network school, the paper brings a new algorithm and accomplished a new timetabling system. It not only meets the demand of ordinary timetabling problem, but also satisfies the network schools especially complicated standard.Keywords: Distance-Learning, time tabling, Artificial Intelligence, genetic algorithms，evolutionary algorithms，Constraint Logic Programming(CLP)目錄第一章 緒論1.1 網(wǎng)絡(luò)教育特點(diǎn)和發(fā)展現(xiàn)狀1.2 本課題的研究背景1.3 本課題的研究目標(biāo)1.4 本課題研究應(yīng)解決的主要問題第二章 排課問題的理論介紹2.1 排課問題的誕生2.2目前排課問題的幾個(gè)普遍的算法2.2.1 Simulated Annealing2.2.2 Constraint Logic Programming2.2.3 Graphic Coloring Heuristics2.2.4 Genetic Algorithms2.2.5 Linear Programming2.3 小結(jié)第三章排課問題的要求3.1 對本排課系統(tǒng)的要求3.1目標(biāo)3.2排課的基本情況3.2.1教學(xué)任務(wù)的劃分3.2.2不同教學(xué)任務(wù)教學(xué)時(shí)間的安排3.2.3排課中按照課程重要性的劃分3.2.4關(guān)于排課時(shí)間的概念3.2.5關(guān)于中同一門課程的持續(xù)時(shí)間的安排3.3排課過程中遇到的各種條件和限制3.3.1排課系統(tǒng)必須滿足的條件(hard constraints)3.3.2排課系統(tǒng)會盡量爭取滿足的條件(soft constraints)3.4小結(jié)第四章 本課題所做排課系統(tǒng)的實(shí)現(xiàn)4.1 本排課系統(tǒng)的排課過程4.2 本排課系統(tǒng)的實(shí)現(xiàn)原理4.2.1 開發(fā)工具和前期準(zhǔn)備4.2.2排課系統(tǒng)的基本思路和算法4.3 本排課算法的小結(jié)第五章 本排課系統(tǒng)的使用介紹5.1 信息的輸入5.1.1教室信息的輸入5.1.2班級信息的輸入5.1.3課程信息的輸入5.1.4教師信息的輸入5.2課表的生成第六章 總結(jié)和展望6.1本課題完成的總結(jié)6.2對于排課系統(tǒng)的期望6.2.1排課系統(tǒng)的架構(gòu)6.2.2 use case技術(shù)6.2.3 COM/DCOM標(biāo)準(zhǔn)對象模型致 謝參考文獻(xiàn)與附錄：第一章 緒論隨著社會科技的不斷發(fā)展，特別近20年來在信息技術(shù)上所取得的革命性進(jìn)步，我們的生活方式也不可避免的不斷地受信息技術(shù)影響而改變，其中就包括我們長久以來的學(xué)習(xí)方式。有著長久歷史的課堂教學(xué)模式，由于有著地域（跨地域的不可行性），時(shí)間（時(shí)間上的不靈活性）以及資源（合格的教師資源和課堂資源的短缺性）已經(jīng)漸漸難以勝任現(xiàn)代社會日益增長的全民學(xué)習(xí)和終身學(xué)習(xí)的要求了。而與此同時(shí)，信息技術(shù)，特別是近年來迅速發(fā)展的互聯(lián)網(wǎng)(INTERNET)為我們帶來了一個(gè)全新的教育理念遠(yuǎn)程教育。1.1 網(wǎng)絡(luò)教育特點(diǎn)和發(fā)展現(xiàn)狀網(wǎng)絡(luò)教育可以是遠(yuǎn)程教育的一種模式。遠(yuǎn)程教育是指位于不同地點(diǎn)的教師和學(xué)生通過通信的方式來完成教學(xué)任務(wù)。遠(yuǎn)程教育的先驅(qū)應(yīng)該是郵件式的函授教育。通過郵件的函授教育，存在著教育雙方的延時(shí)非常嚴(yán)重的情況（郵件在兩地來回的時(shí)間），可謂不是非常的理想。隨著社會技術(shù)的不斷進(jìn)步，在上個(gè)世紀(jì)的二，三十年代出現(xiàn)了基于收音機(jī)的廣播教育。然后在上世紀(jì)的五，六十年代隨著電視的普及，又誕生了電視學(xué)校。不過，無論是廣播還是電視，教學(xué)中非常重要的交互性（教師和學(xué)生之間的及時(shí)互動）以及可回溯性（學(xué)生在任何時(shí)間想要復(fù)習(xí)一下以前所學(xué)的內(nèi)容）都由于技術(shù)的原因沒能很好實(shí)現(xiàn)。值得慶幸的是，隨著互聯(lián)網(wǎng)的飛速發(fā)展，遠(yuǎn)程教育的最新形勢，通過互聯(lián)網(wǎng)Internet或是局域網(wǎng)Intranet的網(wǎng)絡(luò)教育迅速興起，并且提供了目前為止作為理想的遠(yuǎn)程教育方式。目前的對于網(wǎng)絡(luò)教育的研究差不多集中在以下兩個(gè)領(lǐng)域：基于Web的遠(yuǎn)程教育和實(shí)時(shí)的遠(yuǎn)程教育。在基于Web的方式下，教學(xué)內(nèi)容以課間的形式放在Web服務(wù)器上，學(xué)習(xí)者可以在任意時(shí)間任意地點(diǎn)獨(dú)立地學(xué)習(xí)，我們稱之為以學(xué)生為中心的學(xué)習(xí)模式。而實(shí)時(shí)的遠(yuǎn)程教學(xué)則主要利用視頻會議系統(tǒng)傳輸視頻和音頻，購建一種分布式的教室，在這種環(huán)境下，教師和學(xué)生只是在物理位置上不同，我們稱之為面向教師的學(xué)習(xí)模式。在以上兩個(gè)研究領(lǐng)域中，基于Web的教學(xué)模式由于對系統(tǒng)配置無特殊要求，在Internet上應(yīng)用較為容易。而實(shí)時(shí)的遠(yuǎn)程教學(xué)模式，由于對傳輸視頻和音頻系統(tǒng)有較高要求，同時(shí)還要考慮到主教室和分教室之間互相配合的各種情況，運(yùn)作較復(fù)雜，但是由于交互性更好一點(diǎn)，所以在教學(xué)的效果上更甚一籌。所以，在目前的情況下，兩種教學(xué)模式互相依存，共同發(fā)展。比如上海交通大學(xué)的網(wǎng)絡(luò)學(xué)院教學(xué)模式，現(xiàn)在就以實(shí)時(shí)的遠(yuǎn)程教學(xué)模式為主，基于Web的教學(xué)模式為輔。1.2 本課題的研究背景為了適應(yīng)這種網(wǎng)絡(luò)的教育模式，上海交通大學(xué)網(wǎng)絡(luò)教育學(xué)院開發(fā)了一個(gè)非常集成度非常高的電子教務(wù)平臺。這個(gè)平臺所包括的教務(wù)管理內(nèi)容有1、 排課2、 注冊3、 學(xué)生基本信息統(tǒng)計(jì)4、 成績管理5、 畢業(yè)資格審查6、 證書制作、發(fā)放7、 歸檔其中，排課的部分又細(xì)分為1、 按專業(yè)制定教學(xué)培養(yǎng)計(jì)劃（全部課程，包括畢業(yè)設(shè)計(jì)或論文）；2、 按專業(yè)制定每學(xué)期教學(xué)執(zhí)行計(jì)劃；3、 按開設(shè)的課程聘請（落實(shí)）上課教師；4、 根據(jù)教學(xué)執(zhí)行計(jì)劃、學(xué)生人數(shù)、學(xué)生選課地點(diǎn)、教師要求及教室等情況排課；但是，在電子教務(wù)系統(tǒng)中，排課的工作目前仍就是由負(fù)責(zé)排課的教師手工編排。當(dāng)學(xué)院開設(shè)的課程越來越多以后，教師的安排，教室的安排和課程的安排，各種制約條件之間的矛盾會越來越難處理。用手工編排，費(fèi)時(shí)費(fèi)力費(fèi)心，還難免會有顧此失彼的情況發(fā)生，所以將排課部分由計(jì)算機(jī)來完成這一工作變的日益重要。而縱觀目前市面上說流行的各種排課系統(tǒng)軟件，不是小學(xué)版的，就是中學(xué)版的，主要原因是中小學(xué)的上課安排規(guī)律性很強(qiáng)，每次上課人數(shù)由一個(gè)班級組成，不需要換教室，沒有上下學(xué)期課程不同之分，每天上課都為早上4節(jié)，下午2-3節(jié)的固定時(shí)間。沒有晚上要上課的要求，白天也不會有課時(shí)空著等等情況出現(xiàn)。而大學(xué)的排課問題就要復(fù)雜很多，而且各個(gè)大學(xué)的教學(xué)情況不同，導(dǎo)致對排課的要求也有很大的不一樣。所以，目前適合大學(xué)排課的軟件市面上比較罕見。而網(wǎng)絡(luò)教育學(xué)院的排課比起普通的大學(xué)排課方式，更要麻煩許多。比如，網(wǎng)絡(luò)學(xué)院的教室就有多媒體教室，視聽教室等等目前普通的大學(xué)排課中還沒有遇到的問題。而且，在網(wǎng)絡(luò)學(xué)院的授課中，有時(shí)還會出現(xiàn)教師在主教室上課，而通過連線的方式，另外有一部分同學(xué)在分教室上課的情況。至于是否能進(jìn)行連線上課，除了要考慮教室的容量和學(xué)生的數(shù)目，還要考慮所授課程是否適合在不同的教室中連線授課，還要考慮教室的性質(zhì)是否能符合連線上課在技術(shù)上的要求。并且在目前網(wǎng)絡(luò)學(xué)院的教學(xué)中，除了普通的本科生教學(xué)任務(wù)外，還有為了滿足社會需求而開設(shè)的工程碩士課程，其課程又要求安排在雙休日和星期一至星期五的晚上，而且其每個(gè)課時(shí)的長短，每天上課的課時(shí)數(shù)又和普通網(wǎng)絡(luò)學(xué)院的本科生有很大不同。所以由此產(chǎn)生的現(xiàn)實(shí)是，市面上無數(shù)種軟件中沒有為網(wǎng)絡(luò)學(xué)院的排課所開發(fā)的軟件。因此，作為計(jì)算機(jī)領(lǐng)域的一個(gè)經(jīng)典課題，本文的研究課題，“排課系統(tǒng)”，作為網(wǎng)絡(luò)教育學(xué)院電子教務(wù)平臺的一個(gè)補(bǔ)充，在這樣的背景環(huán)境下被提了出來。1.3 本課題的研究目標(biāo)排課系統(tǒng)的本質(zhì)目標(biāo)是合理安排一個(gè)學(xué)期中所有的時(shí)段，模塊，教室還有教師，使之不互相沖突。由于教室，時(shí)間，教師等資源的有限供應(yīng)性（limited available），由此就意味著排課系統(tǒng)必須有一些必須滿足的制約(hard constraints)，從而才能滿足特定的條件。在滿足以上排課的硬性要求要求，如教室的不沖突，教師的不沖突，課程的不沖突的目標(biāo)以后，還應(yīng)該盡一切可能滿足一些不一定必須滿足但最好滿足得要求(soft constraints)比如，將主課盡量的安排在上午等等。最后，在完成上面這些常規(guī)排課的要求上，本課題尚需結(jié)合上海交通大學(xué)網(wǎng)絡(luò)教育學(xué)院的實(shí)際情況，比如因?yàn)橐ㄟ^網(wǎng)絡(luò)上課，對教室有各種性質(zhì)的要求，最后能夠開發(fā)出能夠滿足本校網(wǎng)絡(luò)教育排課這一特殊要求的排課程序出來。1.4 本課題研究應(yīng)解決的主要問題（1） 排課問題數(shù)學(xué)模型的建立。（2） 排課問題中各種限制性制約(hard constraints)條件如何滿足。（3） 排課問題中優(yōu)化條件的如何完成。（4） 由于排課是一個(gè)大規(guī)模排列組合的問題，所有得可能性非常大，所以如何對搜索的規(guī)模進(jìn)行一定的縮小，也是一個(gè)非常重要的問題。第二章 排課問題的理論介紹2.1 排課問題的誕生最近的30年來，排課(time tabling)受到了越來越大的關(guān)注。各種關(guān)于排課的文獻(xiàn)，理論，方法也層出不窮，并且這種趨勢仍有繼續(xù)下去的跡象。各種關(guān)于排課的方法不斷更新，很大一部分原因是因?yàn)榻陙韺W(xué)校教學(xué)的方式在不斷的改變（比如上海交通大學(xué)現(xiàn)在就有了網(wǎng)絡(luò)教育學(xué)院），而排課的方法也必須跟著學(xué)校教學(xué)方式的改變而不斷改變。每一個(gè)學(xué)年或是學(xué)期，大學(xué)的教務(wù)管理當(dāng)局都必須設(shè)計(jì)出一張全新的課程表，而隨著大學(xué)教育規(guī)模的擴(kuò)大和教學(xué)模式的復(fù)雜化，要排出一張理想的課程表成為了一件非常令人頭疼的任務(wù)。其中讓人倍感困惑的就是在排課中有一系列共享資源（比如教室，教師）的課件（modules）引起互相之間的矛盾或說是制約(Constraints)。以上海交通大學(xué)網(wǎng)絡(luò)學(xué)院為例，每一個(gè)課件（modules）通常有兩個(gè)學(xué)時(shí)或是三個(gè)學(xué)時(shí)構(gòu)成。在排課的時(shí)候，若干互相制約的條件必須被考慮到。比如，不能有兩門課（course）在同一時(shí)間，在同一教室上課?；蛘呓淌业娜萘勘壬线@門課的同學(xué)數(shù)量來的小。或者，考慮的更遠(yuǎn)一點(diǎn)，除了這些必須滿足的限制性條件外，還會有一些希望滿足的優(yōu)化條件，比如一些比較重要的課程，最好能安排在上午完成。為了便于管理，同一專業(yè)的英語課程最好能安排在同一時(shí)間完成。等等。還有就是，在某些的固定時(shí)段，某些課程的教師會有進(jìn)修的任務(wù)或是開會的任務(wù)等等，不一而足?？傊?，也就是，在這些時(shí)候，這些教師不能上課，或者說，某些班級的某些課程就不能安排在一周中的這些特定時(shí)段。由于，排課問題是一個(gè)比較經(jīng)典的計(jì)算機(jī)難題，特別是大學(xué)的課程。而我們學(xué)校網(wǎng)絡(luò)學(xué)院，由于授課方式的更為靈活，教學(xué)手段和途徑和傳統(tǒng)的授課方式又有所不同，因此，要做這樣一個(gè)排課的系統(tǒng)就更為困難。所以，迄今為止，絕大多數(shù)的課程表都由人手工完成，除了比較費(fèi)時(shí)費(fèi)力以外，還比較有可能出現(xiàn)一些前后互相矛盾的地方。為此，就算排課問題是一個(gè)比較困難的問題，針對我們學(xué)校網(wǎng)絡(luò)學(xué)院特殊情況的排課系統(tǒng)還是有開發(fā)的必要。通常來說，一張課程表的完成可以分為獨(dú)立的兩個(gè)步驟（1） 教學(xué)資源的分配，如上課時(shí)間，教室，課程等等信息的配置。具體來講，就是那個(gè)班級要上哪些課程，每個(gè)班級的人數(shù)，每門課具體的教師的安排，以及這些教師什么時(shí)候有空等。結(jié)合到網(wǎng)絡(luò)學(xué)院的特殊情況，還必須考慮到上課的教室有沒有一些特殊要求，是否允許幾個(gè)教室之間連線上課等等。（2） 一個(gè)可以接受的課程表的設(shè)計(jì)實(shí)現(xiàn)和完成，所謂可以接受的課程表就是必須滿足先前定義各種限制性的條件，而且要比較好的滿足各種非強(qiáng)制性的期望條件（優(yōu)化條件）的課程表。目前為止來說，由計(jì)算機(jī)能做的只能是第二個(gè)部分的工作，而第一部分的工作通常要排課的老師輸入或決定。而且就長遠(yuǎn)來說，第一部分的工作計(jì)算機(jī)估計(jì)永遠(yuǎn)無法完全的由人來完成。2.2目前排課問題的幾個(gè)普遍的算法作為計(jì)算機(jī)領(lǐng)域的一個(gè)比較經(jīng)典的問題，排課算法的研究在國內(nèi)仍然不是非常普遍。有關(guān)排課算法的相關(guān)資料，國內(nèi)的材料十分的鮮見。雖然，市面上排課的軟件不少，但大多數(shù)卻是為中，小學(xué)開發(fā)的，難度也相對較低。不過，在國際上，有關(guān)排課算法的文章相對就較多，而且雖然迄今為止，沒有所謂最完美，或者說是最佳的排課算法，但由于所做的研究相當(dāng)多，所以已經(jīng)有了較為成熟和理想的排課算法。以下，就是目前為止，較為常見的幾種排課的算法或也可以稱之為技術(shù)。2.2.1 Simulated Annealing 這個(gè)算法名字Simulated Annealing 1420的中文直譯應(yīng)該是“模擬淬火”算法，不過我沒有看到過相關(guān)的中文資料，所以決定還是保留其英文的原名比較好。Simulated Annealing (SA)算法被廣泛應(yīng)用于處理各種不同組合優(yōu)化問題，特別是在學(xué)校的排課計(jì)劃中。其基本的算法描述如下圖所示。Figure 2.1: The Simulated Annealing AlgorithmSA算法相對其他的一些全局優(yōu)化技術(shù)有優(yōu)點(diǎn)也有缺點(diǎn)。優(yōu)點(diǎn)之一是非常容易實(shí)現(xiàn),幾乎可以應(yīng)用到任意一個(gè)組合優(yōu)化問題中去，能為大多數(shù)問題提供解決方案，并能與專家系統(tǒng)等啟發(fā)式方法相結(jié)合解決一系列復(fù)雜的問題。所以SA是一個(gè)比較可靠的技術(shù),不過它的確仍有缺點(diǎn)。為了得到一個(gè)好的結(jié)果，升級的過程以及各種可調(diào)節(jié)變量的選取變的非常重要。而且，SA技術(shù)比較消耗時(shí)間，運(yùn)行的時(shí)候速度比較慢。最顯而易見的將排課問題（Timetabling Problem）映射到Simulated Annealing Algorithm的構(gòu)造如下1. state是一個(gè)包含如下集合的課表: o P: 教師的集合 o C: 班級的集合 o S: 學(xué)生的集合 o R: 教室的集合 o I: 時(shí)間段的集合. 2. cost 或是 E(P, C, S, R, I)定義如下： o E(P): 是分配超過定額 的課同一位教師所引發(fā)沖突的代價(jià)，在計(jì)劃外增加一門或若干門課在教師的計(jì)劃中所引起的沖突 o E(C):是將若干門課程安排在同一時(shí)間上課引發(fā)得不可避免沖突的成本 o E(S):是將不屬于某些學(xué)生專業(yè)的課程安排的這些學(xué)生課表中去所引發(fā)的矛盾的成本o E(R):是將教室分配給不合適（指容量上）班級而引起沖突的成本o E(I):是課時(shí)分配過多或過少所引起沖突的成本3. swap (move) 是以下一個(gè)或多個(gè)班級在集合 C中 班級 和 班級 再考慮到時(shí)間段和 ,以及教室 和 所做的置換。一般來講，每一個(gè)步驟就是指這樣的一次班級的swapping。Figure 2.2： Mapping2.2.2 Constraint Logic ProgrammingConstraint Logic Programming (CLP) 217 是由Logic Programming (LP)結(jié)合限制系統(tǒng)中的限制操作而成。從而產(chǎn)生的一種新的語言結(jié)合了LP 的優(yōu)點(diǎn)(declarative semantics, non-determinism, relational form) 與限制解決算法（constraint-solving algorithms）的高效率。由此，這一語言的優(yōu)勢保障用戶無需關(guān)心搜索的技術(shù)，限制的聲明是明白無誤的而且容易修改和擴(kuò)展。在限制邏輯編程的范例中，有關(guān)限制滿足的問題可以被寫成一個(gè)Horn子句的形式，也就是各種限制性的條件被包含進(jìn)子句中。而當(dāng)程序運(yùn)行的時(shí)候，各種限制相應(yīng)產(chǎn)生被傳遞到限制解決機(jī)制中去。而這一機(jī)制應(yīng)用“域獨(dú)立”(Domain Independence)限制滿足技術(shù)，比如線性程序或者布爾判斷等來找到一個(gè)可行的解決方案。所以，這種方法仍舊是基于搜索的，不過可以有效的減少搜索范圍。限制邏輯編程非常適合排課問題。因?yàn)樗试S所有的公式將限制明示化。雖然，這個(gè)方法的表現(xiàn)會由于排課中的一些小改動而受到極大影響。不過經(jīng)改動多的排課公式仍能很好的滿足各種邏輯條件。而且由于排課問題本質(zhì)上是一個(gè)大規(guī)模的組合問題，所以有一個(gè)極為龐大的搜索范圍。因此，通過用CLP語言解決這個(gè)問題，可以將搜索的范圍壓縮到一個(gè)較小的基礎(chǔ)上并能很好的控制住搜索的時(shí)間。2.2.3 Graphic Coloring Heuristics Graphic Coloring Heuristics 5這個(gè)算法的基本思想是這樣的，假設(shè)有S1-S10這是十名學(xué)生，他們所選的課程分變?yōu)閑1-e6中的若干門，如表2.1所示。StudentLectureS1e1,e2,e3,e6S2e1,e2,e3,e5S3e1,e2,e3,e5S4e1,e2,e5S5e4S6e4,e5S7e2,e4S8e2,e4,e6S9e3,e4,e6S10e3,e4,e6Table 2.1：Example of Student-Lecture Data則我們可將他們之間的這種關(guān)系映射到下圖所示的關(guān)系中去。由于，學(xué)生S1會選擇e1,e2,e3和e6這四門課，所以將e1e2,e1e3,e1e6,e2e3,e2e6,e3e6連起。凡是，同一線段的兩端的兩門課程就不能在同一時(shí)間開設(shè)。Figure 2.3：Graph coloring for a simple timetabling problem不過，這個(gè)算法的用途比較廣泛，但有一個(gè)比較大的缺點(diǎn)，就是特殊應(yīng)用的限制(application-specific constraints)不能很好的整合到這一方法中去。2.2.4 Genetic Algorithms遺傳算法Genetic Algorithms或稱為進(jìn)化算法Evolutionary Algorithms 810引起了越來越多的關(guān)注。有關(guān)遺傳算法在排課領(lǐng)域中的應(yīng)用最早出現(xiàn)于1990左右，由Colorni 53提出，并隨之迅猛發(fā)展。在1997年8月舉行的國際自動排課會議(PATAT97)上，將近1/4的報(bào)告中或多或少的有進(jìn)化算法的技術(shù)。而此前1995舉行的會議上，更有近1/3的報(bào)告是基于遺傳算法。這些數(shù)字表示進(jìn)化算法已經(jīng)成為一個(gè)用來處理一系列較大范圍的排課問題的成熟和成功的方法。遺傳算法的理論受啟發(fā)于達(dá)爾文的進(jìn)化論理論。在遺傳算法中，一系列的解決方案(solutions)對于一個(gè)特定問題(chromosomes)的表現(xiàn)(performance)被評估(evaluated)和被排序（ordered）,然后選出其中表現(xiàn)較好的解決方案作為雙親（parents），然后在將這些parents進(jìn)行適當(dāng)?shù)淖儺惒僮?mutation)或是將兩個(gè)parents進(jìn)行交叉組合的操作（crossover operation），由此由這些parents方案產(chǎn)生一個(gè)或多個(gè)子方案(children).然后這些新產(chǎn)生的方案再次被評估，周而復(fù)始，直到有滿足條件的方案產(chǎn)生。2.2.5 Linear Programming Linear Programming 21是對排課問題進(jìn)行線性求解，通常并不能得到最佳的解。本文的課題的研究，雖然主體上仍舊是基于線性求解的基礎(chǔ)之上，但是在求解的時(shí)候，有優(yōu)先級方面的設(shè)置和一些改動，所以可以在線性求解的基礎(chǔ)上得到一個(gè)較佳的可接受的排課方案。2.3 小結(jié)排課問題發(fā)展到現(xiàn)在的程度，仍舊沒有所謂做理想，最完美的排課方案。各種常見的排課方案，都各有優(yōu)點(diǎn)和缺點(diǎn)。用一種排課方案，不可能做到非常好地解決所有的排課問題。但是，一個(gè)特定的排課環(huán)境，有可能可以找到一個(gè)較理想的排課方案。而且，關(guān)于排課問題的研究，仍舊在不斷深入的研究中。我們現(xiàn)在已經(jīng)可以用計(jì)算機(jī)自動排出一張可以接受得課表了，相信隨著我們的努力，我們將來排出的課表一定會越來越人性化。 第三章排課問題的要求3.1 對本排課系統(tǒng)的要求本課題誕生的原因是因?yàn)樯虾＝煌ù髮W(xué)的網(wǎng)絡(luò)教育學(xué)院需要一套適合網(wǎng)絡(luò)學(xué)院多樣化教學(xué)任務(wù)的排課系統(tǒng)，而排課問題又是計(jì)算機(jī)領(lǐng)域中一個(gè)叫經(jīng)典的問題，正是因?yàn)橛羞@樣一個(gè)契機(jī)，所以本文的研究課題就放在了排課問題得研究上，更確切的說，是網(wǎng)絡(luò)學(xué)院的排課問題的研究上。3.1目標(biāo)本排課系統(tǒng)的目標(biāo)是能夠根據(jù)網(wǎng)絡(luò)學(xué)院的教學(xué)執(zhí)行計(jì)劃、學(xué)生人數(shù)、學(xué)生選課地點(diǎn)、教師要求及教室等情況由計(jì)算機(jī)智能地排出符合要求的課程表。在排課過程中，本排課方案必須滿足所有的限制性條件(hard constraints),也就是不會有沖突的情況出現(xiàn)，同時(shí)還會盡最大的努力完成盡可能多的優(yōu)化性條件（soft constraints）。3.2排課的基本情況3.2.1教學(xué)任務(wù)的劃分按照網(wǎng)絡(luò)學(xué)院的授課對象的不同，需要安排的課表有為網(wǎng)絡(luò)學(xué)院全日制本科學(xué)生所開的課程，有為專升本的學(xué)生所開的課程，還有為工程碩士所開的課程。而按照這些所開課程的不同，在教學(xué)時(shí)間的安排上可以分為全日制和業(yè)余制兩種。其中，網(wǎng)絡(luò)學(xué)院的本科學(xué)生上課時(shí)間屬于全日制，而專升本的同學(xué)，以及工程碩士的同學(xué)的上課時(shí)間屬于業(yè)余制。3.2.2不同教學(xué)任務(wù)教學(xué)時(shí)間的安排全日制的教學(xué)任務(wù)安排在周一至周五的白天業(yè)余制的教學(xué)任務(wù)則安排在周一至周五的晚上，以及周六和周日的全天（白天，晚上）全日制的上課時(shí)間為 上午 4節(jié)（最多） 周一至周五 下午 4節(jié)（最多） 周一至周五業(yè)余制的上課時(shí)間為 上午 5節(jié)（最多） 周六和周日 下午 6節(jié)（最多） 周六和周日 晚上 4節(jié)（最多） 全周3.2.3排課中按照課程重要性的劃分按照課程的重要性劃分，可將全日制的課程劃分為主干課和非主干課之分，并且除此情況外，在重要性上無任何其他的劃分標(biāo)準(zhǔn)。同樣，業(yè)余制的課程也存在主干課和非主干課的區(qū)別，并且除此情況外，在重要性上無任何其他的劃分標(biāo)準(zhǔn)。3.2.4關(guān)于排課時(shí)間的概念因?yàn)槊繉W(xué)期開學(xué)的時(shí)間（指日歷時(shí)間,年月日）無法確定。同時(shí)，在學(xué)期過程中的節(jié)假日換課或停課等情況，也非排課系統(tǒng)事先所能掌控，所以在本排課系統(tǒng)中涉及的時(shí)間只有周數(shù)，第幾周之類的概念，以及某一周中第幾天的概念（周一到周七），沒有年月日的概念，所以本排課系統(tǒng)是一個(gè)基于周概念（weekly）的排課系統(tǒng)。與此類似的情況是，在排課中預(yù)先設(shè)定上課的小時(shí)和分鐘的概念，也不是非常的合理。因?yàn)椋覀儫o法保證每天上午，下午還有晚上開始上課的時(shí)間，或是每節(jié)課的長短，甚至課間的休息時(shí)間在將來一定不會變化。所以，如果將小時(shí)和分鐘排進(jìn)排課系統(tǒng)的算法中，難免在將來會造成某種程度上的困惑。另外的一個(gè)原因是，全日制和業(yè)余制的上課時(shí)間，無論是課時(shí)長短，還是課間休息的時(shí)間都完全不一樣。如果，在排課的核心算法思想中，將小時(shí)和分鐘的單位寫入，將無法同時(shí)處理全日制和業(yè)余制這兩種不同的情況。所以，在本排課系統(tǒng)中每天的課程安排，只有課時(shí)的概念，單位是“節(jié)”，而沒有小時(shí)和分鐘的概念。在課表安排出來以后，小時(shí)和分鐘這類的時(shí)間概念可有排課老師對應(yīng)上課的節(jié)數(shù)靈活的添置上去。3.2.5關(guān)于中同一門課程的持續(xù)時(shí)間的安排根據(jù)網(wǎng)絡(luò)學(xué)院排課教師的多年排課經(jīng)驗(yàn)和要求，每門課的持續(xù)上課時(shí)間以2節(jié)課或者是3節(jié)課構(gòu)成比較合理，極端情況才允許下可能有4節(jié)課，但不可能存在只上1節(jié)課或者連續(xù)上課超過4節(jié)課的情況出現(xiàn)。3.3排課過程中遇到的各種條件和限制排課中必須滿足的條件也就是排課中的限制性條件(hard constraints),如果不能完全滿足這些條件的話，這會引起各種各樣的沖突（conflicts），比如同一時(shí)間，會出現(xiàn)一個(gè)教師要在兩個(gè)不同的地點(diǎn)（教室）上課的情況，或者同一時(shí)間，同一個(gè)教室被安排給多個(gè)不同的班級上不同的課程。很明顯，以上的這些沖突在我們目前認(rèn)知的三維空間是無法完成的，這樣排出來的課表也就是沒有意義或價(jià)值的同時(shí)，排課的時(shí)候還會有一些不是一定需要滿足，但是應(yīng)該盡一切可能完成的條件(soft constraints)，。比如說，要把主干課程安排在上午上課。雖然，違反這一條件不會引起物理意義上的沖突，可以按照這樣的課表上課。但是，這樣排出的課表不會受到同學(xué)和老師的歡迎，是一張非常不科學(xué)的課表，所以也是沒有什么價(jià)值或意義的。在本課題的研究中，所遇到的必須滿足的條件(hard constraints)以及盡量滿足的條件(soft constraints)如下。3.3.1排課系統(tǒng)必須滿足的條件(hard constraints)以下的條件是一些排課系統(tǒng)默認(rèn)的，不需要排課教師人工協(xié)助設(shè)置的，理所當(dāng)然應(yīng)該必須滿足的條件。(1) 每個(gè)班級每個(gè)學(xué)期所指定要完成的課目都必須要被安排，也就是不能出現(xiàn)漏排一門課這類的情況。 (2) 每個(gè)班級每個(gè)學(xué)期所要完成的課目只是被要求完成的課目，也就是不能出現(xiàn)多排一門課這類的情況。(3) 每門課程教學(xué)所需的課時(shí)數(shù)必須要被滿足，也就是每個(gè)班級每周的上課課時(shí)*上課的周數(shù)=每門課程的教學(xué)課時(shí)數(shù)。其中要注意的是，國慶假期等放假，停課情況不在排課系統(tǒng)的考慮范圍之內(nèi)。(4) 同一時(shí)間教師的安排不能有沖突，也就是同一個(gè)教師不能同一時(shí)間在兩個(gè)地點(diǎn)（教室）上課，也不可以在同一時(shí)間，同一地點(diǎn)，教授兩門不同的課程。(5) 同一時(shí)間教室的安排不能有沖突，也就是同一時(shí)間同一教室，不能安排兩批不同的班級學(xué)不同的課程。(6) 全日制的教學(xué)任務(wù)能且只能安排在周一至周五的白天，這里的白天是指上午的4節(jié)課和下午的4節(jié)課。(7) 業(yè)余制的教學(xué)任務(wù)能且只能安排在周一至周五的晚上（4節(jié)課），以及周六和周日全天（上午的4節(jié)課和下午的4節(jié)課）。以下的條件由排課的老師人工協(xié)助給出，可以認(rèn)為是排課中各種所需的條件變量。(1) 每學(xué)期課程課時(shí)的安排每學(xué)期每門課程的課時(shí)有可能會是36學(xué)時(shí)，48學(xué)時(shí)或者72學(xué)時(shí)等等，這些信息需要排課的老師給出。同時(shí)，每門課程的開始時(shí)間，第幾周開始，（因?yàn)椴⒉皇撬械恼n程都是第一周開始，由的課程會在期中開始），這些信息均需要由排課的老師給出。(2) 哪些課程是主干課，哪些課程不是主干課,這些信息同樣由排課老師給出，因?yàn)橛?jì)算機(jī)無法通過課程的名字就知道哪些課程更為主干。(3) 任課老師與課程之間的聯(lián)系，也即哪門課由哪位老師上，甚至同一專業(yè)，同一年級，相同的課程，如英語課，某個(gè)班級的英語課由某位老師上課，都由排課的老師指定，不存在任意的情況。(4) 某些任課老師因?yàn)橐M(jìn)修，開會的關(guān)系，有些時(shí)間不能來上課，也即由這些任教某些課程只能安排在一周的一些指定時(shí)段中，以上信息也需要由排課的老師給出。(5) 某些課程必須在有特定功能的教室上課，如多媒體教室，視聽教室，機(jī)房等。每門課程所需教室功能的信息由排課老師給出。默認(rèn)情況下，任何課程都需要在多媒體教室完成。(6) 一同上課的班級由排課老師給定。教室的容量不能小于上課的學(xué)生數(shù)。特別需要注意的是，對于非主干課程，可以在多個(gè)多媒體教室聯(lián)網(wǎng)上課。而主干課程必須在同一個(gè)教室完成。而如果上的是選修課的話，因?yàn)樯线x修課的人數(shù)和可能選修這門課程的班級相加的人數(shù)不一定相同，所以排課的老師還需要給出實(shí)際選上這門課的同學(xué)的人數(shù)。(7) 幾個(gè)班級合并上課的問題。幾個(gè)不同的班級，由同一個(gè)教師上的相同課程，這幾個(gè)班級是否可以或必須合并在一起上（即同一時(shí)間，同一地點(diǎn)）的問題，由排課老師做出決定 。(8) 由于業(yè)余制有校外的教室，當(dāng)主教室排課時(shí)間與校外教室使用有沖突的時(shí)候，能靈活的改變主教室的排課時(shí)間。（也就是能告知修改過的課程表是否有沖突）3.3.2排課系統(tǒng)會盡量爭取滿足的條件(soft constraints)(1) 主干課盡量安排在上午完成。(2) 同一專業(yè)的英語課盡量安排在同一時(shí)間位置一起上，如同一專業(yè)有4個(gè)班級，則最好前兩節(jié)課1，2班并上，后兩節(jié)課3，4班并上。(3) 同一門課程在一周中的相隔時(shí)間希望至少相隔兩天。(4) 盡量優(yōu)先使用網(wǎng)絡(luò)學(xué)院的教室。(5) “大學(xué)英語”課盡量安排在視聽教室上。(6) 體育課盡量安排在3，4節(jié)課上。(7) 周三的下午盡量不排課。3.4小結(jié)以上的各種限制性條件，不論是必須完成的限制性條件(hard constraints)，還是應(yīng)盡量爭取滿足的條件(soft constraints)，都是在與網(wǎng)絡(luò)學(xué)院的排課教師多次反復(fù)的磋商后得到的結(jié)果。而需要排課老師協(xié)助完成的那些條件變量，則是在開發(fā)這個(gè)排課系統(tǒng)中不斷遇到問題的解決。比如，本來“幾個(gè)班級合并上課的問題。幾個(gè)不同的班級，由同一個(gè)教師上的相同課程，這幾個(gè)班級是否可以或必須合并在一起上（即同一時(shí)間，同一地點(diǎn)）的問題，由排課老師做出決定?！边@一點(diǎn)我并沒有想到，但是在開發(fā)的時(shí)候，就發(fā)現(xiàn)做不下去了，因?yàn)樵谶@種兩可的情況下，會讓計(jì)算機(jī)很難“做人”的，所以這個(gè)問題只能交由排課的老師完成。而且，在上面的所有條件中，可以看出，所謂的必須完成的限制性條件(hard constraints)是絕大多數(shù)排課系統(tǒng)都要完成的。而在應(yīng)盡量爭取滿足的條件(soft constraints)部分，則每個(gè)學(xué)校和學(xué)院的差別就很大了。第四章 本課題所做排課系統(tǒng)的實(shí)現(xiàn)4.1 本排課系統(tǒng)的排課過程如圖4.1所示，排課的時(shí)候首先由排課老師從教務(wù)處取得詳細(xì)的課程設(shè)置，包括所有專業(yè)的課程目錄，課時(shí)數(shù)，課程開始的時(shí)間，那些是主干課，哪些不是，每周上課的次數(shù)，對該課程的具體要求等等，以及可以用來上課的教室的信息。然后，排課老師向任課的老師發(fā)出請求時(shí)間表，也就是詢問任課老師什么時(shí)候可以來上課，什么時(shí)候沒空不能來上課。最后，如果有選修課的話，排課的老師還要統(tǒng)計(jì)每門選修課的實(shí)際人數(shù)。等以上準(zhǔn)備工作都完成以后，排課的老師則將以上的規(guī)則整理，輸入排課系統(tǒng)。同時(shí)，加上各種排課規(guī)則優(yōu)先順序和一部分限制性條件。交由排課系統(tǒng)來嘗試排課。Figure 4.1: 排課的過程由于，資源的有限性和限制性條件的作用，交由排課系統(tǒng)的信息有可能存在互相矛盾的地方，也就是沒有辦法排出一張課表。如果遇到這種情況，則需要排課的老師與任課的老師相互協(xié)商，或是在各門課程中相互協(xié)商，以避開矛盾或沖突。如果，最后協(xié)商無效，則只能由排課老師強(qiáng)制調(diào)節(jié)沖突，也就是取消或削弱一些原來強(qiáng)制完成的限制性條件。有的問題協(xié)商也不一定能解決，比如資源的明顯不夠。比如，教師人數(shù)的不夠，還有就是教室數(shù)量的不足，大小不夠等問題。遇到這些問題，只能由排課的老師向?qū)W校再去申請新的教學(xué)資源，例如，要求增加更多的老師和教室等等。否則的話，排課系統(tǒng)肯定是無能為力的。等所有的條件可以滿足后，排課系統(tǒng)自動排列出符合所有限制性條件(hard constrains)和最大可能滿足優(yōu)化條件(soft constraints)的課程表。然后，再進(jìn)行打印，就可以得到網(wǎng)絡(luò)學(xué)院新學(xué)期的所有班級的課表了。4.2 本排課系統(tǒng)的實(shí)現(xiàn)原理4.2.1 開發(fā)工具和前期準(zhǔn)備本課題所做排課系統(tǒng)的核心開發(fā)是用標(biāo)準(zhǔn)C語言完成的。界面的完成是用到了微軟的MFC。用C語言做核心的原因一個(gè)是因?yàn)榕耪n系統(tǒng)是一個(gè)NP復(fù)雜度的問題，對時(shí)間的開銷很大。C語言的效率較高，可以有一個(gè)較快的速度。另外一個(gè)比較重要的原因是，開發(fā)排課系統(tǒng)前，由于缺少相關(guān)的資料，我并沒有百分百的信心可以做出一個(gè)排課系統(tǒng)。在這樣的情況下，我希望能夠先用較熟悉的C語言做出一個(gè)實(shí)驗(yàn)的版本出來，主要是先看一看我的想法和算法是否正確。否則的話，關(guān)鍵問題錯(cuò)誤，其他的問題就根本談不上了。4.2.2排課系統(tǒng)的基本思路和算法4.2.2.1排課的幾個(gè)核心函數(shù)(1) Input函數(shù)(2) Comp函數(shù)(3) Ready函數(shù)(4) Calc函數(shù)(5) Add函數(shù)(6) Del函數(shù)4.2.2.2排課的流程和各函數(shù)的作用排課的第一步，是由排課的老師在視窗界面中，輸入排課的所需的各項(xiàng)信息。包括有教室的信息，教師的信息，課程的信息，班級的信息，還有各種優(yōu)化性條件。等排課所需的所有信息輸入完畢后，界面的處理函數(shù)將以上信息打包成規(guī)范化的形式，寫入輸入文件lecture.in。Input函數(shù)的介紹Input函數(shù)將處理是lecture.in的信息。在Input函數(shù)中，要處理的事情主要有三件。首先是要生成一個(gè)教師的表格和一個(gè)教室的表格。這些表格用來紀(jì)錄在一周中的時(shí)間內(nèi)，教師或是教室在哪些時(shí)候有空。Input函數(shù)根據(jù)輸入的信息，需要將老師不能上課的時(shí)間以及教室不能開放的時(shí)間填出來。Input中做的第二件事是“減數(shù)分裂”。所謂的“減數(shù)分裂”是這樣的，某些課程在一周的時(shí)間中，要上兩次或是三次。這樣的直接排課的話，會比較麻煩。通過減數(shù)分裂，將這些課拆成完全相同性質(zhì)的兩門課或是三門課（術(shù)語應(yīng)該是Item）。這樣在減數(shù)分裂以后，在排課的時(shí)候，所有的“課程”都是一周只上一次，相對來說考慮起來就比較容易的。Input中做的另外一件比較重要的事情是周數(shù)的合并。其實(shí)做不做周數(shù)的合并，并不會影響算法的正確與否。做周數(shù)合并只是為了提高算法的運(yùn)行效率。因?yàn)椋谥軘?shù)合并之前，比如說，一個(gè)學(xué)期有18周，則在排課的時(shí)候需要考慮這18周的情況。如果一個(gè)教室第一周是有空的，那么它第二周是否有空哪，第三周又如何哪？以此類推，要考慮總共18周的情況?？墒?，如果這18周的情況完全相同的話，我們就可以將這18周合并起來，就當(dāng)成一周的情況來考慮。這樣，算法執(zhí)行的速度可以至少提高18倍。當(dāng)然周數(shù)的合并也是有一定條件的。如圖4.3所示的課程甲和課程乙的情況，課程甲的時(shí)間跨度就可以從第1周到第9周壓縮為“1周”考慮，而課程乙的時(shí)間跨度就可以從第10周到第18周壓縮為第“2周”。因?yàn)榭梢宰C明，當(dāng)一門課程結(jié)束的時(shí)候，另一門課程還沒有開始，則這兩門課程無論怎么安排，教室的安排或是教師的安排，都不會影響到另外一門課。Figure 4.3: 周數(shù)合并的情況一而如圖4.4的情況，課程甲和課程乙有一段沖突的時(shí)間。則課程甲和課程乙在周數(shù)上就無法合并了。因?yàn)椋n程甲在第一周的時(shí)候，某個(gè)時(shí)候某個(gè)教室空著，并不代表在第十周這個(gè)時(shí)候這個(gè)教室仍舊空著。因?yàn)檎n程乙有可能在第十周的這個(gè)時(shí)候會用這個(gè)教室。所以，到第十周的時(shí)候，一個(gè)很嚴(yán)重的沖突就發(fā)生了，兩門課程在同一時(shí)間用了同一個(gè)教室。這是不能允許的錯(cuò)誤。所以，很顯然，在這種情況下，課程甲和課程乙的周數(shù)都無法壓縮或說是將周數(shù)合并。Figure 4.4: 周數(shù)合并的情況二另外一種情況是像上圖所示，課程甲的長度整個(gè)跨過課程乙。則這個(gè)時(shí)候仍舊可以進(jìn)行周數(shù)的合并。因?yàn)樵谡n程乙雖然先結(jié)束，但對課程甲不造成任何影響。所以，我們可以假設(shè)課程乙的長度和課程甲相當(dāng)。然后，進(jìn)行周數(shù)的壓縮。當(dāng)然，在課程乙實(shí)際結(jié)束后，課程乙曾經(jīng)占用的資源會釋放出來，但幸運(yùn)的是，多出來的資源不會造成任何的沖突。Figure 4.5: 周數(shù)合并的情況三在Input函數(shù)即將完成的時(shí)候，最后調(diào)用了qsort函數(shù)。qsort函數(shù)是C語言的標(biāo)準(zhǔn)排序函數(shù)，排序的標(biāo)準(zhǔn)由Comp函數(shù)參數(shù)決定。所以，Comp函數(shù)的內(nèi)容其實(shí)是本排課系統(tǒng)的默認(rèn)優(yōu)先集的設(shè)定。在Comp函數(shù)中，總共有5個(gè)判斷函數(shù)。第一個(gè)判斷函數(shù)的作用是將主干課排在前面。因?yàn)?，在課程輸入的時(shí)候，每門課程都有一定的屬性，像主干課，非主干課，英語課，非英語課，等等。所以，這一標(biāo)準(zhǔn)就是將課程中有主干課屬性的放在前面，當(dāng)都是主干課在比較時(shí)，就將有英語課屬性的放在前面等等。第二個(gè)判斷函數(shù)的作用是將課時(shí)多的課程放在前面。所謂課時(shí)多的課，就是每次上課要連續(xù)上3節(jié)或是4節(jié)的課程，因?yàn)槲野l(fā)現(xiàn)這樣的課程往往比較難排。所以，有必要將他們提到比較前面一點(diǎn)，先進(jìn)行安排。第三個(gè)判斷函數(shù)的作用，是將選擇這門課班級人數(shù)多的排在前面。因?yàn)?，上課的人多，意味著相應(yīng)的教室要比較大，這也是一個(gè)相對來說較苛刻的條件，所以有必要先將他們安排好。第三，第四個(gè)函數(shù)做的事情是這樣的。因?yàn)椋覀兿惹皩⒁恢軆?nèi)要上幾次的課程都拆分開來了，認(rèn)為他們是幾門不同的“課程”。但是，很明顯，他們的課程屬性完全一樣，也就是他們的優(yōu)先級應(yīng)該完全一樣。在這種情況下，我希望在排序的時(shí)候，這些有原來一門課分裂出來的課程都能在隊(duì)列中緊鄰的排列。這樣我就有必要判斷哪些“課程”是由原先同一門課程分裂出來的，哪些不是。所以我要做以下兩個(gè)判斷。一 課程的名稱是否一樣。二 上課的班級是否一樣。如果，以上兩點(diǎn)完全相同的話，則我們有理由認(rèn)為這樣的兩門課就是原先由同一門課程分裂出來的，所以應(yīng)該在排序的時(shí)候緊鄰。完成第一次安C