多品種分批量沖壓車間的耦合選擇NSGA?II調(diào)度優(yōu)化

韓冰冰，王 雙，葛 楊，王 穎

（1.許昌職業(yè)技術(shù)學(xué)院機電與汽車工程學(xué)院，河南許昌 461000；2.鄭州大學(xué)機械學(xué)院，河南鄭州 450001；3.貴州商學(xué)院，貴州貴陽 550014）

1 引言

隨著客戶對產(chǎn)品的個性化和多樣化需求，產(chǎn)品種類日益增多，產(chǎn)品的生命周期日益減短。對于制造企業(yè)講，生產(chǎn)模式由連續(xù)大規(guī)模生產(chǎn)轉(zhuǎn)化為小批量、多種類生產(chǎn)。生產(chǎn)模式的轉(zhuǎn)變使得生產(chǎn)調(diào)度與控制更加復(fù)雜，而優(yōu)越的生產(chǎn)調(diào)度模式可以縮短生產(chǎn)周期、提高生產(chǎn)效率、降低生產(chǎn)成本[1]，因此研究沖壓車間的生產(chǎn)調(diào)度問題具有重要意義。

沖壓車間生產(chǎn)調(diào)度是指把車間有限的生產(chǎn)資源和運輸資源在時間上分配給若干生產(chǎn)任務(wù)，在滿足生產(chǎn)約束的前提下達到減少生產(chǎn)成本、縮短生產(chǎn)周期等目的[2]。根據(jù)優(yōu)化目標(biāo)的不同，可以將沖壓車間調(diào)度優(yōu)化問題劃分為生產(chǎn)成本最優(yōu)化、生產(chǎn)周期最優(yōu)化、換模次數(shù)最優(yōu)化、多目標(biāo)優(yōu)化等[3]。

從優(yōu)化方法角度劃分，沖壓車間調(diào)度優(yōu)化方法可以劃分為最優(yōu)化與啟發(fā)式優(yōu)化兩大類。最優(yōu)化方法包括枚舉法、數(shù)學(xué)規(guī)劃法[4]、拉氏松弛法[5]等，此類方法可以得到?jīng)_壓車間的最優(yōu)調(diào)度方案，但是只適用于小規(guī)模的調(diào)度優(yōu)化問題，對于大規(guī)模調(diào)度問題其計算量過大以至于無法求解。啟發(fā)式優(yōu)化是指通過問題建模，將沖壓車間調(diào)度問題轉(zhuǎn)化為最優(yōu)解搜索問題，常用的啟發(fā)式優(yōu)化算法包括粒子群算法、遺傳算法等，此類方法優(yōu)點是適用于大規(guī)模的車間調(diào)度優(yōu)化問題，缺點是調(diào)度方案的優(yōu)劣取決于啟發(fā)式算法的搜索性能。文獻[6]提出了改進帝國主義競爭算法，用于求解車間調(diào)度優(yōu)化問題，實現(xiàn)了最大完工時間的最小化。文獻[7]針對考慮序列依賴設(shè)置時間的沖壓車間調(diào)度優(yōu)化問題，將遺傳算法與智能搜索算法相結(jié)合，給出了基于混合算法的優(yōu)化求解方法。文獻[8]結(jié)合沖壓成產(chǎn)的能耗特性曲線，建立了完工時間最小、能耗最低的多目標(biāo)模型，使用多層編碼遺傳算法對模型進行了求解，在減少完工時間的同時降低了生產(chǎn)能耗。文獻[9]對于柔性作業(yè)車間調(diào)度問題，以機器總負(fù)荷、完工時間等為優(yōu)化目標(biāo)，將和聲搜索算法引入到多目標(biāo)遺傳算法中并對優(yōu)化模型求解，得到了有效、可行的調(diào)度方案。當(dāng)前針對沖壓調(diào)度優(yōu)化的研究存在以下幾個問題：（1）大多針對傳統(tǒng)少品種大批量生產(chǎn)進行研究，不能滿足當(dāng)前多品種少批量的個性化產(chǎn)品生產(chǎn)需要；（2）計算車間成本沒有考慮運輸成本和換模成本等。

