基于混合NSGA2算法的生產(chǎn)調(diào)度優(yōu)化*

趙政鑫，范 波，霍 華，孫力帆

(河南科技大學(xué)信息工程學(xué)院，洛陽 471023)

0 引言

優(yōu)化過程的目的是為了找到最優(yōu)值或最優(yōu)解，優(yōu)化問題通常為尋找最大值或最小值，根據(jù)目標(biāo)的個(gè)數(shù)劃分為單目標(biāo)優(yōu)化或者多目標(biāo)優(yōu)化，具有多個(gè)目標(biāo)的優(yōu)化問題稱為多目標(biāo)優(yōu)化。多目標(biāo)優(yōu)化模型可作為資源開發(fā)和管理計(jì)劃有效性的最佳評(píng)估工具，智能算法是求解多目標(biāo)優(yōu)化問題的主要手段。常見的智能算法有遺傳算法、粒子群算法、蟻群算法、模擬退火算法、人工蜂群算法、灰狼算法等[1-6]。

調(diào)度問題的研究有利于資源的合理分配，因此有著十分重要的意義，眾多學(xué)者為解決各式各樣的問題進(jìn)行了大量的研究，并使用智能算法尋找最佳生產(chǎn)調(diào)度計(jì)劃。荊巍巍等[7]為解決組件制造過程中的生產(chǎn)調(diào)度問題，以最小化總完工時(shí)間、生產(chǎn)成本和最大化設(shè)備負(fù)荷為目標(biāo)的柔性車間生產(chǎn)調(diào)度模型，使用非支配排序遺傳算法對(duì)多目標(biāo)模型進(jìn)行求解；ZHANG等[8]針對(duì)服裝生產(chǎn)中紡織染色工序調(diào)度問題，建立了以延遲成本和污染物排放水平為目標(biāo)的優(yōu)化模型，并使用粒子群優(yōu)化算法對(duì)多目標(biāo)數(shù)學(xué)模型進(jìn)行求解；PAKPAHAN等[9]為得到自動(dòng)化環(huán)境下作業(yè)車間的生產(chǎn)調(diào)度計(jì)劃，建立了最小化零件總加工時(shí)間和延遲懲罰的多目標(biāo)優(yōu)化模型，并使用蟻群算法對(duì)其進(jìn)行求解，得到生產(chǎn)調(diào)度的最佳時(shí)間表。

多目標(biāo)調(diào)度優(yōu)化問題的求解，需要根據(jù)所選方法具有的特點(diǎn)進(jìn)行改進(jìn)，平衡算法整體的收斂速度和搜索能力等特點(diǎn)。遺傳算法作為常用的多目標(biāo)優(yōu)化問題的求解手段，具有優(yōu)秀的全局搜索能力，但其他特點(diǎn)并不突出，需要改善遺傳算法的收斂速度和局部搜索能力，以提高計(jì)算效率。

1 多目標(biāo)優(yōu)化

1.1 多目標(biāo)優(yōu)化問題描述

多目標(biāo)優(yōu)化是多準(zhǔn)則決策的一個(gè)領(lǐng)域，涉及多個(gè)目標(biāo)函數(shù)同時(shí)優(yōu)化的數(shù)學(xué)問題[10]。通常，多目標(biāo)優(yōu)化問題的數(shù)學(xué)模型由目標(biāo)函數(shù)和約束條件兩部分組成，為統(tǒng)一求取各目標(biāo)的最小值，可以將最大值問題的目標(biāo)函數(shù)進(jìn)行求倒數(shù)或取反，從而將最大值問題轉(zhuǎn)變成最小值問題進(jìn)行求解，約束條件又可細(xì)分為不等式約束和等式約束。因此，多目標(biāo)優(yōu)化問題可以描述為：

minF(x)={f1(x),f2(x),…,fm(x)}s.t.gp(x)≤0,j=1,2,…,Ps.t.hq(x)=0,k=1,2,…,Q

式中，F(xiàn)(x)是目標(biāo)函數(shù)；x是決策變量；gp(x)≤0是不等式約束；P是不等式約束個(gè)數(shù)；hq(x)=0是等式約束；Q是等式約束個(gè)數(shù)；現(xiàn)在需要在滿足約束條件的情況下求解這些目標(biāo)函數(shù)的最小值，得到多目標(biāo)問題的解決方案。

