基于混合算法求解指派問(wèn)題目標(biāo)規(guī)劃模型

王文璨 鞏 梨 劉林忠

(蘭州交通大學(xué)交通運(yùn)輸學(xué)院 甘肅 蘭州 730070)

0 引 言

在運(yùn)籌學(xué)范疇當(dāng)中，指派問(wèn)題是一類很經(jīng)典的問(wèn)題，已經(jīng)廣泛應(yīng)用于生產(chǎn)服務(wù)行業(yè)、運(yùn)輸、資源配送優(yōu)化等科學(xué)研究領(lǐng)域，其目的是找出總成本最優(yōu)的工作分配計(jì)劃，是許多企業(yè)運(yùn)營(yíng)與管理優(yōu)化的基礎(chǔ)，與公司生產(chǎn)效益息息相關(guān)。指派問(wèn)題是典型的NP難問(wèn)題，因此利用高效的方法來(lái)求解該問(wèn)題可以使得人力、財(cái)力、物力的有效節(jié)省，也可以降低企業(yè)成本、提高生產(chǎn)效率。對(duì)于確定收益的指派問(wèn)題的理論與方法，國(guó)內(nèi)外學(xué)者已經(jīng)做了較為透徹的研究，并且解決此類問(wèn)題也有了非常精確的算法。然而，生活總是充滿各種不確定性，隨機(jī)影響收益的因素也較為復(fù)雜，因此對(duì)于含有不確定因素的指派問(wèn)題，其研究?jī)r(jià)值對(duì)于企業(yè)生產(chǎn)過(guò)程提高效率具有很大的經(jīng)濟(jì)意義。

Kuhn等[1]為了求解經(jīng)典指派問(wèn)題，提出著名的匈牙利算法。田倩男等[2]研究了將具有特殊屬性的任務(wù)指派給有限數(shù)量的班次，以任務(wù)完成產(chǎn)生的效益總和最大化為目標(biāo)建立數(shù)學(xué)優(yōu)化模型,應(yīng)用CPLEX軟件對(duì)實(shí)際數(shù)據(jù)進(jìn)行求解。肖繼先等[3]對(duì)隱枚舉法稍加改進(jìn)再結(jié)合不確定函數(shù)法，設(shè)計(jì)了求解指派問(wèn)題的不確定目標(biāo)機(jī)會(huì)約束規(guī)劃模型的混合智能算法。熊圣等[4]提出一種新的廣義非線性整數(shù)規(guī)劃模型，并利用LINGO進(jìn)行求解，結(jié)果表明該模型在求解多人同時(shí)參與完成一項(xiàng)任務(wù)的指派問(wèn)題上是有效的。Ding等[5]提出了一個(gè)不確定隨機(jī)指派問(wèn)題的α-optimistic模型，并設(shè)計(jì)了一種將隨機(jī)模擬引入到分枝定界算法中的求解方案，但是該算法的局限性在于需要大量的存儲(chǔ)空間和計(jì)算時(shí)間。董天雪等[6]在離散狀態(tài)轉(zhuǎn)移算法基礎(chǔ)上，引入了二次狀態(tài)轉(zhuǎn)移和停滯回溯策略，結(jié)果表明離散狀態(tài)轉(zhuǎn)移算法具有相對(duì)較好的穩(wěn)定性和全局搜索能力，優(yōu)于經(jīng)典的模擬退火算法。

本文針對(duì)利潤(rùn)矩陣和時(shí)間矩陣為隨機(jī)的情形，以最大完工利潤(rùn)和最少耗費(fèi)時(shí)間為優(yōu)化目標(biāo)，并結(jié)合不確定理論的特點(diǎn)，建立了任務(wù)分派問(wèn)題的機(jī)會(huì)約束目標(biāo)規(guī)劃模型[7，11]，根據(jù)該模型的特點(diǎn)，利用隨機(jī)模擬和非支配排序遺傳算法融合而成混合智能算法進(jìn)行求解，最后以實(shí)例為基礎(chǔ)對(duì)模型的有效性和準(zhǔn)確性進(jìn)行檢驗(yàn)。

1 指派問(wèn)題模型

1.1 經(jīng)典指派問(wèn)題

某工廠有n臺(tái)機(jī)器需要去完成n項(xiàng)生產(chǎn)任務(wù)，而且第i臺(tái)機(jī)器完成第j項(xiàng)任務(wù)獲得的利潤(rùn)為cij(cij>0)，因此該問(wèn)題的核心就是找出任務(wù)分配的最優(yōu)方案，使得最終完成所有任務(wù)后獲得的利潤(rùn)最大[8]。則數(shù)學(xué)模型如下:

