基于Pareto最優(yōu)的多企業(yè)協(xié)同計(jì)劃調(diào)度優(yōu)化

張美華 李愛平 徐立云

同濟(jì)大學(xué)，上海，201804

0 引言

在生產(chǎn)運(yùn)作領(lǐng)域，調(diào)度主要是用于調(diào)配資源、合理安排生產(chǎn)作業(yè)順序。調(diào)度優(yōu)化過程就是尋找合理調(diào)度方案的過程，即對(duì)生產(chǎn)對(duì)象在不同的生產(chǎn)主體進(jìn)行生產(chǎn)時(shí)，如何合理安排生產(chǎn)的匹配關(guān)系，以優(yōu)化生產(chǎn)進(jìn)程，在滿足現(xiàn)有生產(chǎn)條件下，使生產(chǎn)收益最大化。在網(wǎng)絡(luò)協(xié)同制造環(huán)境下，計(jì)劃調(diào)度將涉及整個(gè)生產(chǎn)鏈中各個(gè)環(huán)節(jié)的任務(wù)規(guī)劃、資源共享和分配，表現(xiàn)出更強(qiáng)的動(dòng)態(tài)性、實(shí)時(shí)性以及協(xié)作性，各個(gè)目標(biāo)所面對(duì)的不確定性和動(dòng)態(tài)因素增大，調(diào)度問題的規(guī)模更大，調(diào)度解的相對(duì)穩(wěn)定性也更難控制，調(diào)度問題不僅要實(shí)現(xiàn)調(diào)度的最優(yōu)化，同時(shí)還要實(shí)現(xiàn)調(diào)度的敏捷性和動(dòng)態(tài)性，其調(diào)度優(yōu)化過程是一個(gè)復(fù)雜的隨機(jī)多目標(biāo)優(yōu)化問題［1］。不同于單目標(biāo)優(yōu)化問題，多目標(biāo)優(yōu)化問題極少存在絕對(duì)最優(yōu)解，而是存在一個(gè)最優(yōu)解集合，即Pareto最優(yōu)解集或非支配解集。

目前在網(wǎng)絡(luò)協(xié)同制造環(huán)境下多企業(yè)協(xié)作的多目標(biāo)調(diào)度優(yōu)化問題的研究方面，國(guó)內(nèi)外學(xué)者做了一些研究，也提出了很多相關(guān)的模型和算法。如文獻(xiàn)［2］建立了以加工時(shí)間、加工成本和加工質(zhì)量為目標(biāo)的多任務(wù)加工資源優(yōu)化配置多目標(biāo)模型，并進(jìn)行了基于遺傳算法的求解。針對(duì)多個(gè)具有供需關(guān)系的制造工廠和多個(gè)地域分散的客戶組成的供需網(wǎng)絡(luò)，文獻(xiàn)［3－5］建立了多目標(biāo)生產(chǎn)計(jì)劃模型，提出了禁忌搜索與后向啟發(fā)式方法相融合的B－TS算法、線性規(guī)劃法、模糊規(guī)劃與遺傳算法來(lái)解決多目標(biāo)多工廠生產(chǎn)計(jì)劃問題。文獻(xiàn)［6］針對(duì)網(wǎng)絡(luò)化協(xié)同制造中的任務(wù)分配問題，建立了以制造任務(wù)完成時(shí)間、完成成本和產(chǎn)品工藝質(zhì)量為目標(biāo)的多目標(biāo)優(yōu)化模型，提出了模型求解的改進(jìn)遺傳模擬退火算法。上述方法都是采用經(jīng)典的加權(quán)算法將多目標(biāo)問題轉(zhuǎn)化為單目標(biāo)問題進(jìn)行求解，需要根據(jù)用戶對(duì)不同目標(biāo)的偏好程度設(shè)置系數(shù)值。最近有學(xué)者提出了基于Pareto概念的多目標(biāo)進(jìn)化優(yōu)化算法，該算法通過模擬生物自然選擇和自然進(jìn)化，不依賴于決策者對(duì)目標(biāo)函數(shù)的偏好，具有隱含的并行性和全局解空間搜索的能力，并且一次運(yùn)行可得到多個(gè)Pareto最優(yōu)解或近似解供用戶選擇，非常適合求解多目標(biāo)優(yōu)化問題，受到越來(lái)越多的關(guān)注。國(guó)內(nèi)外學(xué)者在這方面已經(jīng)做了很多的研究，提出了大量多目標(biāo)進(jìn)化算法，主要包括 VEGA、NPGA、MOGA、SPEA2和NSGA－Ⅱ等算法。其中文獻(xiàn)［7］提出的NSGA－Ⅱ（non－dominated sorting genetic algorithmⅡ）算法，既有良好的收斂性和分布性，又具備較快的收斂速度，被國(guó)內(nèi)外學(xué)者廣泛引用。如文獻(xiàn)［8］提出了一種改進(jìn)的MOGA多目標(biāo)進(jìn)化算法，該算法主要用于考慮各機(jī)器間的工藝協(xié)同性時(shí)對(duì)分布式制造系統(tǒng)的工藝計(jì)劃和調(diào)度進(jìn)行求解。文獻(xiàn)［9］建立了整體運(yùn)行成本與生產(chǎn)負(fù)荷最小化的多目標(biāo)函數(shù)優(yōu)化模型，分析了其時(shí)序約束條件，并采用NSGA－Ⅱ算法進(jìn)行了分析求解。文獻(xiàn)［10］建立了同時(shí)考慮整體生產(chǎn)成本和各企業(yè)設(shè)備生產(chǎn)能力的虛擬企業(yè)多目標(biāo)生產(chǎn)計(jì)劃模型，并利用改進(jìn)的多目標(biāo)進(jìn)化算法NSGA－Ⅱ?qū)υ撃Ｐ瓦M(jìn)行求解。上述研究的共同不足是，都沒有考慮實(shí)際生產(chǎn)運(yùn)作過程中各協(xié)作企業(yè)生產(chǎn)與運(yùn)輸能力對(duì)計(jì)劃調(diào)度的影響。因此，本文基于Pareto最優(yōu)概念，針對(duì)多企業(yè)協(xié)同生產(chǎn)鏈實(shí)際運(yùn)作過程，建立了一種考慮綜合成本和完工時(shí)間的多企業(yè)協(xié)同計(jì)劃調(diào)度多目標(biāo)優(yōu)化模型，并根據(jù)實(shí)際問題對(duì)多目標(biāo)進(jìn)化算法NSGA－Ⅱ進(jìn)行優(yōu)化設(shè)計(jì)來(lái)求解協(xié)同制造過程中的計(jì)劃調(diào)度問題。