1.2 多目標(biāo)調(diào)度優(yōu)化問題的數(shù)學(xué)模型

現(xiàn)有n個(gè)待加工產(chǎn)品，生產(chǎn)加工需要經(jīng)歷的工序數(shù)為m；處理第j道工序可用的并行機(jī)器的數(shù)量Mj；在第j道工序上分給機(jī)器k處理的任務(wù)總數(shù)Nj,k；產(chǎn)品i的工序j在機(jī)器k上的開工時(shí)間和結(jié)束時(shí)間分別為Si,j,k和Fi,j,k，ti,j,k表示產(chǎn)品i的第j道工序在機(jī)器k上的加工時(shí)間；hjk表示工序j在機(jī)器k上處理的第h個(gè)作業(yè)任務(wù)；Ci,j,k表示產(chǎn)品i的第j道工序在機(jī)器k上的加工成本；xi,j,k為決策變量，當(dāng)產(chǎn)品i的工序j使用機(jī)器k進(jìn)行加工時(shí)其數(shù)值為1，其他情況下決策變量的數(shù)值為0。

本文針對(duì)生產(chǎn)調(diào)度問題建立總加工時(shí)間和總生產(chǎn)成本的多目標(biāo)數(shù)學(xué)模型，總加工時(shí)間的目標(biāo)函數(shù)為：

T=max{Fi,m,k} (i=1,2,…,Nm,k;k=1,2,…,Mm)

(1)

總生產(chǎn)成本的目標(biāo)函數(shù)可以表示為：

(2)

調(diào)度問題的常見約束條件如下：

S(h+1)jk,j+1,r=max{F(h+1)jk,j,k,Fhjk,j+1,r}

(h=1,2,…,Njk-1;j=1,2…,m-1;k=1,2,…,Mj;r=1,2,…,Mj+1)

(3)

式(3)表示在機(jī)器r上處理第(h+1)jk個(gè)產(chǎn)品中的第j+1道工序的作業(yè)任務(wù)，即同一產(chǎn)品(h+1)jk上一道工序j的完成時(shí)間和同一臺(tái)加工機(jī)器r上一產(chǎn)品hjk的完成時(shí)間中的最大者就是第(h+1)jk個(gè)產(chǎn)品的最早可開工時(shí)間。

Fi,j,k=Si,j,k+ti,j,k

(i=1,…,n;j=1,…,m;k=1,…,Mj)

(4)

式(4)表示產(chǎn)品的結(jié)束時(shí)間和該產(chǎn)品在機(jī)器上的加工時(shí)間和開工時(shí)間有關(guān)。

(i=1,2,…,n;j=1,2,…,m)

(5)

式(5)表示加工作業(yè)任務(wù)一旦開始就不可以中斷或者轉(zhuǎn)移。

(6)

式(6)表示對(duì)于每道工序，分配給并行機(jī)器的作業(yè)數(shù)量必須和訂單的總數(shù)量一致。

Si,j,k≥0,ti,j,k≥0,Fi,j,k≥0,Ci,j,k≥0

(7)

式(7)表示非負(fù)約束。

2 改進(jìn)的混合算法

多目標(biāo)進(jìn)化算法[11](MOEA)是一種隨機(jī)優(yōu)化技術(shù)，其全局搜索能力優(yōu)秀，最終的輸出結(jié)果精確，與數(shù)學(xué)計(jì)算得到的實(shí)際最優(yōu)解相差無幾，因此經(jīng)常作為多目標(biāo)優(yōu)化問題的求解手段。與其他優(yōu)化算法類似，多目標(biāo)進(jìn)化算法用于尋找特定問題的最優(yōu)Pareto解，最具有進(jìn)化特點(diǎn)的遺傳算法就是通過種群迭代的進(jìn)化思想來求解多目標(biāo)優(yōu)化問題?；赑areto方法的遺傳算法與簡單的遺傳算法的主要區(qū)別在于：基于Pareto方法的遺傳算法使用支配關(guān)系，并根據(jù)個(gè)體之間的支配關(guān)系對(duì)種群進(jìn)行分層，使用支配地位來判斷解的好壞[12]。

