最短時(shí)限指派問(wèn)題的新決策方法

胡勇文，陳國(guó)華，劉 靜

（1.湖北文理學(xué)院 機(jī)械工程學(xué)院；2.純電動(dòng)汽車動(dòng)力系統(tǒng)設(shè)計(jì)與測(cè)試湖北省重點(diǎn)實(shí)驗(yàn)室，湖北 襄陽(yáng) 441053）

0 引言

經(jīng)典指派問(wèn)題是運(yùn)籌學(xué)中一個(gè)重要的組合優(yōu)化問(wèn)題，它在人員和運(yùn)輸調(diào)度、柔性制造系統(tǒng)中有廣泛應(yīng)用。該問(wèn)題可描述為：n人要完成n項(xiàng)任務(wù)，由于每個(gè)人的專長(zhǎng)不同，因此每個(gè)人完成各項(xiàng)任務(wù)的時(shí)間也不相同，問(wèn)如何指派使得完成n項(xiàng)任務(wù)的總時(shí)間最少。實(shí)際生活中，n項(xiàng)任務(wù)通常同時(shí)開(kāi)工，不但要求完成n項(xiàng)任務(wù)的總時(shí)間最少，還需要在最短時(shí)間內(nèi)完成所有任務(wù)，即用時(shí)最多者達(dá)到最小。例如，手術(shù)室搶救病人過(guò)程中醫(yī)護(hù)人員調(diào)度問(wèn)題、救災(zāi)物資等調(diào)運(yùn)問(wèn)題、突發(fā)事故的搶修等問(wèn)題均需要在最短時(shí)間內(nèi)完成所有任務(wù)。一般將需要在最短時(shí)間內(nèi)完成所有任務(wù)且總完成時(shí)間最少的指派問(wèn)題稱為最短時(shí)限指派問(wèn)題，由于該類問(wèn)題多數(shù)情況下符合實(shí)際需要，因此研究最短時(shí)限指派問(wèn)題的決策方法具有重要意義。

最短時(shí)限問(wèn)題首先由Gross[1]提出，并給出了改進(jìn)圈的算法。此后，Garfinkel[2]借助求解最大流思想提出了一種求解最短時(shí)限指派問(wèn)題的閥門算法，但該算法很難檢驗(yàn)給出解的最優(yōu)性。我國(guó)也有眾多學(xué)者對(duì)最短時(shí)限指派問(wèn)題進(jìn)行了深入研究，求解最短時(shí)限指派問(wèn)題的主要算法有：大M法[3]、逐步尋優(yōu)算法[4]、生長(zhǎng)樹(shù)法及標(biāo)號(hào)法[5]、借助二分圖匹配思想的方法[6]、最短時(shí)限逼近法[7]及基于最小調(diào)整法思想的方法[8,9]，其中文獻(xiàn)[8,9]是較有代表性的方法。文獻(xiàn)[9]是建立在匈牙利算法上的求解最短時(shí)限指派問(wèn)題的算法，它需要通過(guò)變換矩陣，試指派，畫最少零元素覆蓋線等步驟，過(guò)程較復(fù)雜，也不利于計(jì)算機(jī)求解。文獻(xiàn)[8]中方法對(duì)獨(dú)立畫圈元素沒(méi)有預(yù)見(jiàn)性，仍需對(duì)問(wèn)題先進(jìn)行試指派，若試指派不滿足行平衡及列平衡，需要進(jìn)行修正步驟，且當(dāng)問(wèn)題的規(guī)模增大時(shí)，所需步驟較多，不利于計(jì)算機(jī)求解。

由于經(jīng)典指派問(wèn)題是特殊的最小費(fèi)用流問(wèn)題[10]，熊德國(guó)等[11]提出了求解最小費(fèi)用流的允許邊算法，且該算法在求解稠密網(wǎng)絡(luò)時(shí)具有良好性能[12]。鑒于最短時(shí)限指派問(wèn)題的特殊性，本文通過(guò)計(jì)算確定最短時(shí)限值，構(gòu)造最短時(shí)限指派問(wèn)題的最小費(fèi)用流模型，通過(guò)求解最小費(fèi)用流模型的最優(yōu)解而得到最短時(shí)限指派問(wèn)題的最優(yōu)解。

