楊帆++李慧++胡又農(nóng)

摘 要 在實(shí)際教學(xué)中，任務(wù)指派問題是一個(gè)綜合考慮教師特長、學(xué)生滿意度、教師教學(xué)精力等多因素的決策問題。應(yīng)用匈牙利算法建立指派模型，求解復(fù)雜因素下的教學(xué)任務(wù)指派問題，定量、精準(zhǔn)地將恰當(dāng)?shù)慕虒W(xué)任務(wù)分配給適當(dāng)?shù)慕處?，以使系統(tǒng)總體滿意度最大化。該指派優(yōu)化模型的建立，使得任務(wù)分配更加客觀和明確。

關(guān)鍵詞 匈牙利算法；教學(xué)任務(wù)；任務(wù)指派問題；MATLAB

中圖分類號(hào)：G642 文獻(xiàn)標(biāo)識(shí)碼：B

文章編號(hào)：1671-489X（2017）14-0012-03

Hungarian Algorithm for Teaching Task Assignment Problem//YANG Fan， LI Hui， HU Younong

Abstract In a practical teaching， the task assignment problem is a

decision-making problem which considers teachers specialty， stu-dents satisfaction， teachers teaching energy and so on. In this paper，

in order to maximize the overall satisfaction of the system， the assign-

ment model is established by using the Hungarian algorithm to solve the task assignment problems in complex conditions， by assigning appropriate teaching tasks to appropriate teachers quantitatively and

accurately. The assignment optimization model makes task assign-ments more objective and clear.

Key words Hungarian Algorithm； teaching task； task assignment problem； MATLAB

1 前言

隨著教學(xué)內(nèi)容的擴(kuò)展，各類前沿技術(shù)在課堂中得到充分體現(xiàn)，教學(xué)課程的設(shè)置、教學(xué)任務(wù)的分配等問題也變得更加復(fù)雜。傳統(tǒng)的教學(xué)任務(wù)指派，主要是根據(jù)任務(wù)之間的關(guān)系、教師的授課情況和學(xué)生的偏好，由專門的教學(xué)管理人員制定課程表，費(fèi)時(shí)、費(fèi)力且效率低，屬于典型的經(jīng)驗(yàn)型管理。隨著教學(xué)管理信息化含量的日益提升，定性的人工進(jìn)行教學(xué)任務(wù)指派的情況已無法適應(yīng)定量、快速、自動(dòng)的科學(xué)管理要求。因此，有必要引入運(yùn)籌學(xué)的理論和方法解決教學(xué)任務(wù)指派問題，并以計(jì)算機(jī)輔助解決實(shí)際問題。

本文基于匈牙利算法，建立教學(xué)任務(wù)指派優(yōu)化模型，分析如何分配教師承擔(dān)教學(xué)任務(wù)以使系統(tǒng)整體滿意度最大化，并采用MATLAB編程實(shí)現(xiàn)求解。

2 指派問題

指派問題的常用描述是有n個(gè)人可承擔(dān)m項(xiàng)任務(wù)，由于每人的專長不同，完成不同任務(wù)的效率也不同，如何指派哪個(gè)人完成哪項(xiàng)任務(wù)，使完成所有任務(wù)的總效率最高或所需總時(shí)間最少？指派問題是運(yùn)輸問題中的一種特殊情況，“派合適的人去做合適的事”是對(duì)該問題的最貼切描述。

指派問題的數(shù)學(xué)模型通常是：設(shè)n個(gè)人（或機(jī)器）被分配去做m件工作，由于工作性質(zhì)和各人（或機(jī)器）的專長不同，完成不同工作的效益（時(shí)間、成本、收益等）將有差別，用系數(shù)矩陣C表示，Cij表示第i個(gè)人完成第j件工作的效益，Cij≥0（i=1，...，n；j=1，...，m）。當(dāng)n=m時(shí)，為平衡狀態(tài)下的標(biāo)準(zhǔn)指派問題；當(dāng)n>m時(shí)，人數(shù)多于任務(wù)數(shù)，屬于不平衡狀態(tài)下?lián)駜?yōu)錄用問題；當(dāng)n

使得總效益最高（時(shí)間最少、成本最小、收益最大等），即目標(biāo)函數(shù)。當(dāng)且時(shí)，為一對(duì)一指派問題；否則為多人協(xié)作或兼職問題。

求解指派問題的方法通常有分支定界法、隱枚舉法、匈牙利法等[1]。匈牙利算法由匈牙利數(shù)學(xué)家Edmonds于1965年提出，是基于Hall定理中充分性證明的思想，用增廣路徑求二分圖最大匹配的算法，算法的核心是尋找增廣路徑，也可用于指派問題的求解[2]。

