馬芹芹，郭強，付曉薇

西北工業(yè)大學(xué)理學(xué)院，西安 710129

多階段雙層目標(biāo)分配問題的精確算法

馬芹芹，郭強，付曉薇

西北工業(yè)大學(xué)理學(xué)院，西安 710129

針對所有工作必須分階段依次完成，但同一個階段的工作可以同時進行的情況下，如何分配現(xiàn)有人員來承擔(dān)這些工作，才能使得完成所有工作的工期最短，并在此前提下使花費的總用時最少的分配問題，通過引入立方檢測矩陣，給出了一種單調(diào)下降的迭代算法。該算法不但能獲取精確最優(yōu)解，而且有很好的計算效率。

分配問題；雙層目標(biāo)；立方檢測矩陣；迭代算法；精確最優(yōu)解

1 引言

分配問題通常都與經(jīng)濟效益和社會效益密切相關(guān)，而且類型很多[1]。針對以總用時最少為目標(biāo)的分配問題，文獻[2-3]分別給出了求解一對一分配問題的匈牙利法[2]和矩陣迭代法[3]；文獻[4]給出了求解一對多確定型分配問題的算法；文獻[5]給出了求解一對多非確定型分配問題的矩陣迭代法。針對以工期最短為目標(biāo)的分配問題，文獻[6]給出了求解一對一分配問題的O.Gross算法；文獻[7]給出了求解一對多確定型分配問題的定界迭代算法；文獻[8]給出了求解一對多非確定型分配問題的字典式搜索法。然而，工期最短的分配方案通常并不唯一，因此，可以在獲取工期最短的前提下，進一步使總用時最少，其現(xiàn)實意義在于追求最高效率的前提下，最大限度地降低勞動強度。針對這類雙層目標(biāo)分配問題，文獻[9]中給出了工作間存在緊前、緊后關(guān)系的一對一分配問題的迭代算法；文獻[10]給出了求解一對多確定型分配問題的暫態(tài)混沌神經(jīng)網(wǎng)絡(luò)算法；文獻[11]給出了求解一對多非確定型調(diào)度問題的多項式時間算法。

上述文獻（文獻[9]除外）研究的都是所有工作同時進行的情況，然而現(xiàn)實中還存在一些多階段分配問題，即所有的n項工作必須分m(1＜m＜n)個階段依次完成，而同一階段的工作可以同時進行。該問題同樣在現(xiàn)實中有著重要的應(yīng)用背景。Punnen和Aneja[12]給出了求解以總用時和工期為目標(biāo)的一對一多階段分配問題的啟發(fā)式算法，獲取近似最優(yōu)解。Seshan[13]給出了求解以工期為目標(biāo)的一對一多階段分配問題的分枝定界算法，雖然能得到精確解，但計算量太大，效率不高。Sonia和Puri[14]給出了求解m=2時以工期最短為目標(biāo)的一對一多階段分配問題的多項式有界算法，但該算法不易推廣到2＜m＜n的情況。Aggarwal等人[15]給出了求解以工期最短為目標(biāo)的一對多確定型的多階段分配問題有效算法。目前關(guān)于該類問題的雙層目標(biāo)規(guī)劃的文獻還比較少。因此，本文主要針對一對一多階段雙層目標(biāo)分配問題進行研究，通過借鑒文獻[3]的算法思想，給出了可用于迭代運算獲取精確最優(yōu)解的立方檢測矩陣，由此形成的算法能保證工期隨迭代運算單調(diào)遞減或者工期不變，但總用時隨迭代運算單調(diào)遞減。

2 多階段雙層目標(biāo)分配問題的模型分析和相關(guān)定義

其中外層目標(biāo)函數(shù)式（1）是求在工期最短的前提下使總用時最少，內(nèi)層目標(biāo)函數(shù)式（2）是求工期最短，內(nèi)層規(guī)劃的約束條件式（3）表示每項工作只能由一個人承擔(dān)，約束條件式（4）表示每個人只能承擔(dān)一項工作。約束條件式（5）是指xij為0-1變量。

該模型是一個雙層0-1整數(shù)規(guī)劃，其可行分配方案的個數(shù)為n !，在n較大時，用窮舉法求解顯然不現(xiàn)實。為此，希望構(gòu)建一種能夠通過迭代運算獲取這種多階段雙層目標(biāo)分配問題的精確最優(yōu)解的算法。為實現(xiàn)這一目的，需先引入以下概念：

雖然，在i≠j的情況下，立方檢測矩陣(dij)n×n中的向量dij并不是(P)的可行分配方案，但是仿照Floyd算法[3]的迭代次序?qū)α⒎綑z測矩陣進行迭代，得到的dii(i=1，2，…，n)一定是(P)的可行分配方案。

3 多階段雙層目標(biāo)分配問題的算法

3.1 算法步驟