(1)

(2)

(3)

xij∈{0,1} 1≤i,j≤n

(4)

式中：xij=1表示第j項(xiàng)任務(wù)分配給第i個(gè)人去完成，否則任務(wù)j未分配給員工i。式(2)說(shuō)明第j項(xiàng)生產(chǎn)加工任務(wù)只能由一臺(tái)機(jī)器來(lái)完成；式(3)說(shuō)明每臺(tái)機(jī)器i至多只可以完成一項(xiàng)任務(wù)。

1.2 指派問(wèn)題的目標(biāo)規(guī)劃模型

不確定因素在面臨的絕大多數(shù)優(yōu)化問(wèn)題中普遍含有。本文的員工以及任務(wù)自身屬性存在異質(zhì)性，員工完成相應(yīng)的任務(wù)獲得的利潤(rùn)和耗費(fèi)時(shí)間是隨機(jī)的，所以要找出該問(wèn)題的最優(yōu)分派方案就會(huì)相當(dāng)困難。針對(duì)本文的多目標(biāo)優(yōu)化問(wèn)題(multi-objective optimization problem)，給出一個(gè)允許范圍，即只要求使約束條件得到滿足的機(jī)會(huì)測(cè)度不小于預(yù)先給定的置信水平，這就是由Charnes和Cooper所提出的第二類隨機(jī)規(guī)劃，即機(jī)會(huì)約束規(guī)劃，其顯著的特點(diǎn)是隨機(jī)約束條件至少以一定的置信水平成立[9-10]。