1 協(xié)同計(jì)劃調(diào)度問題分析

協(xié)同生產(chǎn)鏈由分布的協(xié)作生產(chǎn)企業(yè)提供的生產(chǎn)服務(wù)按一定順序組合，即協(xié)作生產(chǎn)企業(yè)為完成某種產(chǎn)品的生產(chǎn)任務(wù)，而形成的彼此之間的上下聯(lián)系關(guān)系，這種協(xié)作關(guān)系主要體現(xiàn)在生產(chǎn)過程間的合作與協(xié)同。由于生產(chǎn)任務(wù)之間的執(zhí)行次序約束關(guān)系，使得這些協(xié)作企業(yè)的生產(chǎn)活動(dòng)相互聯(lián)系又相互制約。因而，在協(xié)同制造過程中，生產(chǎn)鏈上所有企業(yè)之間的計(jì)劃調(diào)度與協(xié)調(diào)非常重要。本文采用有向無(wú)回圖DAG來(lái)抽象表示各子任務(wù)間的時(shí)序約束關(guān)系。如圖1所示，S為一個(gè)虛擬起始點(diǎn)，與無(wú)前驅(qū)子任務(wù)約束的子任務(wù)節(jié)點(diǎn)相連，虛擬起始點(diǎn)不占用任何操作時(shí)間及操作成本。令G＝（T，E），其中G是子任務(wù)集T的依賴關(guān)系圖，子任務(wù)集合T＝｛T1，T2，…，Tn｝為n個(gè)子任務(wù)的集合，一個(gè)子任務(wù)Ti就是圖1中的一個(gè)節(jié)點(diǎn)，E是任務(wù)依賴關(guān)系圖中的有向邊的集合，表示節(jié)點(diǎn)間的關(guān)系，即各子任務(wù)間的約束關(guān)系，各任務(wù)的啟動(dòng)和執(zhí)行必須滿足一定的時(shí)間和順序約束。（Ti，Tj）∈E（i，j＝1，2，…，n），表示在子任務(wù)Ti沒有完成之前，任務(wù)Tj不能執(zhí)行。

圖1 子任務(wù)約束關(guān)系圖