1 最短時(shí)限指派問(wèn)題及其最小費(fèi)用流模型

最短時(shí)限指派問(wèn)題（Shortest Time Limited Assignment Problem,STL-A）的一般提法如下：假定n個(gè)人要完成n項(xiàng)任務(wù)，由于個(gè)人專長(zhǎng)各異，不同人完成各任務(wù)所需的時(shí)間也不同。設(shè)指派第i個(gè)人去完成第 j項(xiàng)任務(wù)所需的時(shí)間為cij，所有任務(wù)均可同時(shí)開(kāi)工，確定一個(gè)指派方案，使得在最短時(shí)間內(nèi)完成所有任務(wù)，且所花時(shí)間和最少。令xij=0或1，當(dāng)xij=1時(shí)表示指派第i人去完成第 j項(xiàng)任務(wù)，否則xij=0。則STL-A問(wèn)題的數(shù)學(xué)模型如下：

最短時(shí)限的指派問(wèn)題需先滿足目標(biāo)函數(shù)（1），即在目標(biāo)函數(shù)（1）達(dá)到最優(yōu)解的前提下，再使目標(biāo)函數(shù)（2）達(dá)到最優(yōu)。傳統(tǒng)指派問(wèn)題可建立如下形式的最小費(fèi)用流模型（見(jiàn)圖1）。

圖1最短時(shí)限指派問(wèn)題的最小費(fèi)用流模型

其中集合M={1,2,…,n}表示n個(gè)人的集合，集合N={1′,2′,…,n′}表示n項(xiàng)任務(wù)的集合。此兩組節(jié)點(diǎn)之間的邊表示某人可以承擔(dān)某項(xiàng)工作的對(duì)應(yīng)關(guān)系，對(duì)?i∈M,j∈N，邊 （i,j）上單位流量費(fèi)用cij對(duì)應(yīng)STL-A問(wèn)題中效率矩陣中元素cij，規(guī)定邊（i,j）的容量uij=1，表示一人最多只能完成一項(xiàng)任務(wù)。對(duì)?i∈M，規(guī)定csi=0,usi=1，表示一人最多完成一項(xiàng)任務(wù)；對(duì)?i∈N，規(guī)定cjt=0,ujt=1，表示一項(xiàng)任務(wù)只能由一人完成。根據(jù)構(gòu)造的傳統(tǒng)指派問(wèn)題的最小費(fèi)用流模型有：傳統(tǒng)指派問(wèn)題等價(jià)于在圖1中尋求從s至t的流量值為n的最小費(fèi)用流。

假定問(wèn)題STL-A的最優(yōu)解為c*=minmax{cij|xij=1,i,j=1,2,…,n}，則c*必為指派問(wèn)題效率矩陣中的某一元素。此時(shí)最短時(shí)限指派問(wèn)題STL-A可轉(zhuǎn)化為以下單目標(biāo)規(guī)劃模型A：

因此只要能確定c*，STL-A問(wèn)題即可轉(zhuǎn)化為經(jīng)典指派問(wèn)題。設(shè)cij為最短時(shí)限指派問(wèn)題效率矩陣[cij]中第i行，第j列元素，i,j=1,2,…,n。若cij＞c*，則傳統(tǒng)指派問(wèn)題的最小費(fèi)用流模型中可令節(jié)點(diǎn)i到節(jié)點(diǎn)j的單位流量的費(fèi)用為M，M為一無(wú)窮大的正數(shù)，表示在最短時(shí)限指派問(wèn)題中，不能指派第i人完成第j項(xiàng)任務(wù)，否則STL-A問(wèn)題的最優(yōu)解大于c*。若cij≤c*，則在傳統(tǒng)指派問(wèn)題的最小費(fèi)用流模型中節(jié)點(diǎn)i到節(jié)點(diǎn)j的單位流量的費(fèi)用為cij。這樣便得到STL-A的最小費(fèi)用流模型。后文將介紹尋求STL-A問(wèn)題的最優(yōu)解c*的方法。