某公司安排m個(gè)員工去完成n項(xiàng)作業(yè)(m

(5)

(6)

在第①優(yōu)先級(jí)里，給定置信水平α1下，完工后獲得的收益f1(x,c)應(yīng)盡可能要大于等于事先給的限定值b1，因此有目標(biāo)約束:

(7)

在第②優(yōu)先級(jí)里，完工時(shí)間f2(x,t)盡可能以置信水平α2不超過(guò)事先給的限定值b2，因此有目標(biāo)約束:

(8)

根據(jù)上述優(yōu)先結(jié)構(gòu)，得出的不確定環(huán)境下指派問(wèn)題的機(jī)會(huì)約束多目標(biāo)規(guī)劃模型如下所示:

(9)

(10)

(11)

(12)

(13)

xij∈{0,1}i=1,2,…,m,j=1,2,…,n

(14)

(15)

2 混合求解算法

遺傳算法是近幾年來(lái)廣泛被用來(lái)研究的搜索優(yōu)化算法，由美國(guó)的Holland教授于1972年提出，其思想是基于“物競(jìng)天擇，適者生存”的選擇原理。目前它已經(jīng)成為了一種通用的求解算法，具有很高的優(yōu)化效率。對(duì)于上述機(jī)會(huì)約束目標(biāo)規(guī)劃模型，為了提高求解效率，利用隨機(jī)模擬技術(shù)為利潤(rùn)函數(shù)和時(shí)間函數(shù)產(chǎn)生輸入輸出數(shù)據(jù)，然后來(lái)訓(xùn)練一個(gè)神經(jīng)元網(wǎng)絡(luò)逼近不確定函數(shù)，最后融入到非支配排序遺傳算法(NSGA)中，產(chǎn)生一個(gè)效率高的混合智能優(yōu)化算法。

2.1 編碼設(shè)計(jì)

編碼是遺傳算法中的基礎(chǔ)工作之一，它直接影響后續(xù)的遺傳操作，本文采用實(shí)數(shù)編碼規(guī)則，這種遺傳編碼方法操作簡(jiǎn)單靈活，譯碼過(guò)程也較為便捷。向量V1=(v1,v2,…,vk)表示一個(gè)染色體，其中1≤k≤n,1≤vk≤m，其長(zhǎng)度為作業(yè)的數(shù)量，vk代表任務(wù)k被分配給員工的序列號(hào)。例如現(xiàn)有8項(xiàng)工作，需要5個(gè)職工來(lái)完成，如表1所示。

表1 染色體結(jié)構(gòu)設(shè)計(jì)

即：職工1完成工作7，職工2完成工作2和工作8，職工3完成工作1，職工4完成工作5和工作6，職工5完成工作3和工作4。

2.2 初始化種群

良好的初始群體可以有效地節(jié)省進(jìn)化的代數(shù)，避免過(guò)早地陷入局部最優(yōu)，從而影響遺傳算法的性能。一般采用隨機(jī)選取的方式來(lái)產(chǎn)生初始群體，先給每個(gè)工人隨機(jī)分配一個(gè)工作，然后再將剩余沒(méi)被分配的工作隨機(jī)的分配給任意員工。此方法生成的染色體V1,V2,…,VK避免了產(chǎn)生不可行的初始解，該過(guò)程不斷循環(huán)，直到預(yù)先設(shè)定的規(guī)模被初始群體中染色體數(shù)填滿。

2.3 遺傳操作

2.3.1選擇操作

適應(yīng)度值最主要的作用是對(duì)染色體進(jìn)行評(píng)價(jià)，以此作為遺傳操作選優(yōu)淘劣的依據(jù)，因此適應(yīng)度函數(shù)對(duì)于種群的進(jìn)化行為具有很大的決定作用。為了避免進(jìn)化個(gè)體會(huì)偏向某一個(gè)目標(biāo)，本文適應(yīng)度函數(shù)利用非支配排序原理對(duì)種群首先進(jìn)行分級(jí)，然后根據(jù)級(jí)別高低，賦予相應(yīng)的虛擬適應(yīng)度值，級(jí)別越低，適應(yīng)值越高[12]。最后通過(guò)輪盤賭旋轉(zhuǎn)法決定哪些染色體可以進(jìn)行進(jìn)一步的進(jìn)化行為。

2.3.2交叉操作

例如C=5，則交叉過(guò)程如圖1所示。

圖1 交叉方法

2.3.3變異操作

例如V=4，temp=3，則變異過(guò)程如圖2所示。

圖2 變異方法

2.4 算法步驟

非支配排序遺傳算法(NSGA)是由Srinivas和Deb提出的，常常用于求解多目標(biāo)優(yōu)化問(wèn)題，該算法基于非支配排序原理對(duì)種群中的個(gè)體進(jìn)行分級(jí)，對(duì)每一級(jí)分配虛擬適應(yīng)度值，它是基于Pareto最優(yōu)解討論的多目標(biāo)優(yōu)化算法(MOGA)[13-14]。當(dāng)問(wèn)題含有多個(gè)目標(biāo)函數(shù)時(shí)，它們之間相互制約，一個(gè)可行解對(duì)于其中一個(gè)目標(biāo)函數(shù)是最優(yōu)的，但對(duì)于剩余目標(biāo)函數(shù)未必是最好，也有可能卻是惡化的。因此對(duì)于多目標(biāo)優(yōu)化問(wèn)題，往往存在一個(gè)Pareto最優(yōu)解，這個(gè)解對(duì)于所有目標(biāo)函數(shù)來(lái)說(shuō)是個(gè)可“接納”的均衡解，它不被其他決策變量所支配，Pareto最優(yōu)解更好地協(xié)同了多個(gè)優(yōu)化目標(biāo)之間的不相容的問(wèn)題。

算法步驟如下：

Step1根據(jù)Cij和Tij服從的概率分布，利用隨機(jī)模擬技術(shù)為利潤(rùn)函數(shù)和時(shí)間函數(shù)產(chǎn)生輸入輸出數(shù)據(jù)[9]。

Step2根據(jù)Step 1產(chǎn)生的數(shù)據(jù)訓(xùn)練一個(gè)神經(jīng)元網(wǎng)絡(luò)逼近利潤(rùn)函數(shù)和時(shí)間函數(shù)[9]。

Step3根據(jù)初始條件隨機(jī)生成符合約束的N個(gè)染色體，并通過(guò)訓(xùn)練好的神經(jīng)元網(wǎng)絡(luò)對(duì)染色體的可行性進(jìn)一步進(jìn)行檢驗(yàn)[10]。

Step4利用非支配排序原理對(duì)種群染色體進(jìn)行分級(jí)，然后給每一級(jí)按照規(guī)則指定一個(gè)虛擬適應(yīng)度值，級(jí)別越高，賦予的適應(yīng)值越小。

Step5通過(guò)輪盤賭選擇法對(duì)染色體進(jìn)行選擇，以此進(jìn)行后續(xù)的遺傳操作。

Step6進(jìn)行交叉和變異來(lái)更新染色體，并對(duì)子代染色體的可行性利用訓(xùn)練好的神經(jīng)元網(wǎng)絡(luò)進(jìn)行檢驗(yàn)[10]。

Step7利用訓(xùn)練好的神經(jīng)元網(wǎng)絡(luò)計(jì)算所有個(gè)體的函數(shù)值[10]。

Step8重復(fù)Step 4到Step 7，直到循環(huán)次數(shù)達(dá)到迭代終止次數(shù)。

Step9篩選出的最好的個(gè)體作為最優(yōu)解。

3 實(shí)例分析

假設(shè)某工廠有8項(xiàng)生產(chǎn)任務(wù)待生產(chǎn)，而該工廠有5臺(tái)機(jī)器可以用來(lái)加工，在完成所有任務(wù)的前提下，希望得到最優(yōu)的分配方案。假設(shè)每臺(tái)機(jī)器完成每項(xiàng)任務(wù)用圖來(lái)表示，對(duì)每一條弧邊，其權(quán)值利潤(rùn)C(jī)ij由正態(tài)分布N(μ,σ2)生成，其中u和σ分別從區(qū)間(16,25)和(1,4)中隨機(jī)生成，耗費(fèi)的時(shí)間Tij由均勻分布U(5,20)生成，i=1,2,…,5，j=1,2,…,8。

3.1 基本信息及參數(shù)選擇

為驗(yàn)證該混合智能算法對(duì)以上機(jī)會(huì)約束規(guī)劃模型(CCP)模型的合理性，采用C語(yǔ)言進(jìn)行編程計(jì)算，程序中所采用的參數(shù)：迭代終止次數(shù)為50，種群規(guī)模為50，交叉概率由均勻分布U(0.7,0.9)隨機(jī)生成，每5代進(jìn)行一次變異,評(píng)價(jià)函數(shù)參數(shù)α=0.05，利潤(rùn)和時(shí)間得到滿足的置信水平(α1,α2)=(0.9,0.9)下，利潤(rùn)和時(shí)間的目標(biāo)水平為(b1,b2)=(200,100)。

3.2 結(jié)果分析

由于利潤(rùn)和時(shí)間為隨機(jī)變量，結(jié)合本文多目標(biāo)規(guī)劃問(wèn)題的特點(diǎn)，實(shí)例產(chǎn)生的解并不是唯一的，本算例將選擇較為優(yōu)良的一個(gè)解來(lái)進(jìn)行說(shuō)明。通過(guò)運(yùn)行混合智能算法(循環(huán)模擬次數(shù)為100，遺傳迭代次數(shù)為50)，經(jīng)過(guò)29步迭代達(dá)到最優(yōu)，得到的一個(gè)Pareto解方案為：生產(chǎn)任務(wù)4由機(jī)器1完成，生產(chǎn)任務(wù)8由機(jī)器1完成，生產(chǎn)任務(wù)3和生產(chǎn)任務(wù)5由機(jī)器3完成，生產(chǎn)任務(wù)1和生產(chǎn)任務(wù)2由機(jī)器4完成，生產(chǎn)任務(wù)6和生產(chǎn)任務(wù)7由機(jī)器5完成。其中，所有任務(wù)完工后獲得的利潤(rùn)為208元，耗費(fèi)的時(shí)間為65 min。

3.3 實(shí)例結(jié)果對(duì)比

本文采用的非支配排序遺傳算法結(jié)合神經(jīng)網(wǎng)絡(luò)相比于普通遺傳算法，提高了計(jì)算效率，對(duì)于多目標(biāo)問(wèn)題具有較優(yōu)的尋解過(guò)程，如表2所示。

表2 算法效率比較

實(shí)例證明，該混合智能算法針對(duì)類似的多目標(biāo)組合優(yōu)化問(wèn)題可以發(fā)揮最大的尋優(yōu)作用，充分展示了NSGA搜索速度快、尋優(yōu)能力強(qiáng)的優(yōu)勢(shì)，但本文采用的測(cè)試數(shù)據(jù)有限，因此在今后的研究中將增大模擬次數(shù)，進(jìn)一步進(jìn)行更加精準(zhǔn)的分析。

4 結(jié) 語(yǔ)

本文綜合考慮隨機(jī)變量(完工利潤(rùn)C(jī)ij、完工時(shí)間Tij)以及不確定理論的特點(diǎn)，構(gòu)建了指派問(wèn)題的機(jī)會(huì)約束目標(biāo)規(guī)劃模型，在此基礎(chǔ)上利用非支配排序遺傳算法來(lái)求解該模型，給出數(shù)值實(shí)例進(jìn)行測(cè)試，通過(guò)實(shí)例說(shuō)明該算法和模型能夠?yàn)樵搯?wèn)題提供最優(yōu)分配方案。