在協(xié)同生產(chǎn)鏈的實(shí)際運(yùn)作過程中，由于協(xié)同生產(chǎn)鏈中各協(xié)作企業(yè)地理位置分散，考慮到各協(xié)作企業(yè)之間的運(yùn)輸時(shí)間、運(yùn)輸成本，以及生產(chǎn)任務(wù)之間的執(zhí)行次序約束關(guān)系，協(xié)同計(jì)劃調(diào)度優(yōu)化問題求解變得非常復(fù)雜。當(dāng)任何一個(gè)子任務(wù)選擇的協(xié)作企業(yè)改變時(shí)，都會(huì)使得該協(xié)作企業(yè)與相關(guān)聯(lián)協(xié)作企業(yè)之間的運(yùn)輸時(shí)間和運(yùn)輸成本發(fā)生變化，對(duì)前后子任務(wù)的協(xié)作企業(yè)選擇產(chǎn)生影響，進(jìn)而對(duì)其余所有的子任務(wù)選擇協(xié)作企業(yè)產(chǎn)生影響，最終影響整個(gè)協(xié)同生產(chǎn)鏈的總成本、總時(shí)間等，即任何一個(gè)子任務(wù)選擇的協(xié)作企業(yè)發(fā)生改變可以影響整個(gè)協(xié)同計(jì)劃調(diào)度優(yōu)化方案的結(jié)構(gòu)。此外，在多企業(yè)協(xié)作制造模式中，協(xié)作企業(yè)具有較高的自主性和自治性，企業(yè)根據(jù)需要可以參與多條協(xié)同生產(chǎn)鏈，對(duì)整個(gè)協(xié)同生產(chǎn)鏈而言，每一個(gè)協(xié)作企業(yè)的生產(chǎn)與運(yùn)輸能力本身都具有一定的不確定性，這是由于協(xié)同生產(chǎn)鏈的形成機(jī)制造成的。

2 協(xié)同計(jì)劃調(diào)度多目標(biāo)優(yōu)化模型

2.1 問題描述

針對(duì)在企業(yè)協(xié)同生產(chǎn)鏈實(shí)際運(yùn)作過程中，各協(xié)作企業(yè)的生產(chǎn)與運(yùn)輸能力的不確定性對(duì)協(xié)同計(jì)劃調(diào)度的影響，通過綜合考慮協(xié)同生產(chǎn)鏈中具備生產(chǎn)能力，并且愿意承擔(dān)生產(chǎn)任務(wù)的各協(xié)作企業(yè)的生產(chǎn)時(shí)間、生產(chǎn)成本，以及具有子任務(wù)時(shí)序約束關(guān)系的各協(xié)作企業(yè)間的運(yùn)輸時(shí)間、運(yùn)輸成本等指標(biāo)，建立一種考慮綜合成本和完工時(shí)間的多目標(biāo)計(jì)劃調(diào)度優(yōu)化模型，以便從眾多的計(jì)劃調(diào)度方案中選擇出整體最優(yōu)的協(xié)同計(jì)劃調(diào)度方案，即為制造任務(wù)選擇出最優(yōu)的協(xié)作企業(yè)組成協(xié)同生產(chǎn)鏈，并按給定的交貨期完成任務(wù)。

前提條件假設(shè)：

（1）本文主要研究協(xié)同生產(chǎn)鏈企業(yè)間調(diào)度合作，而不涉及各企業(yè)內(nèi)部調(diào)度流程。

（2）每個(gè)子任務(wù)的開始時(shí)間依賴于其他一些子任務(wù)的完成（時(shí)序約束），生產(chǎn)任務(wù)在執(zhí)行期間不中斷。

（3）每個(gè)子任務(wù)只交由一個(gè)生產(chǎn)企業(yè)完成。

（4）忽略企業(yè)的訂貨及企業(yè)內(nèi)部的庫(kù)存成本，僅考慮企業(yè)間的生產(chǎn)成本、時(shí)間及運(yùn)輸成本。

2.2 協(xié)同計(jì)劃調(diào)度多目標(biāo)優(yōu)化模型

設(shè)協(xié)同生產(chǎn)鏈內(nèi)共有協(xié)作企業(yè)m個(gè)，某一制造任務(wù)可以分解為具有時(shí)序約束的子任務(wù)n個(gè)。對(duì)于任一子任務(wù)Ti（i＝1，2，…，n），有 mi（mi∈m）個(gè)協(xié)作企業(yè)可以完成。D為整個(gè)任務(wù)的交貨期。最后一個(gè)子任務(wù)Tn的完成時(shí)間dn為整個(gè)任務(wù)的實(shí)際完工時(shí)間。

2.2.1 決策空間

協(xié)同計(jì)劃調(diào)度方案可以描述為：P＝｛Mij，STij，F(xiàn)Tij，Cij，dn｝，即包含了所有子任務(wù)的最優(yōu)生產(chǎn)企業(yè)、開始生產(chǎn)時(shí)間、完工時(shí)間、綜合成本，以及交貨期等參數(shù)。

可選協(xié)同計(jì)劃調(diào)度方案集合為

式中，NSM為可選協(xié)同計(jì)劃調(diào)度方案的總數(shù)量。