2 最小費(fèi)用流模型的允許邊算法

設(shè)經(jīng)典指派問(wèn)題對(duì)應(yīng)的最小費(fèi)用流問(wèn)題的數(shù)學(xué)模型為：

為方便討論，設(shè)所求的最小費(fèi)用流問(wèn)題對(duì)應(yīng)的網(wǎng)絡(luò)記為G=（N,A,U,C），其中N為節(jié)點(diǎn)集合，A為邊集合，U為各邊的容量集合,C為各邊單位流量費(fèi)用集合。則模型（11）對(duì)應(yīng)的對(duì)偶問(wèn)題為：

其中A為對(duì)應(yīng)最小費(fèi)用流網(wǎng)絡(luò)中的邊的集合，pi為對(duì)應(yīng)節(jié)點(diǎn)i的對(duì)偶變量，pij為對(duì)應(yīng)于邊（i,j）的對(duì)偶變量，分別稱為節(jié)點(diǎn)i及邊（i,j）的勢(shì)。設(shè)x={xij},p={pi,pij}分別為L(zhǎng)P及DP的一組可行解，根據(jù)對(duì)偶理論的互補(bǔ)松弛定理，他們是最優(yōu)解，當(dāng)且僅當(dāng)滿足：

由于pi無(wú)約束，故可任意指定一組pi，并?。?/p>

則必有pij≤0，于是便得到DP的一個(gè)可行解。則式（13）可等價(jià)的寫成：

最小費(fèi)用流的允許邊算法的基本思想為：從一個(gè)費(fèi)用最小可行流（比如0流）開(kāi)始，對(duì)其流量增廣，在增廣過(guò)程中始終滿足條件式（15），便可得到一個(gè)流量更大的最小費(fèi)用流，即在增廣流量時(shí)，只有滿足pi-pj=cij的邊（i,j）上的流才允許調(diào)整。把滿足pi-pj=cij的邊（i,j）稱為允許邊，由允許邊組成的網(wǎng)絡(luò)稱為允許網(wǎng)絡(luò)，記為R。當(dāng)允許網(wǎng)絡(luò)中找不到可增廣鏈且流量尚未達(dá)到原網(wǎng)絡(luò)的最大流時(shí)，修改有關(guān)節(jié)點(diǎn)的勢(shì)，以增加新的允許邊構(gòu)造新的允許網(wǎng)絡(luò)，重新尋找允許網(wǎng)絡(luò)中的可增廣鏈，直到求得目標(biāo)流。則求解指派問(wèn)題的算法可描述為：

pi=0,??i∈N；xij=0,?（i,j）∈A；給源點(diǎn) s標(biāo)號(hào) （0,

第一步：①?i∈S，

?。?/p>

轉(zhuǎn)②；否則，如不能確定θ，則當(dāng)前流已為原網(wǎng)絡(luò)的最大流，算法結(jié)束。

第二步：如果pi-pj=cij，則 （i,j）∈R；

第三步：①對(duì)i∈S，如 （i,j）∈R，j∈Sˉ，且xij＜uij，則給j標(biāo)號(hào) （i,δj），其中；如（j,i）∈R，j∈Sˉ，且xij＞0 ，則給j標(biāo)號(hào) （-i,δj），其中δj=

②如t?S，此時(shí)，允許網(wǎng)絡(luò)中達(dá)到最大流，轉(zhuǎn)第一步；否則,如t∈S，則得到R中的一條可增廣鏈μ，轉(zhuǎn)③；

③增廣流量