針對(duì)多人執(zhí)行多項(xiàng)工作的指派問題，張?jiān)迫A采用匈牙利算法的基本思想和步驟進(jìn)行了研究[3]。目標(biāo)分配問題作為指派問題的一種類型，谷穩(wěn)綜合匈牙利算法及其進(jìn)化算法的特點(diǎn)，對(duì)機(jī)器人足球的目標(biāo)分配問題進(jìn)行了研究[4]。為避免匈牙利算法多次試分配導(dǎo)致處理速度慢的不足，周莉等人對(duì)尋找獨(dú)立零的次序進(jìn)行改進(jìn)，得到匈牙利算法求解指派問題的一次性分配算法[5]。李延鵬等人提出利用虛擬工作代替并聯(lián)環(huán)境，將具有并聯(lián)環(huán)節(jié)的人員指派問題轉(zhuǎn)化為典型的指派問題，提高了匈牙利算法的適用性[6]。謝博耶夫采用反圈法和對(duì)稱差，對(duì)匈牙利算法進(jìn)行了推廣[7]。對(duì)于“人少任務(wù)多”型指派問題的解決，與“加邊補(bǔ)零”法、“加邊補(bǔ)最小值”法等傳統(tǒng)解法不同，馬曉娜通過差額法對(duì)匈牙利算法進(jìn)行了改進(jìn)[8]。

3 基于匈牙利算法的任務(wù)指派優(yōu)化模型

問題描述 教學(xué)課程的指派優(yōu)化問題，需要綜合考慮教師教學(xué)特長、學(xué)生滿意度、課程內(nèi)容等多因素，追求教學(xué)質(zhì)量、滿意度和教師教學(xué)精力等多目標(biāo)的優(yōu)化決策問題，任何一個(gè)參數(shù)的改變都可能影響最終的指派結(jié)果。該類問題可描述為：

假設(shè)有n名不同教研室的教師，N={N1，N2，...，Nn}，所有教師可以講授課程共m門，M={M1，M2，...，Mm}。已知n名教師對(duì)m門課程的擅長程度矩陣G、n名教師的課時(shí)上限序列U和學(xué)員對(duì)教師滿意度序列S，如何安排n名教師教授的課程，使得總體教學(xué)質(zhì)量、教師精力和學(xué)生滿意度最優(yōu)化？

指派優(yōu)化模型 由于該問題涉及因素較多，因此，采用解析方法或傳統(tǒng)的匈牙利算法難以給出合適結(jié)果?？傮w最優(yōu)化的前提是教師擅長課程、精力和學(xué)生滿意度滿足基本要求，本文采用比值的方式求解三種因素的綜合表現(xiàn)。矩陣G元素值為百分比，Gij值越高，表明第i名教師對(duì)第j門課程的擅長程度越好。序列U和S經(jīng)過歸一化處理后，也可表現(xiàn)為百分比形式，Ui值越高，表明第i名教師的教學(xué)任務(wù)越飽滿；Si值越高，表明學(xué)生對(duì)第i名教師的滿意度越高。以Tij表現(xiàn)三種因素綜合影響下第i名教師教授第j門課程的情況。Tij值與Gij、Si呈現(xiàn)正相關(guān)關(guān)系，而與Ui呈現(xiàn)負(fù)相關(guān)關(guān)系，計(jì)算得到：

末位淘汰制是當(dāng)前高校教師競爭較為常用的制度[9]，對(duì)所有教師求解Tij，對(duì)Tij按值由高到低排序PT，根據(jù)T進(jìn)行課程指派前的初始末位淘汰。因此，模型的目標(biāo)方程為：

約束條件如下：

1）n為能夠完成教學(xué)任務(wù)的教師數(shù)量，m為需要完成的教學(xué)課程數(shù)量，i表示教師，j表示教學(xué)課程；

2）教師擅長教學(xué)課程的程度矩陣G，其值由教學(xué)專

家、往屆學(xué)生成績和教師自身資歷確定，其值越高，表明越擅長；

3）教學(xué)課時(shí)飽滿程度序列U，由教師所承擔(dān)的教學(xué)任務(wù)、科研任務(wù)、外出授課學(xué)習(xí)和自身情況確定，其值越高，表明教師課程任務(wù)越重；

4）學(xué)生滿意度序列S，由往屆學(xué)生評(píng)價(jià)、本屆學(xué)生評(píng)價(jià)綜合確定，其值越高，表明教師講授課程的受歡迎程度越高；

5）矩陣為修正后的擅長矩陣，依據(jù)G、U和S求解T，采用末位淘汰制修正G后成為。

模型求解

1）構(gòu)建平衡的矩陣G。求解平衡問題是匈牙利算法的特長，當(dāng)教師數(shù)量和教學(xué)課程數(shù)量不相等時(shí)，需要增添虛擬的教師或課程，重新構(gòu)建平衡的矩陣G。具體方法如下：

①若n>m，一門教學(xué)課程可能由多個(gè)教師講授，屬于不平衡狀態(tài)下?lián)駜?yōu)錄用問題，可虛擬n-m門課程，構(gòu)建新的平衡矩陣G={Gn×m∣Gn×（n-m）}。

②若n