這里針對多品種分批生產(chǎn)的沖壓車間調(diào)度問題，建立了沖壓車間調(diào)度的優(yōu)化目標(biāo)模型和約束條件模型，在NSGA?II算法中引入了耦合選擇策略，從而給出了耦合選擇NSGA?II算法的優(yōu)化方法，經(jīng)過優(yōu)化減少了沖壓車間的完工時間、加工成本和換模次數(shù)。

2 沖壓車間調(diào)度模型

2.1 問題描述

多種類分批量的離散型沖壓車間車間調(diào)度示意，如圖1所示。

圖1 車間調(diào)度示意圖Fig.1 Schematic Diagram of Workshop Scheduling

沖壓車間中有N種分批量的待加工工件，記為J1，J2，…，JN。每個工件具有若干道加工工序，工件Ji的第k道工序記為Oik。對同一工件來說，其工序的加工順序是預(yù)先確定的，且每道加工工序只有一套模具可用，這意味著不同批次的同一工件同一工序不能在時間上出現(xiàn)重疊。每套模具可以在不同沖壓機上進行加工。接下來對沖壓車間調(diào)度的已知條件、前提假設(shè)、優(yōu)化目標(biāo)進行明確。

已知條件：（1）工件類型、加工批量及數(shù)量；（2）每套模具可使用的機床集合；（3）每道工序在不同機床的加工時間、成本、換模時間等；（4）工件在機床間的運輸成本。

前提假設(shè)：（1）工件使用等量分批原則；（2）同一工件的工序已預(yù)先確定，不同工件間無加工優(yōu)先級；（3）同一批量的工件開始加工后不再間斷。

優(yōu)化目標(biāo)：通過為每套模具分配機床，并確定各工件各批次的加工時序，實現(xiàn)所有工件的完工時間最短、換模次數(shù)最少、加工成本最少等目標(biāo)。

2.2 問題建模

如前所述，這里以所有工件的最大完工時間最短、換模次數(shù)最少和車間能耗最低為優(yōu)化目標(biāo)。

（1）最大完工時間模型。最大完工時間是指在一個生產(chǎn)周期內(nèi)，從第一個工件加工開始，到最后一個工件完工為止所消耗的時間。其數(shù)學(xué)描述為：

（2）換模次數(shù)模型。此處的換模次數(shù)是指一個生產(chǎn)周期內(nèi)在所有機床上的換模次數(shù)總和，所有機床在0時刻的裝模設(shè)置為一次換模，則換模次數(shù)計算方法為：

（3）加工成本模型。沖壓車間的成本包括換模成本、沖壓成本和運輸成本，即：

根據(jù)生產(chǎn)實際，設(shè)置以下3個約束條件：

（1）同批次工件的同一工序只能在同一機床上加工，使用數(shù)學(xué)描述為：

（2）同一時刻某機床只能加工一道工序，即：

（3）任一批次工件的加工開始時間需大于上一批次工件的完工時間與換模時間之和，即：

綜合以上建模過程，得到?jīng)_壓車間調(diào)度模型為：

3 基于耦合選擇NSGA?II的調(diào)度優(yōu)化

3.1 傳統(tǒng)NSGA-II算法

NSGA?II算法是在遺傳算法基礎(chǔ)上加入非支配排序策略，使其適用于多目標(biāo)優(yōu)化問題[10]，其關(guān)鍵步驟包括染色體編碼、遺傳操作、解碼等。

（1）染色體編碼。染色體編碼方式是實際問題與算法的結(jié)合點，每條染色體表示一個可行解。這里針對沖壓車間調(diào)度問題，采用4基因鏈纏繞方式得到染色體，其中2基因鏈為自由變量，另外2基因鏈為非自由變量，不具備優(yōu)化意義，其設(shè)置只是為了便于解碼。以3個工件的4批次加工為例進行說明，加工任務(wù)，如表1所示。

表1 沖壓加工任務(wù)Tab.1 Stamping Task