在使用基于Pareto方法的遺傳算法來解決多目標(biāo)優(yōu)化問題時(shí)，其中最可靠和最常用的是帶精英策略的非支配排序的遺傳算法[13](NSGA2)，該算法是非支配排序的遺傳算法[14](NSGA)的第二個(gè)版本。相較于第一個(gè)版本，NSGA2提出了快速非支配的排序方法，降低了算法的計(jì)算復(fù)雜度；采用了擁擠度作為保持種群多樣性的指標(biāo)，也是評(píng)價(jià)同等級(jí)個(gè)體好壞的標(biāo)準(zhǔn)；引入精英策略，通過將父子種群合并，并選取排序靠前的個(gè)體作為新種群用于下一代的種群進(jìn)化。

2.1 NSGA2算法

NSGA2算法的主要包含以下內(nèi)容：

(1)非支配排序。在NSGA2算法當(dāng)中，根據(jù)支配關(guān)系將所有個(gè)體依次劃分到不同等級(jí)的前沿之中，個(gè)體的前沿等級(jí)反應(yīng)了個(gè)體的好壞程度，若相比較的兩個(gè)個(gè)體前沿等級(jí)不相同，等級(jí)數(shù)字越低，表明個(gè)體所處前沿越靠前，該個(gè)體在選擇環(huán)節(jié)的優(yōu)先度越高。

在計(jì)算每個(gè)個(gè)體所處前沿等級(jí)時(shí)，首先尋找當(dāng)前種群中的所有非支配個(gè)體，組成非支配解集F1，將該集合中所有個(gè)體均標(biāo)記為Pareto等級(jí)1，然后刪除這些個(gè)體，消除Pareto等級(jí)1對(duì)其余個(gè)體的支配。然后將剩余種群中的非支配個(gè)體提取出來組成解集F2，并為這些個(gè)體標(biāo)記為Pareto等級(jí)2，如此循環(huán)往復(fù)，直到所有個(gè)體都有獨(dú)立的等級(jí)標(biāo)記，完成對(duì)種群的分級(jí)。

(2)擁擠距離的計(jì)算。同等級(jí)的個(gè)體需要以擁擠距離為指標(biāo)來進(jìn)一步衡量個(gè)體的好壞，當(dāng)每個(gè)個(gè)體的支配等級(jí)劃分完成之后，需要進(jìn)行擁擠距離的計(jì)算，在同前沿等級(jí)的情況下，擁擠距離越大的個(gè)體，其在種群進(jìn)行非支配排序時(shí)的序列越靠前，擁擠距離的計(jì)算公式如下：

(8)

(3)個(gè)體好壞評(píng)判依據(jù)。當(dāng)兩個(gè)個(gè)體的前沿等級(jí)不相等時(shí)，優(yōu)先選擇前沿等級(jí)更小的個(gè)體；當(dāng)兩個(gè)個(gè)體的前沿等級(jí)相同時(shí)，再比較擁擠距離，優(yōu)先選取擁擠距離較大的個(gè)體。

(4)精英保留策略。在NSGA2算法中，采用的是精英保留策略為新一代種群篩選優(yōu)秀的個(gè)體。這個(gè)策略是將父子種群進(jìn)行合并，共同構(gòu)建一個(gè)總數(shù)是種群規(guī)模二倍的新種群，然后對(duì)合并后的新種群進(jìn)行前沿等級(jí)和擁擠距離的計(jì)算，得到所有個(gè)體好壞的排序，根據(jù)比較環(huán)節(jié)決優(yōu)的規(guī)則，依次為下一代代種群中填入優(yōu)秀個(gè)體，直到下一代種群的規(guī)模恢復(fù)至合并前種群的規(guī)模大小。

(5)NSGA2算法基本過程。NSGA2算法是基于Pareto方法求解多目標(biāo)優(yōu)化問題，使用支配關(guān)系來衡量個(gè)體好壞，但其迭代進(jìn)化過程與傳統(tǒng)遺傳算法大致相同，主要步驟如下：初始化參數(shù)，創(chuàng)建初始種群；對(duì)種群進(jìn)行快速非支配排序，并選取優(yōu)秀的個(gè)體進(jìn)入交配池；進(jìn)行交叉、變異等遺傳操作產(chǎn)生子代種群；父子種群合并，并采用精英選擇策略，選出的個(gè)體作為下一次迭代過程的父代種群；迭代循環(huán)，直至滿足終止條件，將Pareto等級(jí)為1的解作為最終結(jié)果輸出。