則流量變?yōu)椋害浴?υ′+δt。如υ′=n，則已得到流量為n的最小費(fèi)用流，算法結(jié)束；否則，保留源點(diǎn)s的標(biāo)號(hào)，刪除其余所有標(biāo)號(hào)，轉(zhuǎn)第三步①。

當(dāng)最小費(fèi)用流網(wǎng)絡(luò)中未達(dá)到最大流，該算法通過(guò)增加及節(jié)點(diǎn)的勢(shì)后總可以找到至少一條允許邊，因此經(jīng)過(guò)有限次數(shù)改變節(jié)點(diǎn)勢(shì)后，必可找到一條從s至t的增廣鏈。由于算法是在允許邊上增廣流量，暫且將此算法稱作允許邊算法。

3 STL-A問(wèn)題的允許邊算法

根據(jù)問(wèn)題STL-A及A的關(guān)系，用最小費(fèi)用流的允許邊算法求解STL-A問(wèn)題的基本思想為：先找出每行及每列元素中最小元素的最大者作為初始備選最優(yōu)解，并在最小費(fèi)用流網(wǎng)絡(luò)中只保留效率矩陣中元素不大于初始最優(yōu)解對(duì)應(yīng)的邊，并利用允許邊算法尋求當(dāng)前網(wǎng)絡(luò)中的最小費(fèi)用流，判斷流量是否達(dá)到給定值。若流量未達(dá)到最優(yōu)值，則以增值最小原則調(diào)整當(dāng)前備選最優(yōu)解，重復(fù)以上過(guò)程，直到在最小費(fèi)用流網(wǎng)絡(luò)中找到流量值為n的最小費(fèi)用流，此時(shí)邊xij=1,i=∈M,j∈N即為指派第i人完成第j項(xiàng)任務(wù)。

為尋求STL-A問(wèn)題的最優(yōu)解c*，令：

現(xiàn)考慮效率矩陣[cij]中位于不同行元素集C1={ci′j,i′=1,2,…,n} ，以及位于不同列的元素集C2={cij′,j′=1,2,…,n}。顯然，對(duì)ci1j1,ci2j2∈C1，若有j1≠j2,?i1,j1,i2,j2=1,2,…,n。則已找到STL-A問(wèn)題的最優(yōu)解，且xi′j=1 若ci′j∈C1；xi′j=0 ，若ci′j?C1；同樣，對(duì)ci3j3,ci4j4∈C2，有則已找到 STL-A 問(wèn)題的最優(yōu)解，且，若，若cij′?C2。若不存在每行（列）中的最小元素位于不同列（行），即當(dāng)前不存在STL-A的最優(yōu)解。按照增值最小原則調(diào)整當(dāng)前備選最優(yōu)解，令：

實(shí)際上，T2對(duì)應(yīng)在效率矩陣[cij]中值為T2的元素。此時(shí)在當(dāng)前最小費(fèi)用流網(wǎng)絡(luò)中令：

其中，M為一無(wú)窮大的正數(shù)。

用允許邊算法求解STL-A問(wèn)題的具體步驟如下：初始化：

①按式（18）至式（20）計(jì)算T1。在對(duì)應(yīng)的最小費(fèi)用流模型中只保留cij≤T1的邊。

②pi=0,?i∈N;xij=0,?（i,j）∈A；給源點(diǎn)s標(biāo)號(hào) （0,+∞）；點(diǎn)S={s}∪M,Sˉ=N∪{t}。

此時(shí)流量υ′=0 。記割 [S,Sˉ]的前向邊集為 （S,Sˉ），后向邊集 （Sˉ,S）：

第一步：①?i∈S，

?。?/p>

轉(zhuǎn)②；否則，如不能確定θ，則當(dāng)前流已為原網(wǎng)絡(luò)的最大流，即已找到STL-A問(wèn)題的最優(yōu)解，算法結(jié)束。

②并令：

第二步：如果pi-pj=cij，則 （i,j）∈R；