染色體長度與工序總數(shù)一致，對于圖1中的加工任務(wù)，工件J1有2個加工批次，因此工序長度為6，工件J2、J3均有1個加工批次，工序長度分別為2、3，因此染色體長度為11。對于3工件4批次加工任務(wù)，染色體使用十進制編碼，4基因鏈包括工序編碼、機床編碼、加工時間編碼和加工成本編碼，如圖2所示。

圖2 染色體編碼方式Fig.2 Chromosome Coding Mode

圖2中工序編碼和機床編碼為自由變量，可進行優(yōu)化，加工時間、加工成本為非自由變量，根據(jù)工序和機床共同確定。工序編碼解釋為：編碼1表示工件J1的第一批次，編碼2表示工件J1的第二批次，編碼3表示工件J2的加工批次，編碼4表示工件J3的加工批次。

在工序編碼中，1出現(xiàn)了3次，分別表示第一批次工件J1的工序O11、O12、O13，工序中其余編碼與此含義一致。以第一基因位為例對4條基因鏈進行釋義：工件2的第1工序在機床3上加工，加工時間為12s，加工成本為37元/h。

（2）染色體初始化。染色體以隨機方式進行初始化，隨機包括工序編碼隨機和機床編碼隨機。

實現(xiàn)方法為：首先生成一組可行的工序編碼，隨機生成對應(yīng)的可用機床；將工序編碼進行打亂并隨機排序，而后隨機生成對應(yīng)的可用機床，重復(fù)以上過程，直至獲得設(shè)定規(guī)模的染色體。

（3）染色體交叉。染色體交叉包括工序交叉和機床交叉2種方式，這里以隨機方式選擇一種交叉方式執(zhí)行。工序交叉為將父代1和父代2的工序進行交叉，相應(yīng)的機床保持不變，如圖3所示。

圖3中將編碼2作為固定位，其余編碼按照順序依次交叉。由于染色體工序編碼和機床編碼位自由變量，因此只給出了工序編碼和機床編碼。

圖3 工序交叉Fig.3 Procedure Crossover

機床交叉方法為：首先產(chǎn)生｛1，2，3，4｝的真子集，根據(jù)子集中的編碼將相應(yīng)的機床進行交叉。假如某次產(chǎn)生的子集為{4}，則機床交叉，如圖4所示。

圖4 機床交叉Fig.4 Machine Crossover

（4）染色體變異。以圖2的編碼為例對染色體變異方法進行介紹，從11 個基因位中產(chǎn)生兩個隨機數(shù)n1，n2∈[]1，11，且n1n2。將n1和n2對應(yīng)的工序進行兩點變異，得到中間子代。

為了防止出現(xiàn)非法解，需要檢查中間子代的工序順序，當(dāng)交叉引起工序順序變化時，將其機床按原編碼順序進行調(diào)整，從而得到合法的子代，以上過程，如圖5所示。

圖5 兩點變異Fig.5 Two Points Mutation

在圖5中將第4基因位和第8基因位的工序碼交換，交換后發(fā)現(xiàn)編碼“4”的工序順序未變化，而編碼“2”的工序順序發(fā)生了變化。因此將父代中編碼“2”對應(yīng)的機床“3、1、4”依次填入到工序碼“2”對應(yīng)位置，得到子代。

（5）選擇策略。傳統(tǒng)NSGA?II 算法依據(jù)非支配排序和擁擠度進行選擇，非支配排序方法和擁擠度計算方法可參考文獻[11]，這里不再贅述。

傳統(tǒng)NSGA?II 算法首先依據(jù)非支配層進行染色體篩選，而后依據(jù)擁擠度進行選擇，使染色體規(guī)模保持恒定[12]。

（6）染色體解碼。根據(jù)算法得到的優(yōu)化解，對其解碼得到?jīng)_壓車間成產(chǎn)的甘特圖，以圖2所示的染色體編碼為例，將換模時間全部設(shè)置為30min，其對應(yīng)的機床甘特圖，如圖6所示。