2.2 混合算法改進(jìn)初始種群

混合算法是求解多目標(biāo)優(yōu)化問題的有效方向，整合智能算法來解決優(yōu)化問題是當(dāng)前研究的一大熱點(diǎn)[15]?；旌纤惴ǖ哪繕?biāo)是根據(jù)智能算法各自的特點(diǎn)，發(fā)揮算法對(duì)應(yīng)的優(yōu)點(diǎn)，改進(jìn)混合算法整體的性能。

NSGA2算法和粒子群算法都是基于種群的方法，前者具有全局搜索能力強(qiáng)但搜索速度慢的特點(diǎn)，后者的特點(diǎn)為計(jì)算速度快卻容易過早收斂，兩者結(jié)合可以互補(bǔ)特點(diǎn)，因此本文將NSGA2算法和粒子群算法進(jìn)行混合。這兩種智能算法均是基于種群迭代的方式進(jìn)行尋優(yōu)，符合算法混合需要遵循的原則，且可以在保留各自算法自身優(yōu)點(diǎn)的同時(shí)，互相彌補(bǔ)各自的不足，得到一個(gè)整體尋優(yōu)效果更好的混合算法。

粒子群算法的核心內(nèi)容為粒子的迭代公式，式(9)、式(10)分別是每次迭代對(duì)粒子的速度和位置進(jìn)行更新：

(9)

(10)

對(duì)NSGA2算法而言，初始種群的好壞影響智能算法尋優(yōu)收斂的效率。若選取優(yōu)秀的個(gè)體參與交叉環(huán)節(jié)，可以將優(yōu)秀的基因片段分享給其他個(gè)體并遺傳給下一代，通過在尋優(yōu)過程中進(jìn)行有效的信息交換，從而提高算法整體的計(jì)算效率，增加種群搜索到最優(yōu)解的概率，加快對(duì)多目標(biāo)優(yōu)化問題的求解速度。相反，若隨機(jī)初始化產(chǎn)生的初始種群整體欠佳，交叉算子難以發(fā)揮將優(yōu)良個(gè)體的基因片段遺傳給后代的作用，交叉效果就會(huì)大打折扣，從而增加遺傳算法尋找到最優(yōu)解所消耗的時(shí)間。

如圖1所示，本文通過將粒子群算法和NSGA2算法相混合，首先在第一階段中利用粒子群算法尋優(yōu)速度快、搜索效率高的特點(diǎn)對(duì)多目標(biāo)問題進(jìn)行初步尋優(yōu)，獲得進(jìn)化到一定程度上的種群。然后混合算法進(jìn)入第二階段，將粒子群算法的輸出結(jié)果作為NSGA2算法中的部分初始種群，從而提高NSGA2算法初始種群的整體質(zhì)量，以此達(dá)到優(yōu)化NSGA2算法初始種群的目的。為增加第二階段初始種群的豐富度，將經(jīng)過粒子群算法初步優(yōu)化后的個(gè)體與第二階段隨機(jī)初始化產(chǎn)生的個(gè)體相混合，擴(kuò)大NSGA2算法的種群規(guī)模，然后進(jìn)行后續(xù)的迭代優(yōu)化。將兩種基于群體的智能算法進(jìn)行混合，不僅避免由第一階段粒子群算法尋優(yōu)得到的個(gè)體陷入局部最優(yōu)的情況，在一定程度上改善了粒子群算法容易過早收斂的缺點(diǎn)，增強(qiáng)了其全局搜索能力，還優(yōu)化了第二階段中NSGA2的初始種群，從而提高了其進(jìn)化效率、改善了優(yōu)秀基因片段的流通，有利于找尋全局最優(yōu)解。

圖1 混合算法改進(jìn)初始種群

2.3 局部搜索

局部搜索是通過在某些個(gè)體的附近區(qū)域進(jìn)行搜索，以期望產(chǎn)生更好的個(gè)體，并將其作為未來的父代參與種群進(jìn)化過程當(dāng)中。

