張美華 李愛平 徐立云

同濟大學，上海，201804

0 引言

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

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

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

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

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

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

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

2.1 問題描述

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

前提條件假設：

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

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

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

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

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

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

2.2.1 決策空間

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

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

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

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

定義子任務約束：

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

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

其對應的多目標優(yōu)化模型為：

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

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

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

每個任務的完工日期為

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

（3）約束條件。

①任務選擇約束：

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

②任務時序約束：

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

③資源約束：

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

④總交貨期約束：

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

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

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

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

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

3.2.1 染色體編碼與解碼

圖2 改進的NSGA－Ⅱ算法基本流程圖

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

編碼規(guī)則如下：

（1）將子任務編號為1，2，…，n。

（2）一個個體由n個基因組成，每一基因的位置與子任務號相對應。

（3）將所有的協(xié)作企業(yè)進行編號，不同的子任務對應的協(xié)作企業(yè)數(shù)mi不同，一個協(xié)作企業(yè)可以申請多項子任務，但是一項子任務只能分配給一個協(xié)作企業(yè)。

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

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

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

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

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

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

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

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

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

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

3.2.3 遺傳算法算子的設計

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

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

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

4 仿真應用

以某柴油機廠為例，某一任務可以分解為8個有時序約束關(guān)系的子任務，協(xié)同生產(chǎn)鏈由10家備選協(xié)作企業(yè)組成，各子任務約束關(guān)系如圖1所示，則子任務約束矩陣中：R12＝1，R24＝1，R34＝1，R47＝1，R57＝1，R68＝1，R78＝1。子任務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)時間如表1所示。

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

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

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

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

圖4 初始種群的分布圖

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

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

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

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

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

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

表3 算法性能比較

5 結(jié)論

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

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

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

［3］蘇生，戰(zhàn)德臣，李海波，等.不確定需求和能力約束下的多目標多工廠生產(chǎn)計劃［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］郭志明，莫蓉，孫惠斌，等.改進GSA算法在協(xié)同制造任務分配中的應用［J］.計算機工程與應用，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］高陽，羅根.不確定環(huán)境下虛擬企業(yè)生產(chǎn)計劃多目標優(yōu)化模型研究［J］.組合機床與自動化加工技術(shù)，2009（1）：97－100.

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

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

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