圖6 圖1對應(yīng)的甘特圖Fig.6 Gantt Chart of Figure 1

（7）算法結(jié)束。當(dāng)算法迭代次數(shù)達到最大次數(shù)時，算法結(jié)束，輸出全局最優(yōu)解。

3.2 耦合選擇NSGA-II算法

分析傳統(tǒng)NSGA?II 算法染色體選擇方法可知，染色體選擇首先依據(jù)非支配排序，而后依據(jù)擁擠度選擇染色體，這種方法意味著擁擠度只能作用于最后一個非支配層，不利于染色體整體的多樣性。

針對這一問題，這里提出了染色體的二元耦合選擇方法，其核心思想為：根據(jù)非支配層排序，自適應(yīng)確定每層需刪除的染色體數(shù)量，而后根據(jù)擁擠度從每個支配層中刪除擁擠度值小的染色體。

非支配層數(shù)量記為M，非支配層編號記為m，遺傳操作后染色體超出設(shè)定規(guī)模的數(shù)量記為Qd，則支配層m需舍棄的染色體數(shù)量為：

分析式（8）可知，本節(jié)提出的耦合選擇方法使擁擠度作用于每個非支配層，可以更有效提高染色體多樣性和算法優(yōu)化能力，以從2個支配層的20個染色體中選擇14個為例，耦合選擇策略與傳統(tǒng)選擇策略的對比效果，如圖7所示。

圖7 兩點變異Fig.7 Two Points Mutation

在圖7中，按照傳統(tǒng)選擇策略在第2非支配層中刪除6個染色體。

按照耦合選擇策略，依據(jù)式（8）在第1非支配層刪除2個染色體，第2非支配層中刪除4個染色體。從結(jié)果可直觀看出，耦合選擇方法的染色體分布均勻性（也即多樣性）更好。

3.3 基于耦合選擇NSGA-II算法的求解流程

根據(jù)以上對耦合NSGA?II 算法的描述，制定基于耦合選擇NSGA?II算法的沖壓車間優(yōu)化流程，如圖8所示。

圖8 優(yōu)化流程Fig.8 Flow of Optimization

4 實驗驗證及分析

4.1 實驗設(shè)置

以某汽車生產(chǎn)的沖壓車間調(diào)度優(yōu)化為例進行驗證，在某一生產(chǎn)周期內(nèi)該車間需生產(chǎn)4種工件，每種工件均生產(chǎn)2批，可用的機床為6臺，各工件的工序、可用機床、生產(chǎn)時間、生產(chǎn)時間及相應(yīng)的模具，如表2所示。另外，將換模時間統(tǒng)一設(shè)置為30min，換模一次的成本為20元。

表2 沖壓任務(wù)及條件Tab.2 Stamping Task and its Condition

表中：“—”表示此機床無法加工此工序；“8/46”—機床M1加工工序O11的單件時間為8s，單價加工成本為46元/h，其余數(shù)據(jù)與此數(shù)據(jù)含義一致。

各機床之間的運輸成本，如表3所示。

表3 機床間的運輸成本（元）Tab.3 Transportation Cost Among Machines（yuan）

4.2 耦合選擇NSGA-II與傳統(tǒng)NSGA-II對比分析

耦合選擇NSGA?II算法的參數(shù)設(shè)置為：染色體規(guī)模為200，迭代次數(shù)為100，交叉概率為0.45，變異概率為0.05。使用耦合選擇NSGA?II算法得到的Pareto解集，如圖9所示。

圖9 Pareto解集Fig.9 Pareto Solutions

按照相同的參數(shù)設(shè)置，使用傳統(tǒng)NSGA?II 算法同樣可以獲得一組Pareto解集，將耦合選擇NSGA?II算法與傳統(tǒng)NSGA?II算法得到的Pareto解集分別統(tǒng)計，結(jié)果，如表4所示。

表4 兩種NSGA-II算法的搜索結(jié)果Tab.4 Searching Result of Two NSGA-II Algorithms

