高校排課問題的雙向匹配博弈分析

高校排課問題的雙向匹配博弈分析

1基于雙向匹配的排課設計由于教育資源相對有限，教學排課規(guī)模大，教學安排復雜，規(guī)律多變，尤其是高校課程，學生教學時間分別為每周、前后、分工、不同的班級、不同的教師、多班教師、大教室、小教室、特殊教室等。多年來，這一直是學校教育最復雜的復雜費用的問題。每年，由于師生對優(yōu)秀學生教育的滿意度很低，學校的教育管理和效率也有很大的限制。沒有一個相對完整的智能教學系統(tǒng)來解決這個問題。多年的研究及實踐表明,排課問題實質是一個多約束、非線性、模糊的時空組合的數(shù)學問題,眾多的排課設計算法均在自動篩選和自動組合方面存在一定缺陷,智能化程度不高,只是解決排課的部分問題。根據(jù)雙向匹配博弈理論,高校排課問題本質上均可看作是一個教師、班級(專業(yè)班或合班)、課程與教室在時間空間中的匹配問題,也即在滿足一些約束條件的前提下,把教室資源提供給各個需求教師,其主要目標就是依據(jù)各專業(yè)教學計劃將教室、教師、班級、課程安排在一周內某一個不發(fā)生沖突的時間里。如今在諸如男女婚配問題、醫(yī)生和醫(yī)院、工作崗位和員工、學生和學校、課程和老師、研究員和行業(yè)、病人和人體器官等等匹配市場上Gale-Shapley算法有著廣泛的應用,具有很強的應用性及操作性。本文提出基于雙邊匹配博弈理論及Gale-Shapley算法思想實現(xiàn)高校自動排課的策略,以期在解決課程、班級、教師、教室、時間沖突的基礎上,最大程度地提高師生對排課結果的滿意度,同時達到充分合理地利用學校各類教學資源的效果。2組成a或bj的較優(yōu)匹配1962年,美國數(shù)學家DavidGale和LloydShapley發(fā)明了一種尋找穩(wěn)定婚姻的策略,即延遲接受算法(DeferredAcceptanceAlgorithms),也稱G-S算法,旨在通過此算法尋找到市場中的穩(wěn)定匹配。2012年LloydShapley和美國經(jīng)濟學家AlvinE.Roth借助以“雙邊匹配理論和延遲接受算法(Gale-Shapley算法)”為基石在穩(wěn)定市場匹配理論和市場設計實踐上做出的卓越成績獲得了諾貝爾經(jīng)濟學獎。(1)G-S算法的核心思想:在一個雙邊匹配模型中存在兩個集合A={a1,a2,…,an}和B={b1,b2,…,bm},需要把集合A、B中元素匹配成穩(wěn)定有序對(ai,bj)。集合A(或B)中的每個個體均對另外一個集合B(或A)中的個體存在一個滿足完備性和可傳遞性的偏好函數(shù)P(x),x取值為ai或bj,例如若P(ai)={bj1,bj2,…,bjm},則表示ai第一選擇為bj1,第二選擇為bj2,依此類推;同理P(bj)={ai1,ai2,…,ain},則表示bj第一選擇為ai1,第二選擇為ai2,依此類推。(2)集合A、B中元素匹配成穩(wěn)定有序對(ai,bj)的匹配機理:第一輪匹配開始,集合A中的每個個體按照各自偏好函數(shù)向集合B中排在自己第一選擇順序的個體發(fā)送選擇信息,而B中所有收到選擇信息的個體從收到的選擇信息中根據(jù)自己的偏好函數(shù)選擇排在最優(yōu)先的選擇信息作為“暫時性接受”的匹配對象,同時拒絕其他的選擇信息,當然也可以全部拒絕。第二輪匹配開始,所有上輪A中還沒有匹配成功(被拒絕)的個體ai再次向B中自己還沒有發(fā)送過的個體bj按自己的偏好函數(shù)選擇順序排在最前的個體發(fā)送信息(無論該個體是否配對),而B中所有收到選擇信息的個體從收到的選擇信息(包括現(xiàn)有的匹配對象)中根據(jù)自己的偏好函數(shù)選擇排在最優(yōu)先的選擇信息作為“暫時性接受”的匹配對象,同時拒絕其他的選擇信息,當然也可以全部拒絕。第三輪匹配還是按照第二輪的規(guī)則進行,以此類推。一直進行到不再有A中個體ai向B中個體bj發(fā)送選擇信息為止。然后所有被接受的個體ai和接受他個體bj達成最終匹配,匹配過程全部結束。3基于gale痙攣算法的大學教學策略3.1基于gs算法的思維定性分析高校排課問題涉及的教師、班級、課程、教室、時間匹配問題本質上可抽象為由教師、班級、課程構成的教學班集合與教室、時間構成的時空集合進行匹配的問題,即安排好一個教學班的教學任務,就意味著教師、班級、課程、教室、時間的匹配關系被確定了。這里設由教師、課程、班級(專業(yè)自然班或選課班)對應構成的教學班組成集合A,簡稱教學班集合,而由時間(教學時段)和教室構成的集合為B,簡稱時空集合,其中元素成為時空元素,那么排課問題就轉化為對集合A與集合B中元素的對應匹配問題。在GS算法中,要求集合A與集合B中元素對另一集合的元素有一個嚴格的偏好排序,故根據(jù)排課問題的需求情況,可建立如下的偏好排序原則。(1)教學班集合A中每一元素對時空集合B中所有元素的偏好,由教學班的任課教師對該班課程教學在時間和教室的分配上做出一種預期安排給出排序,即得集合A中每一個元素對B中元素的一個嚴格偏好排序,而這種偏好排序能充分體現(xiàn)教師作為專業(yè)教育者對課程、教學及自身工作安排上的合理化考慮。(2)時空集合B中每一元素對教學班集合A中所有元素的偏好,則由教學管理者根據(jù)排課應遵循的完備性、正確性、合理性、人性化等原則賦予該集合B的每一個元素對集合A中所有元素有一個嚴格的偏好排序,其實質就是根據(jù)制定的原則,對集合A發(fā)出的偏好排序依次進行接受和拒絕的判定。3.2多個班級同時申請、不同預排名單、各因子單的班級匹配所有教學班由任課教師向教學管理單位提交教學預期安排的申請,即把教學班集合A對集合B中所有元素的偏好排序提供給教學管理者,然后由教學管理者進行如下的匹配進行教學班課表的安排。第一輪,教學管理者按所有教學班任課教師提供的第一偏好與時空集合B中元素進行匹配安排,若集合B中某元素只有一個教學班申請,則該教學班可暫被接受,記入預排名單;若B中某元素若有多個教學班同時申請,則教學管理者從這些申請的教學班中留下B中該元素偏好排序上最好的教學班,其他的教學班都被拒絕,進入下一輪申請,被留下的教學班記入預排名單。第二輪,教學管理者按沒有進入預排名單(被拒絕)的教學班任課教師提供的、還沒有被時空集合中元素拒絕過的最偏好申請與時空集合B中元素進行匹配安排,比較集合B中每一時空元素所有本輪申請的教學班和上一輪留在預排名單上的教學班,從中留下最偏好的教學班,拒絕其他教學班,被拒絕的教學班進入下一輪申請,留下的教學班記入預排名單。第K輪,教學管理者按所有在上一輪被拒絕的教學班向他可接受并且沒有拒絕過他的時空元素中最偏好的元素提出的申請比較集合B中每一時空元素所有本輪申請的教學班和上一輪留在預排名單上的教學班,從中留下最偏好的教學班,拒絕其他教學班,被拒絕的教學班進入下一輪申請,留下的教學班記入預排名單。當沒有教學班的申請?zhí)岢龌虮痪芙^的時候,這個匹配程序停止。由于教學班和時空元素的數(shù)目有限,并且往往時空元素的個數(shù)一般均大于教學班的數(shù)量(否則無法招生辦學),這個過程一定會在有限步后停止,所有留在預排名單上的教學班就被教學管理者正式排入課表。3.3基于時空元素的學習過程設計在排課自動雙向匹配實際執(zhí)行中,主要是確定教師提交時間教室偏好集合A與學校時空元素集合B特殊偏好排序設置策略、排課結果的合理化及人性化和自動雙向匹配處理過程的設計實現(xiàn)。3.3.1基于分析的排課篩選(1)教師時空偏好元素集合A是由每個教學班的任課教師自己提交的偏好時間及教室偏好排序的組合構成。(2)學校時空元素特殊偏好集合B主要解決集合A在出現(xiàn)多個課程教學班對同一個時空元素提出申請時,如何建立接受或拒接申請的判斷依據(jù),以保證排課應遵循的完備性、正確性、合理性及人性化等原則問題。在實際設計中采用對教師、課程、班級、教學班等分配唯一的編號,同時將任課教師的職稱高低、年齡大小、申請時間先后等因素先后順序進行權重的設置,各項加權指標求和后,數(shù)值最大的優(yōu)先匹配,這樣保證同教學時段均不重復出現(xiàn)即可避免沖突,保證排課的正確性。3.3.2接受或拒絕課堂教學偏好申請原則(1)以任課教師自己提出排課期望進行匹配,體現(xiàn)了對任課教師專業(yè)素養(yǎng)的認可以及給其較大的自主選擇權;(2)教學管理者在設定接受或拒絕教學班偏好申請原則時,充分考慮教室容量、課程性質,以及任課教師的職稱高低、年齡大小、申請時間先后等因素,并設定這些因素的先后順序;(3)對學生排課的滿意度及選課的沖突問題,由任課教師對課程、教學的專業(yè)認識提出的排課偏好,以及教學管理者對課程性質等的排課剛性要求,另外可排好課表,再由學生自主選課填充教學班人數(shù)的辦法等措施來解決。3.3.3計算過程中雙方的特定一致性的描述我們將教師時空元素集合A和學校時空元素特殊偏好排序集合B進行符號化設定,自動排課匹配機制執(zhí)行過程符號描述如圖1所示。3.4實驗結果和匹配結果埃爾文.羅斯(1982)證明,一般來說,不存在對所有參與人都激勵相容的穩(wěn)定匹配機制,所有的偏好操縱,只要是非劣納什均衡的,那么它都是一個穩(wěn)定的匹配結果。本文設計的排課匹配策略排好排序符合非劣納什均衡,實際匹配過程只需對每一輪次申請匹配同一時空元素的教學班進行篩選即可。因為排課雙向匹配任何一個集合A中個體ai,如果它發(fā)現(xiàn)集合B中個體bj比它現(xiàn)在的匹配更好的話,那么這個個體bj一定曾經(jīng)拒絕過他,也意味著在該個體bj看來A中有個體aj的比ai更好。這意味著即使再給他一次匹配機會,他還是會被拒絕,所以整個排課匹配過程策略能夠實現(xiàn)穩(wěn)定匹配。4愿景的匹配匹配博弈理論