本文在經(jīng)過交叉和變異操作環(huán)節(jié)之后增加局部搜索環(huán)節(jié)，根據(jù)個(gè)體的支配等級(jí)和擁擠距離信息，得到非支配前沿中的每個(gè)目標(biāo)的邊界點(diǎn)和除了邊界點(diǎn)之外擁擠距離最大的稀疏點(diǎn)。如圖2所示，包含擁擠距離為無窮大的邊界點(diǎn)，一共尋找擁擠距離排名前三的個(gè)體作為局部搜索的區(qū)域中心，圍繞這些個(gè)體對(duì)附近的解空間進(jìn)行局部搜索。通過采用多個(gè)策略變更染色體的基因序列從而生成局部解，將局部搜索得到的所有個(gè)體并入本次迭代的種群當(dāng)中，一起進(jìn)行快速非支配排序，共同進(jìn)行選擇操作。

圖2 局部搜索的中心

本文的局部搜索策略有以下特點(diǎn)：由于進(jìn)行局部搜索的區(qū)域中心是直接根據(jù)快速非支配排序的結(jié)果得到的，不需要重新計(jì)算新的指標(biāo)，在一定程度上減小了計(jì)算。選擇少量的個(gè)體作為局部搜索的中心，而不是對(duì)每個(gè)個(gè)體都進(jìn)行局部搜索的操作，在一定程度上避免了無效的搜索，降低了設(shè)計(jì)的復(fù)雜度。采用多個(gè)策略生成局部解，增加了局部解的多樣性，有利于尋找到更優(yōu)的個(gè)體。

采用多策略相結(jié)合方式進(jìn)行局部搜索得到的局部解組成的群體，其豐富度更高，有利于提升局部搜索的效率。本文選用逆轉(zhuǎn)基因片段、交換基因位和基因位前置的三種方式對(duì)選出的個(gè)體進(jìn)行局部搜索，多策略相結(jié)合的局部搜索提升了豐富度和多樣性，并且這些局部搜索策略的優(yōu)點(diǎn)是不會(huì)生產(chǎn)非法解。逆轉(zhuǎn)基因片段是隨機(jī)選取兩個(gè)基因節(jié)點(diǎn)，將節(jié)點(diǎn)間的遺傳信息倒序排列。交換基因位是隨機(jī)選取兩個(gè)基因位，交換兩者所攜帶的遺傳信息。基因位前置是隨機(jī)選取一個(gè)或多個(gè)基因位將其插入某個(gè)或某些基因位之前。這三種策略均是隨機(jī)挑選變更的位置，即便同一條染色體使用相同的策略，依舊有很大概率得到不同的染色體排序方式。

2.4 混合算法步驟及流程圖

改進(jìn)的混合算法具體流程如圖3所示。

圖3 混合算法流程圖

3 仿真分析

本文基于銅合金板帶生產(chǎn)調(diào)度信息進(jìn)行分析，采用文中所提到粒子群和NSGA2相結(jié)合的混合算法對(duì)銅板帶調(diào)度問題的多目標(biāo)數(shù)學(xué)模型進(jìn)行求解，得到最佳的調(diào)度方案。在符合銅板帶實(shí)際生產(chǎn)加工流程下，優(yōu)化調(diào)度任務(wù)的總加工時(shí)間和總生產(chǎn)成本，為企業(yè)節(jié)約時(shí)間、減小成本，提高生產(chǎn)效率，從而增強(qiáng)企業(yè)的競爭力。

依據(jù)銅板帶工藝的工序流程、機(jī)器分配以及生產(chǎn)約束，對(duì)各訂單在各道工序上的操作順序進(jìn)行安排。以10個(gè)銅板帶全流程生產(chǎn)加工的訂單任務(wù)為例，將銅板帶生產(chǎn)加工的全流程簡化合并為4個(gè)環(huán)節(jié)，共有12臺(tái)機(jī)器對(duì)其進(jìn)行處理，熔鑄、熱軋、冷軋、熱處理這四道工序并行機(jī)器數(shù)量分別為3臺(tái)、2臺(tái)、2臺(tái)和4臺(tái)，不同工序其加工工藝的數(shù)據(jù)信息不同。加工時(shí)間中包含了運(yùn)輸時(shí)間，生產(chǎn)成本不包含銅合金的原料成本，銅板帶訂單的調(diào)度信息如表1所示，各訂單在各環(huán)節(jié)加工時(shí)間的單位是分鐘，加工成本的單位是萬元。