子任務(wù)集合為T＝｛T1，T2，…，Tn｝；子任務(wù)Ti的備選協(xié)作企業(yè)的集合為Mi＝｛Mi1，Mi2，…，Mij｝，（j∈ ｛1，2，…，mi｝，i∈ ｛1，2，…，n｝）；定義決策變量：

定義子任務(wù)約束：

2.2.2 協(xié)同計(jì)劃調(diào)度多目標(biāo)優(yōu)化模型

面向協(xié)同生產(chǎn)鏈的協(xié)同生產(chǎn)計(jì)劃調(diào)度優(yōu)化目標(biāo)是使整個(gè)任務(wù)的制造過程最優(yōu)，即整個(gè)協(xié)同生產(chǎn)鏈的綜合成本最低，任務(wù)完工時(shí)間最短。

其對(duì)應(yīng)的多目標(biāo)優(yōu)化模型為：

（1）綜合成本最低。數(shù)學(xué)表述式為

式中，Cij為企業(yè)Mj完成子任務(wù)Ti的生產(chǎn)成本；dCjk為存在時(shí)序約束關(guān)系的2個(gè)子任務(wù)所選中企業(yè)Mj、Mk間的運(yùn)輸成本；δCij為企業(yè)Mj生產(chǎn)成本的動(dòng)態(tài)不確定因子；δdCjk為企業(yè)Mj、Mk間運(yùn)輸成本的動(dòng)態(tài)不確定因子。

（2）任務(wù)完工時(shí)間最短。數(shù)學(xué)表述式為

每個(gè)任務(wù)的完工日期為

式中，MTij為子任務(wù)Ti在企業(yè)Mj的生產(chǎn)時(shí)間；dTjk為存在時(shí)序約束關(guān)系的2個(gè)子任務(wù)所選中企業(yè)Mj、Mk間的運(yùn)輸時(shí)間；δMTij為企業(yè)Mj生產(chǎn)子任務(wù)Ti的生產(chǎn)時(shí)間的動(dòng)態(tài)不確定因子；δdTjk為企業(yè)Mj、Mk間的運(yùn)輸時(shí)間的動(dòng)態(tài)不確定因子。

（3）約束條件。

①任務(wù)選擇約束：

式（4）表示每個(gè)子任務(wù)必須選擇且只能選擇一個(gè)企業(yè)進(jìn)行生產(chǎn)。

②任務(wù)時(shí)序約束：

式（5）表示對(duì)有時(shí)序約束關(guān)系的子任務(wù)，前一子任務(wù)完工后，后一子任務(wù)才能開工。

③資源約束：

式（6）表示同一企業(yè)同一時(shí)間只能加工一個(gè)子任務(wù)。

④總交貨期約束：

3 基于Pareto最優(yōu)的NSGA－Ⅱ算法

3.1 基于Pareto最優(yōu)的NSGA－Ⅱ算法原理

NSGA算法［12］是基于個(gè)體的等級(jí)按層次來(lái)分類的，將非支配排序法引入遺傳算法，在選擇配對(duì)之前，先按解個(gè)體的非支配性進(jìn)行排序。NSGA－Ⅱ是對(duì)NSGA算法的改進(jìn)，采用了快速的非支配性排序方法（fast－nondominated－sorting），定義的擁擠距離（crowding distance）用于估計(jì)某個(gè)點(diǎn)周圍的解密度，以取代適應(yīng)值共享。NSGA－Ⅱ有效地克服了NSGA的三大缺陷，使得其計(jì)算復(fù)雜性降低，具備最優(yōu)保留機(jī)制及無(wú)需確定一個(gè)共享參數(shù)，從而進(jìn)一步提高了計(jì)算效率和算法的魯棒性。

本文基于Pareto最優(yōu)解思想，利用NSGA－Ⅱ多目標(biāo)優(yōu)化算法來(lái)探討多目標(biāo)協(xié)同計(jì)劃調(diào)度的優(yōu)化方法。改進(jìn)的NSGA－Ⅱ算法流程如圖2所示，在算法的整體框架內(nèi)，根據(jù)問題的實(shí)際要求設(shè)計(jì)了有效的編解碼方式和遺傳操作，集成了局部變異種群重復(fù)個(gè)體和自適應(yīng)精英保留策略，用以保證算法的收斂性和多樣性。

3.2 基于NSGA－Ⅱ的調(diào)度優(yōu)化算法設(shè)計(jì)

3.2.1 染色體編碼與解碼

圖2 改進(jìn)的NSGA－Ⅱ算法基本流程圖