由表4 中的統(tǒng)計數(shù)據(jù)可以看出，耦合選擇NSGA?II 算法的Pareto解集中解的質(zhì)量高于傳統(tǒng)NSGA?II算法，耦合選擇NSGA?II算法得到的3個目標(biāo)參數(shù)最大值、最小值和均值全部小于傳統(tǒng)NSGA?II算法，這是因為傳統(tǒng)NSGA?II算法的選擇機制沒有考慮到染色體多樣性問題，而耦合選擇NSGA?II算法的選擇機制交替使用支配層和擁擠度作為參考，兼顧了染色體多樣性和優(yōu)劣性，因此耦合選擇NSGA?II 算法Pareto 解集質(zhì)量高于傳統(tǒng)NSGA?II算法。

4.3 耦合選擇NSGA-II優(yōu)化方案與當(dāng)前方案對比

使用線性加權(quán)法從耦合選擇NSGA?II算法優(yōu)化的Pareto解集中選擇一個最優(yōu)解，分為3 步實現(xiàn)，分別為消除量綱、確定權(quán)重、計算綜合評價。

（1）消除量綱

各目標(biāo)參數(shù)的量綱不同，難以進行有效的比較，因此首先需要消除量綱。對于M個目標(biāo)參數(shù)，每個目標(biāo)有N個解，則參數(shù)序列{dmn}采用極差法消除參數(shù)量綱，為：

式中：emn—目標(biāo)參數(shù)m的第n個解消除量綱后的值；dmn—目標(biāo)參數(shù)m的第n個解消除量綱前的值；dmmax—目標(biāo)參數(shù)m的最大值；dmmin—目標(biāo)參數(shù)m的最小值。

（2）確定權(quán)重

這里將3 個目標(biāo)參數(shù)設(shè)置為相同權(quán)重，即w1=0.33、w2=0.33、w3=0.34。

（3）計算綜合評價

根據(jù)各參數(shù)權(quán)重和去量綱后的參數(shù)值，計算第n個解的綜合評價為：

式中：Sn—第n個解的綜合評價值。根據(jù)這里的優(yōu)化目標(biāo)，Sn取得最小值對應(yīng)的解即為最優(yōu)解。

按照以上步驟，從Pareto解集中獲得最優(yōu)解，染色體解碼后得到機床甘特圖，如圖10所示。

圖10 優(yōu)化后的機床甘特圖Fig.10 Machine Gant Chart After Optimization

沖壓車間當(dāng)前的沖壓方案根據(jù)批次順序確定的，即按照工件順序加工完一批后再加工第二批，機床甘特圖，如圖11所示。

圖11 優(yōu)化前的機床甘特圖Fig.11 Machine Gant Chart Before Optimization

統(tǒng)計優(yōu)化前后沖壓車間的換模次數(shù)、加工成本和最大完工時間，對比結(jié)果，如圖12所示。優(yōu)化前換模次數(shù)為23次，加工成本為2050元，最大完工時間為15.86h。優(yōu)化后換模次數(shù)為11次，加工成本為1672元，最大完工時間為9.52h，比優(yōu)化前分別減少了52.2%、18.4%、40.0%。以上結(jié)果說明耦合選擇NSGA?II算法可以對沖壓車間調(diào)度進行有效優(yōu)化，減少了加工時間、加工成本和換模次數(shù)。

圖12 優(yōu)化結(jié)果對比Fig.12 Comparison of Optimization Result

5 結(jié)論

這里研究了多品種分批生產(chǎn)的沖壓車間調(diào)度優(yōu)化問題，建立了沖壓調(diào)度優(yōu)化模型，提出了耦合選擇NSGA?II 算法的優(yōu)化方法，經(jīng)驗證得出以下結(jié)論：（1）與傳統(tǒng)NSGA?II算法比，耦合選擇NSGA?II 算法的選擇策略能夠兼顧染色體的多樣性和優(yōu)越性，其Pareto解集質(zhì)量高于傳統(tǒng)NSGA?II算法；（2）與當(dāng)前沖壓方案比，優(yōu)化后的沖壓調(diào)度方案有效減少了完工時間、加工成本和換模次數(shù)。