③若n=m，屬于平衡狀態(tài)下的標(biāo)準(zhǔn)指派問題，直接由匈牙利算法求解。

構(gòu)建結(jié)束后，由求解最大值轉(zhuǎn)為求解最小值，將目標(biāo)函數(shù)轉(zhuǎn)為標(biāo)準(zhǔn)的目標(biāo)函數(shù)。即求，令

，則與有相同的最優(yōu)解。

2）處理擅長矩陣、飽滿序列和滿意度序列。如果某教師Ni無法講授某項(xiàng)課程Mj，則將擅長矩陣G對(duì)應(yīng)元素Gij的值設(shè)定為0。對(duì)滿意度序列S進(jìn)行歸一化處理：

對(duì)課程飽滿程度序列U進(jìn)行歸一化處理：

3）修正擅長矩陣G。根據(jù)處理后的擅長矩陣、飽滿序列和滿意度序列，求解T進(jìn)行末位淘汰。將所有Tij值按由高到低的順序進(jìn)行排序，設(shè)定合理的淘汰比例p，對(duì)于排名低于p的，取消該教師講授相應(yīng)課程的安排，即當(dāng)PT（Tij）≤p時(shí)，Gij=0，修正形成矩陣G′。

4 實(shí)例分析

某高校計(jì)劃開設(shè)創(chuàng)客空間，需要開展的教學(xué)任務(wù)有焊接、車工、鉗銑磨工、數(shù)控、3D打印、切割?，F(xiàn)有8名教師可承擔(dān)相關(guān)課程教學(xué)，教師對(duì)教學(xué)課程的擅長矩陣G見表1。根據(jù)教師自身安排、專家組打分和課時(shí)等分析，得到教師教學(xué)任務(wù)的飽滿程度序列U，見表2。通過問卷調(diào)查、往屆課程成績、學(xué)生座談等形式，得到學(xué)生對(duì)教師的滿意度序列S，見表3。根據(jù)學(xué)校本學(xué)期末位淘汰安排，執(zhí)行p=15%的末位淘汰率。計(jì)算T并進(jìn)行排序，如表4所示，得到綜合排名靠后的教師課程為（A2-車工）、（A2-鉗銑磨工）、

（A3-數(shù)控）、（A4-車工）、（A6-3D打?。┖停ˋ7-焊接），將其執(zhí)行末位淘汰改進(jìn)矩陣G′。

隨后采用匈牙利算法進(jìn)行最優(yōu)化指派，使用MATLAB進(jìn)行編程求解，得到教師A2和A7不參與該項(xiàng)教學(xué)任務(wù)，其他的如表5所示。

5 結(jié)論

在傳統(tǒng)教學(xué)任務(wù)指派中，需考慮教師擅長度和教學(xué)任務(wù)飽滿程度、學(xué)生滿意度等諸多問題，采用一般經(jīng)驗(yàn)進(jìn)行定性的任務(wù)指派費(fèi)時(shí)、費(fèi)力、效率低。而采用定量分析和計(jì)算機(jī)輔助解決實(shí)際問題，使得結(jié)論客觀而可靠。本文從實(shí)際教學(xué)出發(fā)，以教學(xué)任務(wù)指派問題建立模型，應(yīng)用匈牙利算法實(shí)現(xiàn)總滿意度最高的求解，使得任務(wù)分配更加客觀和明確，具備可操作性和可重復(fù)性，為教育任務(wù)分配提供科學(xué)依據(jù)。

參考文獻(xiàn)

[1]胡運(yùn)權(quán)，郭耀煌.運(yùn)籌學(xué)教程[M].4版.北京：清華大學(xué)出版社，2012.

[2]傅家良.運(yùn)籌學(xué)方法與模型[M].上海：復(fù)旦大學(xué)出版社，2006.

[3]張?jiān)迫A.論匈牙利算法在指派問題管理工作中的應(yīng)用[J].價(jià)值工程，2016（25）：214-215.

[4]谷穩(wěn).基于進(jìn)化匈牙利算法的目標(biāo)分配問題研究及應(yīng)用[D].西安：西安電子科技大學(xué)，2013.

[5]周莉，張維華，徐射雕.求解指派問題的一次性分配算法[J].計(jì)算機(jī)工程與應(yīng)用，2011（18）：135-138，152.

[6]李廷鵬，錢彥嶺，李岳.基于改進(jìn)匈牙利算法的多技能人員調(diào)度方法[J].國防科技大學(xué)學(xué)報(bào)，2016（2）：144-149.

[7]謝博耶夫.匈牙利算法及其推廣[D].上海：華東師范大學(xué)，2016.

[8]馬曉娜.“人少任務(wù)多”型指派問題的一種新算法[J].重慶工商大學(xué)學(xué)報(bào)：自然科學(xué)版，2014（12）：68-71，75.

[9]姚維.如何看待高校實(shí)行“末位淘汰制”[J].亞太教育，

2016（22）：201，189.