編碼的好壞直接影響到進(jìn)化的方法以及進(jìn)化運(yùn)算的效率。協(xié)同計(jì)劃調(diào)度的目的是進(jìn)行子任務(wù)的分配與時(shí)間的優(yōu)化，本文在編碼過程中只考慮子任務(wù)分配問題，至于時(shí)間的制定與優(yōu)化，將由解碼過程分析實(shí)現(xiàn)。在一般情況下，與每個(gè)子任務(wù)相對(duì)的協(xié)作企業(yè)的數(shù)量都是不等的，因此采用基于排列的實(shí)值編碼，每條染色體代表一個(gè)調(diào)度選擇方案。

編碼規(guī)則如下：

（1）將子任務(wù)編號(hào)為1，2，…，n。

（2）一個(gè)個(gè)體由n個(gè)基因組成，每一基因的位置與子任務(wù)號(hào)相對(duì)應(yīng)。

（3）將所有的協(xié)作企業(yè)進(jìn)行編號(hào)，不同的子任務(wù)對(duì)應(yīng)的協(xié)作企業(yè)數(shù)mi不同，一個(gè)協(xié)作企業(yè)可以申請(qǐng)多項(xiàng)子任務(wù)，但是一項(xiàng)子任務(wù)只能分配給一個(gè)協(xié)作企業(yè)。

（4）初始個(gè)體的每個(gè)基因位上的值，在相互排斥的第i個(gè)子任務(wù)的所有備選協(xié)作企業(yè)的集合｛1，2，…，Mi｝之中隨機(jī)產(chǎn)生，染色體結(jié)構(gòu)如圖3所示。即一條染色體中基因位用來(lái)表示子任務(wù)，而對(duì)應(yīng)的基因值則用來(lái)表示該子任務(wù)所選擇的協(xié)作企業(yè)。如第4位的“7”表示：子任務(wù)T4由協(xié)作企業(yè)M7來(lái)完成。

圖3 染色體結(jié)構(gòu)圖

解碼過程也是對(duì)各協(xié)作企業(yè)調(diào)度的過程，以確定各子任務(wù)在協(xié)作企業(yè)的開始和完工時(shí)間，并得到整個(gè)任務(wù)的總交貨時(shí)間。在解碼過程中，要根據(jù)子任務(wù)約束Riq，主要保證某一子任務(wù)開始生產(chǎn)時(shí)所有的關(guān)聯(lián)子任務(wù)已經(jīng)完成。編碼方案的解碼分為兩步：首先，將染色體根據(jù)基因值依次轉(zhuǎn)換為子任務(wù)的協(xié)作企業(yè)序列；其次，依照協(xié)作企業(yè)序列查找對(duì)應(yīng)子任務(wù)的生產(chǎn)時(shí)間、運(yùn)輸時(shí)間，根據(jù)約束式（5），計(jì)算該子任務(wù)的上一個(gè)相關(guān)聯(lián)約束子任務(wù)的完成時(shí)間，取較大者為該子任務(wù)的最早開始時(shí)間，如果該子任務(wù)前面無(wú)約束子任務(wù)時(shí)，根據(jù)約束式（6）查看該子任務(wù)對(duì)應(yīng)的協(xié)作企業(yè)的當(dāng)前完工時(shí)間，取其作為該子任務(wù)的開始時(shí)間。重復(fù)此過程，直至將所有子任務(wù)分配給各自的協(xié)作企業(yè)為止，最終獲得各子任務(wù)的開始時(shí)間和完工時(shí)間以及總完工時(shí)間，從而得到一個(gè)協(xié)同計(jì)劃調(diào)度方案。

3.2.2 快速非支配性排序方法和精英策略

（1）快速非支配性排序。在NSGA－Ⅱ算法中，個(gè)體的適應(yīng)度包括最優(yōu)解的非支配等級(jí)和擁擠距離。根據(jù)解碼結(jié)果及式（1）、式（2），計(jì)算每個(gè)個(gè)體相應(yīng)的f1（x）和f2（x）目標(biāo)函數(shù)值，以此作為非支配性分層的依據(jù)，對(duì)最優(yōu)解集中的解根據(jù)目標(biāo)函數(shù)值的大小進(jìn)行排序，并賦予相應(yīng)的非支配等級(jí)。然后對(duì)每一層進(jìn)行擁擠距離的排序。擁擠距離用于估計(jì)一個(gè)解周圍其他解的密集程度。設(shè)每一個(gè)體i的支配等級(jí)屬性和擁擠距離屬性分別為irank和idis，隨機(jī)選取2個(gè)個(gè)體并進(jìn)行比較，保留一個(gè)優(yōu)良個(gè)體，淘汰另一較差個(gè)體。其過程為