第三步：①對(duì)i∈S，如 （i,j）∈R，j∈Sˉ，且xij＜uij，則給j標(biāo)號(hào) （i,δj），其中；如（j,i）∈R，j∈Sˉ，且xij＞0 ，則給 j標(biāo)號(hào) （-i,δj），其中

②t?S，此時(shí)，允許網(wǎng)絡(luò)中達(dá)到最大流，轉(zhuǎn)STEP1；否則,如t∈S，則找到R中的可增廣鏈μ，轉(zhuǎn)第三步③；否則，若t?S，轉(zhuǎn)第一步①；

③增廣流量

則流量變?yōu)椋害浴?υ′+δt。如υ′=n，則已得到流量為n的最小費(fèi)用流，算法結(jié)束；否則，保留源點(diǎn)s的標(biāo)號(hào)，刪除其余所有標(biāo)號(hào)，令T1=T1+min{cij-T1|cij＞T1,i,j=1,2,…,n}，并在當(dāng)前最小費(fèi)用流網(wǎng)絡(luò)中增加值為T1的單位流量費(fèi)用所對(duì)應(yīng)的邊，轉(zhuǎn)第一步①。

根據(jù)以上算法描述，下面給出用允許邊算法求解STL-A問(wèn)題的正確性。

證明：對(duì)?j∈N，若xjt=1，則t不能取得與j直接相關(guān)的標(biāo)號(hào)；否則，由于cjt=0，若j能取得標(biāo)號(hào)的同時(shí)，t也能取得標(biāo)號(hào)，即找到一條從s至t的增廣鏈。此外，對(duì)?j∈N，若j能取得標(biāo)號(hào)時(shí)，且xij=1，i∈M，則節(jié)點(diǎn)i也能取得標(biāo)號(hào)。因此，第一次迭代后，至少找到一條增廣鏈，流量增加量至少為1；在第l次迭代時(shí)，由以上討論易知，通過(guò)更新T1的值，并在當(dāng)前網(wǎng)絡(luò)中加入對(duì)應(yīng)的邊后，最多經(jīng)修改l次節(jié)點(diǎn)的勢(shì)（l次迭代），便可尋求至少一條從s至t的增廣鏈，流量至少增加1。因此，最多經(jīng)1+2+…+n=（n2+n）/2次迭代后，即可得到流量值為n的最小費(fèi)用流的最優(yōu)解，此時(shí)節(jié)點(diǎn)s的勢(shì)（此時(shí)ps=T1）即為滿足時(shí)限最短要求的最優(yōu)解，而邊xij=1,i∈M,j∈N即為指派第i人完成第j項(xiàng)任務(wù)。

根據(jù)算法描述易知，本文的算法還適用于人數(shù)與任務(wù)數(shù)不相等、每人只能做一件事的最短時(shí)限指派問(wèn)題，只需求解給定流量（流量值即為人數(shù)或任務(wù)數(shù)的值）下的最小費(fèi)用流問(wèn)題即可，且計(jì)算過(guò)程更為簡(jiǎn)單。針對(duì)一人可做多事或一事可由多人做的最短時(shí)限指派問(wèn)題，只需調(diào)整邊（s,i）,i∈M或邊 （j,t）,j∈N的容量即可。如，第i＃人可做兩件事，則設(shè)定邊 （s,i＃）的容量為2，同理，若第j?？杀粌扇俗觯瑒t設(shè)定邊 （j＃,i）的容量為2。

4 算例

例1：某供電系統(tǒng)中有4處供電故障，該供電系統(tǒng)只有在所有故障均排除后才能恢復(fù)供電，現(xiàn)要分配4名工人到4處供電故障處檢修。由于不同故障處所處條件以及各工人專長(zhǎng)不同，不同工人檢修不同的供電故障處的時(shí)間（單位：分）如表1。問(wèn)如何指派4名工人，使得該供電系統(tǒng)在最短時(shí)間能恢復(fù)的前提下，總共檢修時(shí)間最短。