根據(jù)立方檢測矩陣的特點，可以按照下列方法構(gòu)建多階段雙層目標(biāo)分配問題的求解思路：首先用最小元素法[16]獲取一個可行分配方案，構(gòu)造當(dāng)前可行分配方案下的立方檢測矩陣，然后按照Floyd算法的迭代次序?qū)α⒎綑z測矩陣實施迭代運算，以獲取一個工期更短或工期不變，但總用時更少的可行分配方案，不斷重復(fù)這樣的過程，直到最終獲得工期最短，并在此前提下總用時最少的可行分配方案，這樣的分配方案便是最優(yōu)分配方案。具體的算法步驟如下：

此時，最短工期為L；該最短工期下的最少總用時為T。

由上述算法步驟看出，步驟（1）給出初始可行分配方案的時間復(fù)雜度為O(n3)，存儲輸入數(shù)據(jù)的空間復(fù)雜度為O(n2)；步驟（3）構(gòu)造當(dāng)前可行分配方案下的立方檢測矩陣的時間復(fù)雜度為O(n3)，空間復(fù)雜度為O(n3)；步驟（4）至步驟（11）按照Floyd算法的迭代次序進行迭代，理論上最壞情況下，迭代一次（即由一種可行分配方案變換到另一種工期更短或者工期不變但總用時更少的可行分配方案）的時間復(fù)雜度為O(n4)，且最多迭代n!次。所以，本文給出的算法是一個時間復(fù)雜度為O(n!·n4)、空間復(fù)雜度為O(n3)的指數(shù)算法。

3.2 算法依據(jù)

定理設(shè)d是(P)的可行分配方案，(dij)n×n是對應(yīng)的立方檢測矩陣，則d為(P)的最優(yōu)分配方案的充要條件是，對(dij)n×n按照算法步驟（4）至步驟（11）實施迭代運算，迭代過程中必有dii≡d(i=1，2，…，n)。

證明必要性（反證法）假設(shè)存在dii≠d，則由立方檢測矩陣的定義和算法的迭代過程知，dii的初值為d，且隨著迭代，dij對應(yīng)的工期單調(diào)遞減或者工期保持不變，但總用時單調(diào)遞減。當(dāng)i≠j時，dij不是可行分配方案，而i=j時，dij表示由第i項工作經(jīng)過一個循環(huán)調(diào)整再重新回到第i項工作的分配方案，故dii(i=1，2，…，n)總是可行分配方案，而且dii對應(yīng)的工期小于d對應(yīng)的工期，或者dii對應(yīng)的工期等于d的工期，但是dii對應(yīng)的總用時小于d的總用時，這與d為最優(yōu)分配方案矛盾。

充分性：由算法的迭代過程知，算法的迭代具有遍歷性，并且隨著迭代，dii對應(yīng)的工期單調(diào)遞減或者工期保持不變，但總用時單調(diào)遞減。若dii≡d(i=1，2，…，n)，則說明d對應(yīng)的工期和總用時已經(jīng)達到最優(yōu)了，即d為最優(yōu)分配方案。

表1 第i人承擔(dān)第j項工作的用時

4 算例演示

為了更加直觀地顯示和了解本文所給的算法，下面用一個例子來演示這種算法的運算過程和特點。

已知，n=10，m=3，a1=3，a2=4，a3=3，D1= {1，2，3}，D2={4，5，6，7}，D3={8，9，10}，第i人承擔(dān)第j項工作的用時矩陣(tij)10×10如表1所示，求工期最短的前提下使得總用時最少的最優(yōu)分配方案。

解：由算法步驟（1）給出初始可行分配方案：d= (8，2，9，7，10，4，1，6，3，5)T，表示第8個人承擔(dān)第1項工作，第2個人承擔(dān)第2項工作，…，第5個人承擔(dān)第10項工作。按照算法步驟（2）算出此時的工期為28，總用時為60。

按照算法步驟（3）寫出該可行分配方案下的立方檢測矩陣；接著按算法步驟（4）～（11）進行第1次迭代運算，迭代到i=8，j=8，h=1時，出現(xiàn)d88≠d，d88=(6，2，9，7，10，4，1，8，3，5)T，則d88不但是可行分配方案（表示第6個人承擔(dān)第1項工作，第2個人承擔(dān)第2項工作，…，第5個人承擔(dān)第10項工作），而且d88對應(yīng)的工期比d對應(yīng)的工期更短。因此d?d88。轉(zhuǎn)到步驟（2）知，d88對應(yīng)的工期為27。

重復(fù)上述操作，至第9次（遠遠小于10!次）迭代時，知dii=d(i=1，2，…，10)，即當(dāng)前的可行分配方案d=(8，4，2，7，10，9，6，3，1，5)T是最優(yōu)分配方案，表示第8個人承擔(dān)第1項工作，第4個人承擔(dān)第2項工作，…，第5個人承擔(dān)第10項工作。此時最短工期為21，該最短工期下的最少總用時為53。具體的迭代過程和結(jié)果見表2。