在NSGA－Ⅱ算法中，由于個(gè)體適應(yīng)度值分配機(jī)制和構(gòu)造新種群時(shí)的個(gè)體選擇機(jī)制，合并種群時(shí)容易產(chǎn)生一些重復(fù)個(gè)體被賦予了相同的適應(yīng)度值而被選擇進(jìn)入了下一代種群中，使得算法對(duì)目標(biāo)空間的搜索效率變低，而且這種個(gè)體重復(fù)的現(xiàn)象不會(huì)隨著算法的運(yùn)行而消失，在最終的輸出解集里面仍然有一定數(shù)量的個(gè)體在目標(biāo)空間是相互重復(fù)的。因此算法所得解集的分布性受到影響，解集質(zhì)量不夠理想。在本文中，每次在種群合并后的分層排序階段，為了保持種群的個(gè)體多樣性，首先，對(duì)合并后的種群Rt檢驗(yàn)其是否具有重復(fù)的個(gè)體，若有，則對(duì)該重復(fù)個(gè)體進(jìn)行局部變異，直至種群Rt中的個(gè)體各不相同，并由式（1）和式（2）計(jì)算所有新個(gè)體的目標(biāo)函數(shù)值。

（2）精英策略。精英策略即保留父代中的優(yōu)良個(gè)體直接進(jìn)入子代，這種方法在保持好的個(gè)體及加速向Pareto前沿收斂方面都有很好的表現(xiàn)。但在NSGA－Ⅱ算法中由于沒有限制精英解的范圍，使得種群在進(jìn)化到某一代以后，種群中的所有解都是精英，隨后各代的操作都將在精英解中進(jìn)行，非精英解無(wú)法參與其中，降低了解的多樣性，使得全局解的搜索速度減慢并最終導(dǎo)致種群過早收斂到局部Pareto解。

因此，為了確保個(gè)體的多樣性及搜索向全局Pareto優(yōu)解收斂，自適應(yīng)地限制當(dāng)前精英解集的范圍，從而使非精英解集也能平等的參與到新種群的操作就顯得尤為重要。因此，在組成父代種群時(shí)，我們采用文獻(xiàn)［13］的分布函數(shù)自適應(yīng)地選取精英數(shù)量，從而更好地保持種群的多樣性。其分布函數(shù)為

式中，ni為從非支配集合Fi中選取的個(gè)體數(shù)；nFi為非支配集合Fi中的個(gè)體數(shù)；r為自適應(yīng)精英算子，r∈（0，1）是一個(gè)可以由用戶來(lái)自定義的參數(shù)。

從分布函數(shù)可以看出，等級(jí)1（i＝1）中所選取的精英數(shù)的比例最大，而等級(jí)1中的解是當(dāng)前種群中最好的最優(yōu)解，這充分照顧到了精英解，使得遺傳操作中具有較多的精英解參與，同時(shí)也使得非精英解參與到新種群的操作中。隨著等級(jí)數(shù)i值的增大，每個(gè)非支配層中所選取的精英解比例依次減少，這對(duì)于各個(gè)等級(jí)都是公平的，也體現(xiàn)了“適者生存，優(yōu)勝劣汰”的思想。

3.2.3 遺傳算法算子的設(shè)計(jì)

（1）選擇操作。這里采用二元錦標(biāo)賽選擇算子，從父代種群Pt＋1中隨機(jī)選擇2個(gè)染色體，按排序等級(jí)值越小越優(yōu)先，同一等級(jí)則擁擠距離越大越優(yōu)先的原則，采用隨機(jī)錦標(biāo)賽的形式來(lái)產(chǎn)生優(yōu)選種群。

（2）交叉操作。根據(jù)協(xié)同計(jì)劃調(diào)度的染色體編碼方案特點(diǎn)和約束，在本文中，優(yōu)化算法將采用均勻交叉算子，即將每個(gè)點(diǎn)都作為潛在的交叉點(diǎn)，隨機(jī)產(chǎn)生與個(gè)體等長(zhǎng)的0－1掩碼，掩碼中的片斷表明了哪個(gè)父?jìng)€(gè)體向子個(gè)體提供變量值，然后根據(jù)該模板對(duì)2個(gè)父代個(gè)體進(jìn)行交叉，得到2個(gè)新個(gè)體，這樣保證產(chǎn)生的每個(gè)子個(gè)體都是可行解，可提高算法的搜索效率，保持種群的多樣性。

（3）變異操作。由于協(xié)同生產(chǎn)鏈中每個(gè)子任務(wù)都可以由多個(gè)協(xié)作企業(yè)來(lái)完成，這里采用隨機(jī)擾動(dòng)算子，選定一個(gè)個(gè)體作為父?jìng)€(gè)體，隨機(jī)選擇一個(gè)基因位，被選中個(gè)體的基因值用協(xié)作企業(yè)集合Mi中隨機(jī)選取的整數(shù)替代。