表1 不同工人檢修故障處所需時(shí)間表

該問(wèn)題屬于典型的最短時(shí)限指派問(wèn)題，利用本文給出算法求解過(guò)程如下：

初始化：

按式（18）至式（20）計(jì)算T1，保留效率矩陣中元素值cij≤T1的元素，并建立對(duì)應(yīng)的最小費(fèi)用流模型，各邊上的數(shù)據(jù)表示（cij,uij,xij）。為使圖更加簡(jiǎn)潔，標(biāo)號(hào)過(guò)程省略。且若邊上流量為“0”，則該邊的數(shù)據(jù)表示為（cij,uij），如圖2。

圖2初始化后的最小費(fèi)用流模型

第一步：計(jì)算勢(shì)θ，此時(shí)θ=min{15,18,18,17,16,17}=15。

第二步：尋求允許網(wǎng)絡(luò)R中最大流。通過(guò)標(biāo)號(hào)可找到一條增廣鏈s→A→1→t，增廣流量后，網(wǎng)絡(luò)圖如圖3。由于此時(shí)流量值為1，未達(dá)到最大流量4，故仍需迭代。

圖3允許網(wǎng)絡(luò)R0上的最大流

第三步：經(jīng)過(guò)三次迭代后，網(wǎng)絡(luò)中的流量達(dá)到3，如圖4，此時(shí)已達(dá)到初始化后最小費(fèi)用流模型的最大流量，但未達(dá)到流量為4的最小費(fèi)用流。故需更新T1，按式（21）規(guī)則更新后T1=19。加入對(duì)應(yīng)邊后的網(wǎng)絡(luò)圖如圖5。

圖4允許網(wǎng)絡(luò)R上的最大流

圖5更新T1后的最小費(fèi)用流網(wǎng)絡(luò)

第四步：經(jīng)過(guò)兩次迭代后，找到一條s→B→1→A→2→t的增廣鏈，增廣后的流量為4，已達(dá)到最大流，如圖6。

圖6T1=19時(shí)的最小費(fèi)用最大流的最優(yōu)解

圖6中，網(wǎng)絡(luò)中流量為4，已達(dá)到最大流。至此，對(duì)應(yīng)表1中的指派問(wèn)題的最優(yōu)解為：工人A、B、C、D分別處理2、1、3、4處故障能使該供電系統(tǒng)在最短時(shí)間內(nèi)恢復(fù)供電，并且總維修時(shí)間最少，最少總時(shí)間為18+19+16+17=70min。

5 結(jié)束語(yǔ)

本文將具有最短時(shí)限的指派問(wèn)題轉(zhuǎn)化為最小費(fèi)用流模型，通過(guò)更新最短“時(shí)限”值而更新構(gòu)造的最小費(fèi)用流網(wǎng)絡(luò)。同時(shí)利用基于對(duì)偶原理的允許邊算法求解最短時(shí)限指派問(wèn)題的最小費(fèi)用流模型。與已有求解最短時(shí)限指派問(wèn)題的算法相比，本算法不需要將最短時(shí)限指派問(wèn)題通過(guò)矩陣反復(fù)變換轉(zhuǎn)化為經(jīng)典指派問(wèn)題進(jìn)行求解，而是通過(guò)計(jì)算最短時(shí)限值構(gòu)造最小費(fèi)用流網(wǎng)絡(luò)，直接通過(guò)改變節(jié)點(diǎn)的勢(shì)以擴(kuò)大允許網(wǎng)絡(luò)進(jìn)而在允許網(wǎng)絡(luò)中尋求最小費(fèi)用流網(wǎng)絡(luò)的最優(yōu)解。該算法在迭代過(guò)程中充分利用了上一次迭代的信息，迭代過(guò)程簡(jiǎn)單，計(jì)算量小，易于在計(jì)算機(jī)上實(shí)現(xiàn)。