表2 迭代過程

5 結(jié)論

本文給出的多階段雙層目標(biāo)分配問題屬于NP完全問題，不存在多項式算法。本文給出的算法屬于指數(shù)算法，但是其具備的單調(diào)迭代運算的特點，使其依然具有很好的運算效率，尤其是在問題的規(guī)模不是特別大的情況下。正如，求解線性規(guī)劃（屬于NP完全問題）的單純形法，雖然屬于指數(shù)算法，但其單調(diào)迭代運算的特征，使得至今沒有任何一種求解線性規(guī)劃的算法能夠取代它。因此，本文針對多階段雙層目標(biāo)分配問題給出的算法有很好的使用價值。另外，本文涉及的是一對一的多階段雙層目標(biāo)分配問題，在此基礎(chǔ)上，還可以進一步討論一對多確定型的多階段雙層目標(biāo)分配問題以及一對多非確定型的多階段雙層目標(biāo)分配問題，這些分配問題同樣有著廣泛的應(yīng)用背景。

[1]Pentico D W.Assignment problems：a golden anniversary survey[J].European Journal of Operational Research，2007，176（2）：774-793.

[2]Kuhn H W.The Hungarian method for the assignment problem[J].Naval Research Logistics Quarterly，2005，52（1）：7-21.

[3]郭強.分配問題的一種新的迭代算法[J].系統(tǒng)工程與電子技術(shù)，2004，26（12）：1915-1916.

[4]郭強，陳新莊.平衡和不平衡運輸問題與分配問題的通用迭代算法[J].運籌與管理，2007，16（6）：57-62.

[5]李巖，郭強.非確定型指派問題的求解算法[J].計算機工程與應(yīng)用，2009，45（15）：61-63.

[6]Gross O.The bottleneck assignment problem[M].Santa Monica：The Rand Corporation，1959：16-20.

[7]Mazzola J B，Neebe A W.An algorithm for the bottleneck generalized assignment problem[J].Computer&Operations Research，1993，20（4）：355-362.

[8]Aora S，Puri M C.A variant of time minimizing assignment problem[J].European Journal of Operational Research，1998，110（2）：314-325.

[9]郭強.基于相關(guān)任務(wù)分配的網(wǎng)絡(luò)計劃的算法[J].計算機學(xué)報，2008，31（7）：1138-1145.

[10]汪鳴鑫，周紹梅.基于暫態(tài)混沌神經(jīng)網(wǎng)在非平衡B指派問題的應(yīng)用[J].計算機工程，2006，32（23）：205-207.

[11]Kyparisis G J，Koulamas C.Open shop scheduling with makespan and total completion time criteria[J].Computers&Operations Research，2000，27（1）：15-27.

[12]Punnen A P，Aneja Y P.Categorized assignment scheduling：a tabu search approach[J].The Journal of the Operational Research Society，1993，44（7）：673-679.

[13]Seshan C R.Some generalisations of time minimizing assignment problem[J].Journal of Operational Research Society，1981，32（6）：489-494.

[14]Sonia，Puri M C.Two-stage time minimizing assignment problem[J].Omega，2008，36（5）：730-740.

[15]Aggarwal V，Tikekar V G，Hsu L F.Bottleneck assignment problems under categorization[J].Computers&Operations Research，1986，13（1）：11-26.

[16]錢頌迪.運籌學(xué)[M].北京：清華大學(xué)出版社，2005：80-82.

MA Qinqin,GUO Qiang,FU Xiaowei

College of Science,Northwestern Polytechnical University,Xi’an 710129,China

All jobs must be grouped into some stages and carried out successively,but jobs at the same stage can be commenced simultaneously.In this case,this paper researches how to allocate all jobs to the existing persons so as to minimize the completion time subject to the minimum makespan.A monotone decreasing iterative algorithm,which can obtain the precise optimal solution and has good computational efficiency,is proposed by introducing cubic detection matrix.

assignment problem;bi-objective;cubic detection matrix;iterative algorithm;precise optimal solution

A

TP301

10.3778/j.issn.1002-8331.1212-0219

MA Qinqin,GUO Qiang,FU Xiaowei.Precise algorithm of bi-objective assignment problem based on multi-stage. Computer Engineering and Applications,2014,50（21）：44-47.

馬芹芹（1986—），女，碩士研究生，研究領(lǐng)域為最優(yōu)化理論與算法；郭強（1961—），男，副教授，研究領(lǐng)域為最優(yōu)化理論與算法，運籌學(xué)與網(wǎng)絡(luò)規(guī)劃；付曉薇（1986—），女，碩士研究生，研究領(lǐng)域為最優(yōu)化理論與算法。E-mail：18792710927@163.com

2012-12-18

2013-02-20

1002-8331（2014）21-0044-04

CNKI出版日期：2013-03-26，http://www.cnki.net/kcms/detail/11.2127.TP.20130326.1040.006.html