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

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

1 引言

隨著客戶對(duì)產(chǎn)品的個(gè)性化和多樣化需求，產(chǎn)品種類日益增多，產(chǎn)品的生命周期日益減短。對(duì)于制造企業(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)資源和運(yùn)輸資源在時(shí)間上分配給若干生產(chǎn)任務(wù)，在滿足生產(chǎn)約束的前提下達(dá)到減少生產(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)化問題，對(duì)于大規(guī)模調(diào)度問題其計(jì)算量過大以至于無法求解。啟發(fā)式優(yōu)化是指通過問題建模，將沖壓車間調(diào)度問題轉(zhuǎn)化為最優(yōu)解搜索問題，常用的啟發(fā)式優(yōu)化算法包括粒子群算法、遺傳算法等，此類方法優(yōu)點(diǎn)是適用于大規(guī)模的車間調(diào)度優(yōu)化問題，缺點(diǎn)是調(diào)度方案的優(yōu)劣取決于啟發(fā)式算法的搜索性能。文獻(xiàn)[6]提出了改進(jìn)帝國主義競(jìng)爭(zhēng)算法，用于求解車間調(diào)度優(yōu)化問題，實(shí)現(xiàn)了最大完工時(shí)間的最小化。文獻(xiàn)[7]針對(duì)考慮序列依賴設(shè)置時(shí)間的沖壓車間調(diào)度優(yōu)化問題，將遺傳算法與智能搜索算法相結(jié)合，給出了基于混合算法的優(yōu)化求解方法。文獻(xiàn)[8]結(jié)合沖壓成產(chǎn)的能耗特性曲線，建立了完工時(shí)間最小、能耗最低的多目標(biāo)模型，使用多層編碼遺傳算法對(duì)模型進(jìn)行了求解，在減少完工時(shí)間的同時(shí)降低了生產(chǎn)能耗。文獻(xiàn)[9]對(duì)于柔性作業(yè)車間調(diào)度問題，以機(jī)器總負(fù)荷、完工時(shí)間等為優(yōu)化目標(biāo)，將和聲搜索算法引入到多目標(biāo)遺傳算法中并對(duì)優(yōu)化模型求解，得到了有效、可行的調(diào)度方案。當(dāng)前針對(duì)沖壓調(diào)度優(yōu)化的研究存在以下幾個(gè)問題：（1）大多針對(duì)傳統(tǒng)少品種大批量生產(chǎn)進(jìn)行研究，不能滿足當(dāng)前多品種少批量的個(gè)性化產(chǎn)品生產(chǎn)需要；（2）計(jì)算車間成本沒有考慮運(yùn)輸成本和換模成本等。

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

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

2.1 問題描述

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

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

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

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

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

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

2.2 問題建模

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

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

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

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

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

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

（2）同一時(shí)刻某機(jī)床只能加工一道工序，即：

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

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

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

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

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

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

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

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

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

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

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

圖3 工序交叉Fig.3 Procedure Crossover

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

圖4 機(jī)床交叉Fig.4 Machine Crossover

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

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

圖5 兩點(diǎn)變異Fig.5 Two Points Mutation

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

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

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

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

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

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

3.2 耦合選擇NSGA-II算法

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

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

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

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

圖7 兩點(diǎn)變異Fig.7 Two Points Mutation

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

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

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

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

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

4 實(shí)驗(yàn)驗(yàn)證及分析

4.1 實(shí)驗(yàn)設(shè)置

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

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

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

各機(jī)床之間的運(yùn)輸成本，如表3所示。

表3 機(jī)床間的運(yùn)輸成本（元）Tab.3 Transportation Cost Among Machines（yuan）

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

耦合選擇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)計(jì)，結(jié)果，如表4所示。

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

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

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

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

（1）消除量綱

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

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

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

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

（3）計(jì)算綜合評(píng)價(jià)

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

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

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

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

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

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

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

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

5 結(jié)論

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