表1 銅板帶調(diào)度信息

10個(gè)訂單在各道工序上的機(jī)器分配決定了具體的調(diào)度信息，本次銅板帶生產(chǎn)調(diào)度實(shí)例通過MATLAB R2020a平臺(tái)的數(shù)字仿真實(shí)現(xiàn)。所采用的混合算法主要參數(shù)信息如下，粒子群算法的種群規(guī)模為40，迭代次數(shù)為50，慣性權(quán)重為1；NSGA2算法的種群規(guī)模為100，迭代次數(shù)為300，交叉概率和變異概率分別為0.9和0.1。銅板帶生產(chǎn)調(diào)度問題的生產(chǎn)加工甘特圖如圖4所示，橫坐標(biāo)表示銅板帶生產(chǎn)加工的時(shí)間(單位是min)，縱坐標(biāo)表示銅板帶生產(chǎn)加工所使用的機(jī)器編號(hào)(機(jī)器1-3屬于熔鑄環(huán)節(jié)，機(jī)器4-6屬于熱軋環(huán)節(jié)，機(jī)器7-8屬于冷軋環(huán)節(jié)，機(jī)器9-12屬于熱處理環(huán)節(jié))，甘特圖中作業(yè)任務(wù)的格式為[訂單號(hào)，工序號(hào)]，從圖中可以清楚得知作業(yè)任務(wù)的分配。

圖4 銅板帶生產(chǎn)加工甘特圖

銅板帶調(diào)度問題的Pareto前沿如圖5所示，改進(jìn)混合算法的各個(gè)目標(biāo)值更佳，具有更好的Pareto前沿分布，表明其尋優(yōu)性能優(yōu)于原始算法。

圖5 銅板帶調(diào)度問題的Pareto前沿

從實(shí)驗(yàn)結(jié)果可以看出，銅板帶生產(chǎn)調(diào)度問題中非支配解的調(diào)度方案在總加工時(shí)間和總生產(chǎn)成本上的分布，兩個(gè)目標(biāo)相互聯(lián)系、相互沖突，每個(gè)非支配解的調(diào)度方案都有各自的優(yōu)點(diǎn)，不論是總加工時(shí)間短或者總生產(chǎn)成本低。多目標(biāo)優(yōu)化算法可以在一次運(yùn)行中為銅板帶調(diào)度問題提供多種備選解決方案，由于每個(gè)備選解決方案都有各自優(yōu)勢(shì)，無法得到一個(gè)時(shí)間和成本均是最優(yōu)的方案，企業(yè)可以根據(jù)訂單任務(wù)的具體需求在非支配解集中選擇合適的調(diào)度方案，根據(jù)所選方案解析出相對(duì)應(yīng)的生產(chǎn)加工甘特圖，從而將各個(gè)訂單任務(wù)分配到相應(yīng)的機(jī)器上進(jìn)行作業(yè)。

4 結(jié)束語

文中針對(duì)生產(chǎn)調(diào)度多目標(biāo)優(yōu)化問題，以總加工時(shí)間和總生產(chǎn)成本為目標(biāo)建立數(shù)學(xué)模型，以銅板帶全流程工藝生產(chǎn)流程為例，采用改進(jìn)混合算法對(duì)生產(chǎn)調(diào)度優(yōu)化問題進(jìn)行求解，選取其中一個(gè)調(diào)度方案并繪制甘特圖。實(shí)例結(jié)果表明，所提方法可以得到更好的Pareto前沿，在各個(gè)目標(biāo)值上的最佳值均優(yōu)于原始方法，證明了對(duì)初始種群和局部搜索進(jìn)行改進(jìn)的有效性，提高了生產(chǎn)調(diào)度多目標(biāo)問題的求解效率。根據(jù)算法求取的調(diào)度方案更具合理性，有利于縮短時(shí)間、減少成本，可以改善企業(yè)的生產(chǎn)效率。