胡勇文，陳國華，劉 靜

（1.湖北文理學院 機械工程學院；2.純電動汽車動力系統(tǒng)設計與測試湖北省重點實驗室，湖北 襄陽 441053）

0 引言

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

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

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

1 最短時限指派問題及其最小費用流模型

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

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

圖1最短時限指派問題的最小費用流模型

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

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

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

2 最小費用流模型的允許邊算法

設經(jīng)典指派問題對應的最小費用流問題的數(shù)學模型為：

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

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

由于pi無約束，故可任意指定一組pi，并取：

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

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

pi=0,??i∈N；xij=0,?（i,j）∈A；給源點 s標號 （0,

第一步：①?i∈S，

取：

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

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

第三步：①對i∈S，如 （i,j）∈R，j∈Sˉ，且xij＜uij，則給j標號 （i,δj），其中；如（j,i）∈R，j∈Sˉ，且xij＞0 ，則給j標號 （-i,δj），其中δj=

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

③增廣流量

則流量變?yōu)椋害浴?υ′+δt。如υ′=n，則已得到流量為n的最小費用流，算法結束；否則，保留源點s的標號，刪除其余所有標號，轉第三步①。

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

3 STL-A問題的允許邊算法

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

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

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

實際上，T2對應在效率矩陣[cij]中值為T2的元素。此時在當前最小費用流網(wǎng)絡中令：

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

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

①按式（18）至式（20）計算T1。在對應的最小費用流模型中只保留cij≤T1的邊。

②pi=0,?i∈N;xij=0,?（i,j）∈A；給源點s標號 （0,+∞）；點S={s}∪M,Sˉ=N∪{t}。

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

第一步：①?i∈S，

取：

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

②并令：

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

第三步：①對i∈S，如 （i,j）∈R，j∈Sˉ，且xij＜uij，則給j標號 （i,δj），其中；如（j,i）∈R，j∈Sˉ，且xij＞0 ，則給 j標號 （-i,δj），其中

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

③增廣流量

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

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

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

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

4 算例

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

表1 不同工人檢修故障處所需時間表

該問題屬于典型的最短時限指派問題，利用本文給出算法求解過程如下：

初始化：

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

圖2初始化后的最小費用流模型

第一步：計算勢θ，此時θ=min{15,18,18,17,16,17}=15。

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

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

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

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

圖5更新T1后的最小費用流網(wǎng)絡

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

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

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

5 結束語

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