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

馬芹芹，郭強(qiáng)，付曉薇

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

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

馬芹芹，郭強(qiáng)，付曉薇

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

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

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

1 引言

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

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

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

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

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

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

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

3.1 算法步驟

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

此時(shí)，最短工期為L(zhǎng)；該最短工期下的最少總用時(shí)為T(mén)。

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

3.2 算法依據(jù)

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

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

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

表1 第i人承擔(dān)第j項(xiàng)工作的用時(shí)

4 算例演示

為了更加直觀地顯示和了解本文所給的算法，下面用一個(gè)例子來(lái)演示這種算法的運(yùn)算過(guò)程和特點(diǎn)。

已知，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項(xiàng)工作的用時(shí)矩陣(tij)10×10如表1所示，求工期最短的前提下使得總用時(shí)最少的最優(yōu)分配方案。

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

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

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

表2 迭代過(guò)程

5 結(jié)論

本文給出的多階段雙層目標(biāo)分配問(wèn)題屬于NP完全問(wèn)題，不存在多項(xiàng)式算法。本文給出的算法屬于指數(shù)算法，但是其具備的單調(diào)迭代運(yùn)算的特點(diǎn)，使其依然具有很好的運(yùn)算效率，尤其是在問(wèn)題的規(guī)模不是特別大的情況下。正如，求解線(xiàn)性規(guī)劃（屬于NP完全問(wèn)題）的單純形法，雖然屬于指數(shù)算法，但其單調(diào)迭代運(yùn)算的特征，使得至今沒(méi)有任何一種求解線(xiàn)性規(guī)劃的算法能夠取代它。因此，本文針對(duì)多階段雙層目標(biāo)分配問(wèn)題給出的算法有很好的使用價(jià)值。另外，本文涉及的是一對(duì)一的多階段雙層目標(biāo)分配問(wèn)題，在此基礎(chǔ)上，還可以進(jìn)一步討論一對(duì)多確定型的多階段雙層目標(biāo)分配問(wèn)題以及一對(duì)多非確定型的多階段雙層目標(biāo)分配問(wèn)題，這些分配問(wèn)題同樣有著廣泛的應(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]郭強(qiáng).分配問(wèn)題的一種新的迭代算法[J].系統(tǒng)工程與電子技術(shù)，2004，26（12）：1915-1916.

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

[5]李巖，郭強(qiáng).非確定型指派問(wèn)題的求解算法[J].計(jì)算機(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]郭強(qiáng).基于相關(guān)任務(wù)分配的網(wǎng)絡(luò)計(jì)劃的算法[J].計(jì)算機(jī)學(xué)報(bào)，2008，31（7）：1138-1145.

[10]汪鳴鑫，周紹梅.基于暫態(tài)混沌神經(jīng)網(wǎng)在非平衡B指派問(wèn)題的應(yīng)用[J].計(jì)算機(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]錢(qián)頌迪.運(yùn)籌學(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àn)樽顑?yōu)化理論與算法；郭強(qiáng)（1961—），男，副教授，研究領(lǐng)域?yàn)樽顑?yōu)化理論與算法，運(yùn)籌學(xué)與網(wǎng)絡(luò)規(guī)劃；付曉薇（1986—），女，碩士研究生，研究領(lǐng)域?yàn)樽顑?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