4 仿真應(yīng)用

以某柴油機(jī)廠為例，某一任務(wù)可以分解為8個(gè)有時(shí)序約束關(guān)系的子任務(wù)，協(xié)同生產(chǎn)鏈由10家備選協(xié)作企業(yè)組成，各子任務(wù)約束關(guān)系如圖1所示，則子任務(wù)約束矩陣中：R12＝1，R24＝1，R34＝1，R47＝1，R57＝1，R68＝1，R78＝1。子任務(wù)Ti的備選企業(yè) Mi 集合為 T1：｛M1，M3，M4，M6，M10｝，M1＝5；T2：｛M2，M3，M5，M8｝，M2＝4；T3：｛M1，M2，M3，M4，，M8，M9｝，M3＝6；T4：｛M2，M5，M7，M9｝，M4＝4；T5：｛M3，M4，M6，M8，M10｝，M5＝5；T6：｛M1，M5，M8，M10｝，M6 ＝4；T7：｛M4，M7，M9｝，M7＝3；T8：｛M2，M5，M7，M8，M10｝，M8＝5；交貨期為60天。

其中各備選協(xié)作企業(yè)的生產(chǎn)成本和生產(chǎn)時(shí)間如表1所示。

表1 各備選協(xié)作企業(yè)的生產(chǎn)成本（萬(wàn)元）和生產(chǎn)時(shí)間（d）

各備選企業(yè)之間的運(yùn)輸時(shí)間dTij和運(yùn)輸成本dCij可分別表示為

用MATLAB 2009進(jìn)行仿真，初始種群大小為100，迭代次數(shù)為100次，取交叉概率Pc＝0.7，變異概率Pm＝0.05，自適應(yīng)精英算子r＝0.9。

初始種群個(gè)體的分布及Pareto最優(yōu)解集如圖4、圖5所示。

圖4 初始種群的分布圖

圖5 協(xié)同計(jì)劃調(diào)度Pareto最優(yōu)解集

從圖4、圖5可以看出，初始種群中的個(gè)體散亂分布于一個(gè)較大的范圍內(nèi)，而當(dāng)算法結(jié)束時(shí)，個(gè)體分布已經(jīng)集中到了最優(yōu)解所存在的區(qū)域內(nèi)，所得最優(yōu)解集在Pareto前沿分布均勻，具有良好的多樣性和收斂性。最優(yōu)解集所對(duì)應(yīng)的一組協(xié)同計(jì)劃調(diào)度優(yōu)化方案如表2所示。

表2 協(xié)同計(jì)劃調(diào)度優(yōu)化方案

決策者可根據(jù)自己的偏好或結(jié)合生產(chǎn)實(shí)際情況，選取一個(gè)方案作為優(yōu)化調(diào)度結(jié)果。此外，由表2也可以看出，方案4和方案5具有相近的目標(biāo)值，選擇的企業(yè)也相似，因此，當(dāng)實(shí)際生產(chǎn)中遇到任何變動(dòng)時(shí)，還可以進(jìn)行快速的反應(yīng)和處理，提高了企業(yè)協(xié)同計(jì)劃調(diào)度的靈活性。圖6所示為選取方案4時(shí)對(duì)應(yīng)的協(xié)同計(jì)劃調(diào)度甘特圖，數(shù)字表示任務(wù)和執(zhí)行的企業(yè)。

圖6 協(xié)同計(jì)劃調(diào)度甘特圖

為驗(yàn)證算法在解決協(xié)同生產(chǎn)計(jì)劃調(diào)度多目標(biāo)優(yōu)化問題上的性能，同時(shí)采用VEGA和SPEA2算法在參數(shù)設(shè)置相同的情況下進(jìn)行計(jì)算比較。表3所示為應(yīng)用NSGA－Ⅱ算法與VEGA和SPEA2算法各運(yùn)行30次的對(duì)比結(jié)果。計(jì)算結(jié)果表明，本文算法具有計(jì)算耗時(shí)少，解的性能較好，對(duì)于求解協(xié)同制造計(jì)劃調(diào)度的多目標(biāo)優(yōu)化問題能取得良好的效果。

表3 算法性能比較

5 結(jié)論

針對(duì)在企業(yè)協(xié)同生產(chǎn)鏈實(shí)際運(yùn)作過程中，各協(xié)作企業(yè)的生產(chǎn)與運(yùn)輸能力的不確定性對(duì)協(xié)同計(jì)劃調(diào)度的影響，本文以綜合成本和任務(wù)完工時(shí)間為優(yōu)化目標(biāo)，在子任務(wù)執(zhí)行時(shí)序、總?cè)蝿?wù)執(zhí)行時(shí)間、協(xié)作企業(yè)資源約束下，建立了一種適合多企業(yè)協(xié)同計(jì)劃調(diào)度的多目標(biāo)優(yōu)化模型。為了從眾多的計(jì)劃調(diào)度方案中選擇出整體最優(yōu)的協(xié)同計(jì)劃調(diào)度方案，本文利用Pareto最優(yōu)概念的NSGA－Ⅱ多目標(biāo)進(jìn)化算法進(jìn)行求解，設(shè)計(jì)了有效的編解碼方式和遺傳算子操作規(guī)程，并通過局部變異種群重復(fù)個(gè)體改善解集的質(zhì)量，提高算法的搜索效率，自適應(yīng)地選取Pareto最優(yōu)解集的精英數(shù)量，更好地保持了種群的多樣性和全局最優(yōu)解的收斂性。所建立的多目標(biāo)優(yōu)化模型使多企業(yè)協(xié)同生產(chǎn)鏈整個(gè)任務(wù)的制造過程最優(yōu)，實(shí)現(xiàn)了節(jié)約成本與提高協(xié)作企業(yè)效益的目標(biāo)；采用多目標(biāo)優(yōu)化算法獲得的Pareto最優(yōu)解集，有利于決策者根據(jù)優(yōu)化目標(biāo)的重要程度和生產(chǎn)過程中的實(shí)際情況做出相應(yīng)的決策選擇。最后通過仿真實(shí)例，驗(yàn)證了算法的有效性。

［1］高陽(yáng)，曾小青，周偉.多智能體協(xié)同生產(chǎn)管理及其系統(tǒng)［M］.北京：清華大學(xué)出版社，2006.

［2］尹勝，尹超，劉飛，等.多任務(wù)外協(xié)加工資源優(yōu)化配置模型及遺傳算法求解［J］.重慶大學(xué)學(xué)報(bào)，2010，33（3）：49－55.

［3］蘇生，戰(zhàn)德臣，李海波，等.不確定需求和能力約束下的多目標(biāo)多工廠生產(chǎn)計(jì)劃［J］.計(jì)算機(jī)集成制造系統(tǒng)，2007，13（4）：692－697.

［4］Al－e－h(huán)ashem S M J，Malekly H，Aryanezhad M B.A Multi－objective Robust Optimization Model for Multi－product Multi－site Aggregate Production Planning in a Supply Chain Under Uncertainty［J］.International Journal of Production Economics，2011，134（1）：28－42.

［5］Aliev R A，F(xiàn)azlollahi B，Guirimov B G，et al.Fuzzy－genetic Approach to Aggregate Production－distribution Planning in Supply Chain Management［J］.Information Sciences，2007，177（20）：4241－4255.

［6］郭志明，莫蓉，孫惠斌，等.改進(jìn)GSA算法在協(xié)同制造任務(wù)分配中的應(yīng)用［J］.計(jì)算機(jī)工程與應(yīng)用，2011，47（14）：210－213.

［7］Deb K，Pratap A，Agarwal S，et al.A Fast and Elitist Multiobjective Genetic Algorithm：NSGA－Ⅱ［J］.IEEE Transactions on Evolutionary Computation，2002，6（2）：182－197.

［8］Zhang Wenqiang，Gen M.Process Planning and Scheduling in Distributed Manufacturing System U－sing Multiobjective Genetic Algorithm ［J］.IEEE Transactions on Electrical and Electronic Engineering，2010，5（1）：62－72.

［9］Cheng Fangqi，Ye Feifan，Yang Jianguo.Multi－objective Optimization of Collaborative Manufacturing Chain with Time－sequence Constraints［J］.The International Journal of Advanced Manufacturing Technology，2009，40（9／10）：1024－1032.

［10］高陽(yáng)，羅根.不確定環(huán)境下虛擬企業(yè)生產(chǎn)計(jì)劃多目標(biāo)優(yōu)化模型研究［J］.組合機(jī)床與自動(dòng)化加工技術(shù)，2009（1）：97－100.

［11］王小平，曹立明.遺傳算法－理論、應(yīng)用與軟件實(shí)現(xiàn)［M］.西安：西安交通大學(xué)出版社，2002.

［12］Srinivas N，Deb K.Multi－objective Optimization Using Nondominated Sorting in Genetic Algorithms［J］.Evolutionary Computation，1994，2（3）：221－248.

［13］楊善學(xué)，王宇平.基于Pareto最優(yōu)和限制精英的多目標(biāo)進(jìn)化算法［J］.計(jì)算機(jī)工程與應(yīng)用，2007，43（2）：108－110.