李　言　巴　黎　曹　源　劉　永　楊明順

西安理工大學(xué)，西安，710048

考慮多目標(biāo)的工藝規(guī)劃與調(diào)度集成問(wèn)題研究

李言巴黎曹源劉永楊明順

西安理工大學(xué)，西安，710048

針對(duì)工藝規(guī)劃與調(diào)度集成問(wèn)題在多目標(biāo)優(yōu)化方面的不足，考慮將多目標(biāo)優(yōu)化集成到工藝規(guī)劃與調(diào)度集成問(wèn)題中。以最長(zhǎng)完工時(shí)間、加工成本及設(shè)備最大負(fù)載為優(yōu)化目標(biāo)，對(duì)該多目標(biāo)工藝規(guī)劃與調(diào)度集成問(wèn)題進(jìn)行建模，并提出了一種非支配排序遺傳算法，鑒于加工信息的多樣性，使用多層結(jié)構(gòu)表示可行解，對(duì)該算法的選擇及遺傳操作等步驟進(jìn)行了設(shè)計(jì)。最后，以實(shí)例驗(yàn)證了上述模型的正確性及算法的有效性。

工藝規(guī)劃與調(diào)度集成；多目標(biāo)；非支配排序遺傳算法；選擇操作

0　引言

工藝規(guī)劃與調(diào)度作為生產(chǎn)系統(tǒng)中極為重要的兩個(gè)子系統(tǒng)，往往以獨(dú)立、串行的模式運(yùn)行[1-3]。在產(chǎn)品設(shè)計(jì)階段，工藝規(guī)劃指定工件從毛坯至成品所需的原材料、機(jī)床及加工路線；在調(diào)度階段，調(diào)度系統(tǒng)將根據(jù)工藝規(guī)劃獲得的結(jié)果，對(duì)各加工資源進(jìn)行調(diào)度[3]。這種相互獨(dú)立、串行的運(yùn)行方式，易導(dǎo)致工藝路線不切合實(shí)際、資源利用不均、產(chǎn)生調(diào)度瓶頸等問(wèn)題[1-3]。

近年來(lái)，工藝規(guī)劃與調(diào)度集成(integrated process planning and scheduling，IPPS)逐漸成為國(guó)內(nèi)外學(xué)者們的研究熱點(diǎn)。工藝規(guī)劃與調(diào)度的集成，對(duì)于消除資源沖突、減少工件流通時(shí)間、提高設(shè)備利用率、縮短產(chǎn)品制造周期等具有重要意義[1-2]。

當(dāng)前，針對(duì)IPPS問(wèn)題的相關(guān)研究集中在理論研究、集成模型、算法改進(jìn)等方面。理論研究方面，文獻(xiàn)[1-2]指出了單獨(dú)考慮工藝規(guī)劃與調(diào)度所導(dǎo)致的多種問(wèn)題及局限性，介紹了目前解決靜態(tài)及動(dòng)態(tài)IPPS的多種方法，給出了工藝規(guī)劃與車間調(diào)度以及兩者集成研究的發(fā)展方向。集成模型方面，文獻(xiàn)[3]提出了一種基于代理的IPPS方法，將IPPS問(wèn)題涉及的工件、機(jī)器及求解算法以Agent的形式進(jìn)行封裝，提出了一種基于Agent的IPPS系統(tǒng)；文獻(xiàn)[4]提出了一種由初始規(guī)劃層、匹配規(guī)劃層及詳細(xì)規(guī)劃層組成的三層結(jié)構(gòu)IPPS復(fù)合式集成模型，并通過(guò)一個(gè)應(yīng)用實(shí)例對(duì)該模型進(jìn)行了驗(yàn)證；文獻(xiàn)[5]提出了一種由工藝規(guī)劃選擇模塊、調(diào)度模塊、調(diào)度分析模塊及工藝路線修正模塊組成的IPPS模型，提出一種遺傳算法對(duì)IPPS問(wèn)題進(jìn)行了求解。算法改進(jìn)方面，文獻(xiàn)[6]針對(duì)IPPS問(wèn)題，以最長(zhǎng)完工時(shí)間(makespan)為優(yōu)化目標(biāo)，提出一種基于遺傳算法和禁忌搜索的混合算法，并以多個(gè)算例對(duì)該算法進(jìn)行了驗(yàn)證；文獻(xiàn)[7]針對(duì)IPPS問(wèn)題，分別建立了makespan、加工成本等因素的數(shù)學(xué)優(yōu)化模型，提出了一種基于進(jìn)化算法的求解方法，最后，以多個(gè)實(shí)例對(duì)所建模型及算法進(jìn)行了驗(yàn)證；文獻(xiàn)[8]針對(duì)以makespan為優(yōu)化目標(biāo)的IPPS問(wèn)題，提出了一種主動(dòng)學(xué)習(xí)遺傳算法，并以多個(gè)實(shí)例驗(yàn)證了該算法的有效性；文獻(xiàn)[9]針對(duì)IPPS問(wèn)題，使用與或圖表示各工件的各道工序以及各工序間的關(guān)系，提出了一種改進(jìn)蟻群算法，并通過(guò)大量實(shí)例對(duì)該算法進(jìn)行了驗(yàn)證；文獻(xiàn)[10]針對(duì)IPPS問(wèn)題，提出一種將遺傳算法與人工神經(jīng)網(wǎng)絡(luò)結(jié)合的混合啟發(fā)式算法，并以多個(gè)算例對(duì)該算法進(jìn)行了驗(yàn)證。

目前，針對(duì)IPPS問(wèn)題進(jìn)行建模與求解的相關(guān)文獻(xiàn)，大多以makespan作為優(yōu)化目標(biāo)。實(shí)際生產(chǎn)中，企業(yè)由多個(gè)不同職能的部門組成，由于各部門對(duì)生產(chǎn)調(diào)度的期望有所不同，且各期望目標(biāo)可能存在相互沖突[11]，若僅以makespan為優(yōu)化目標(biāo)，難以符合實(shí)際的生產(chǎn)調(diào)度情況。

將多目標(biāo)優(yōu)化與生產(chǎn)調(diào)度問(wèn)題相結(jié)合，形成了多種多目標(biāo)生產(chǎn)調(diào)度問(wèn)題，如：多目標(biāo)柔性作業(yè)車間調(diào)度問(wèn)題(multi-objective flexible job-shop scheduling problem，MOFJSP)[11-18]、多目標(biāo)作業(yè)車間調(diào)度問(wèn)題(multi-objective job-shop scheduling problem，MOJSP)[19]、多目標(biāo)流水作業(yè)調(diào)度問(wèn)題(multi-objective flow-shop scheduling problem，MOFSP)[20]、多目標(biāo)并行機(jī)調(diào)度問(wèn)題(multi-objective parallel machine scheduling problem，MOPMSP)[21]、多目標(biāo)開(kāi)放作業(yè)調(diào)度問(wèn)題(multi-objective open shop scheduling problem，MOOSSP)[22]等。

考慮多目標(biāo)優(yōu)化的生產(chǎn)調(diào)度問(wèn)題的相關(guān)文獻(xiàn)大多為作業(yè)車間調(diào)度(job-shop scheduling problem，JSP)、流水作業(yè)調(diào)度(flow-shop scheduling problem，F(xiàn)SP)問(wèn)題。隨著制造技術(shù)的不斷改進(jìn)與提升，一方面，大多數(shù)車間存在多種功能相似的設(shè)備共存的狀況[23]；另一方面，由于加工手段和技術(shù)的多樣性，工件已不再拘泥于單一工藝路線[1]。IPPS問(wèn)題同時(shí)具有并行機(jī)環(huán)境及復(fù)合工藝路線特點(diǎn)，相較于JSP、FSP等通常的調(diào)度問(wèn)題，該問(wèn)題的求解空間更大、復(fù)雜度更高，其調(diào)度結(jié)果也更加符合實(shí)際的生產(chǎn)情況，已被認(rèn)定為NP困難問(wèn)題[6-7]。

筆者在上述文獻(xiàn)的基礎(chǔ)上，同時(shí)考慮makespan、加工成本及設(shè)備最大負(fù)載3個(gè)優(yōu)化目標(biāo)，提出一種多目標(biāo)IPPS(multi-objective integrated process planning and scheduling，MOIPPS)問(wèn)題，建立該問(wèn)題的數(shù)學(xué)模型，并設(shè)計(jì)相應(yīng)的求解算法，最后，以一個(gè)實(shí)例對(duì)模型及算法進(jìn)行驗(yàn)證。

1　問(wèn)題建模

基于上述參數(shù)，分別以makespan最小、加工成本最小及設(shè)備最大負(fù)載最小為優(yōu)化目標(biāo)，建立目標(biāo)函數(shù)如下。

makespan最?。?/p>

(1)

加工成本最低：

(2)

設(shè)備最大負(fù)載最?。?/p>

(3)

針對(duì)本文所研究的問(wèn)題，考慮以下約束：

(4)

(5)

(6)

根據(jù)約束(3)，更新各相關(guān)參數(shù)如下：

(1)工件i的第v″道工序的完工時(shí)間為

(7)

(2)加工設(shè)備j的可開(kāi)工時(shí)間為

(8)

(9)

2　算法設(shè)計(jì)

由上述建模過(guò)程可知，MOIPPS問(wèn)題屬NP困難問(wèn)題。Deb等[24]在2002年提出一種針對(duì)多目標(biāo)優(yōu)化的非支配排序遺傳算法(non-dominated sorting genetic algorithm-Ⅱ，NSGA-Ⅱ)，該算法被廣泛用于各種多目標(biāo)優(yōu)化問(wèn)題的求解[19]。

本文提出一種適用于MOIPPS問(wèn)題的非支配排序遺傳算法，由于MOIPPS問(wèn)題的復(fù)雜性及離散性，需要對(duì)算法的一些關(guān)鍵模塊進(jìn)行設(shè)計(jì)。

2.1編碼

由于MOIPPS問(wèn)題加工信息的多樣性，為便于后續(xù)的遺傳操作，本文提出一種6層編碼結(jié)構(gòu)，將加工所需的所有信息集成到該結(jié)構(gòu)當(dāng)中，對(duì)調(diào)度方案進(jìn)行編碼。該結(jié)構(gòu)由工件層、機(jī)器層、加工時(shí)間層、加工成本層、加工方法層及工藝路線層組成。其中，工件層為各工件的編碼；機(jī)器層為各加工設(shè)備的編碼；加工時(shí)間層為機(jī)器對(duì)應(yīng)不同工序的加工時(shí)間；加工成本層為機(jī)器對(duì)應(yīng)不同工序的加工成本；加工方法層為工件各道工序?qū)?yīng)的加工方法；工藝路線層為不同工件對(duì)應(yīng)的工藝路線編碼。

基于上述定義，以3種工件、3臺(tái)機(jī)器的MOIPPS問(wèn)題為例，其編碼示例如表1所示。

表1　MOIPPS問(wèn)題編碼示例

表1中，第1列的碼值表示工件2采用工藝路線4進(jìn)行加工，由于工件編碼2第1次出現(xiàn)在工件層，即代表該工件的第1道工序，其第1道工序的加工方法為2，由機(jī)器3加工，加工時(shí)間為3.6 h，加工成本為30元/h。以此類推。

2.2解碼

采用半主動(dòng)解碼對(duì)各解進(jìn)行解碼，假設(shè)編碼長(zhǎng)度為l，具體解碼步驟如下：

(1)初始化計(jì)數(shù)器i=1；

(2)提取當(dāng)前解的編碼中位于第i列上的數(shù)據(jù)；

(3)若該列對(duì)應(yīng)工件層上的編碼值在工件層中第s次出現(xiàn)，則代表該工件的第s道工序；

(4)根據(jù)第i列中的數(shù)據(jù)，以及建模中的約束條件，記錄該工件第s道工序?qū)?yīng)的加工時(shí)間區(qū)間；

(5)i←i+1，若i>l，則表示各工件各道工序的加工時(shí)間區(qū)間已確定，轉(zhuǎn)至步驟(6)；否則，轉(zhuǎn)至步驟(2)；

(6)根據(jù)各工件各道工序的加工時(shí)間區(qū)間，獲得makespan及設(shè)備最大負(fù)載；

(7)根據(jù)各工件各道工序的加工時(shí)間區(qū)間及機(jī)器的加工成本，獲得該解對(duì)應(yīng)的加工成本。

至此，一次解碼操作完畢。

2.3選擇操作

本文首先結(jié)合Pareto支配關(guān)系，對(duì)各解進(jìn)行分層操作，得到各解對(duì)應(yīng)的前沿層級(jí)；其次，計(jì)算各解的擁擠度；最后，結(jié)合偏序關(guān)系，使用錦標(biāo)賽選擇法對(duì)種群進(jìn)行選擇操作。

2.3.1分層操作

進(jìn)行分層操作前，首先定義Pareto支配關(guān)系[22]：對(duì)于具有N個(gè)優(yōu)化目標(biāo)的多目標(biāo)最小化問(wèn)題，假設(shè)某解集P由M個(gè)個(gè)體組成，P={x1，x2，…，xM}，對(duì)于任意解xi，對(duì)應(yīng)第j個(gè)目標(biāo)的目標(biāo)值為fj(xi)，則解xu支配解xv需同時(shí)滿足以下條件：①對(duì)于任意目標(biāo)值fk，滿足fk(xu)≤fk(xv)；②?k′，滿足fk′(xu)

由上述Pareto支配關(guān)系的定義可知，對(duì)于多目標(biāo)最小化問(wèn)題，若解xu支配解xv，則解xu優(yōu)于解xv。

假設(shè)種群P={x1，x2，…，xM}，對(duì)應(yīng)層級(jí)集合RANK={rank1，rank2，…，rankM}，被支配數(shù)集合DN={dn1，dn2，…，dnM}，初始化rankh=-1，dnh=0，h=1,2,…,M。分層操作步驟如下：

(1)初始化層級(jí)計(jì)數(shù)器w=1；

(2)針對(duì)種群P，按照上述Pareto支配關(guān)系，確定P中每個(gè)個(gè)體的被支配數(shù)；

(3)對(duì)于P中被支配數(shù)為0的個(gè)體，將w賦值給這些個(gè)體對(duì)應(yīng)的層級(jí)；

(4)刪去P中層級(jí)為w的個(gè)體，w←w+1，若此時(shí)P非空，令剩余個(gè)體的被支配數(shù)為0，轉(zhuǎn)至步驟(2)，否則，P中所有個(gè)體的層級(jí)被確定。

2.3.2擁擠度計(jì)算

除前沿層級(jí)外，擁擠度是比較個(gè)體優(yōu)劣的另一個(gè)重要指標(biāo)。若兩個(gè)相比較的個(gè)體所屬層級(jí)相同，為保持種群多樣性，一般認(rèn)為擁擠度較大的個(gè)體為較優(yōu)個(gè)體[24]。

對(duì)于上述最小化問(wèn)題，假設(shè)擁擠度集合CD={cd1，cd2，…，cdM}，則個(gè)體xi對(duì)應(yīng)擁擠度cdi的計(jì)算按照以下步驟進(jìn)行：

(1)初始化計(jì)數(shù)器j=1；

(2)根據(jù)種群P中個(gè)體對(duì)應(yīng)第j個(gè)目標(biāo)的目標(biāo)值fj，將種群P中的個(gè)體由小到大排列；

(3)若xi排在第1位或末位，置cdi為一個(gè)絕對(duì)大的數(shù)值，跳轉(zhuǎn)至步驟(9)；否則，跳轉(zhuǎn)至步驟(4)；

(4)找到經(jīng)過(guò)排序后，排在xi前一位和后一位的個(gè)體，假設(shè)分別為xfront、xbehind；

(5)找到對(duì)應(yīng)fj值最大和最小的兩個(gè)個(gè)體，假設(shè)分別為xmax、xmin；

(6)計(jì)算xi對(duì)應(yīng)第j個(gè)目標(biāo)的擁擠度，即

cdfij=(fj(xbehind)-fj(xfront))/(fj(xmax)-fj(xmin))

(10)

(7)j←j+1，若j>N，跳轉(zhuǎn)至步驟(8)，否則，跳轉(zhuǎn)至步驟(2)；

(8)計(jì)算xi的擁擠度，即

(11)

(9)計(jì)算結(jié)束，得到cdi。

2.3.3錦標(biāo)賽選擇

在進(jìn)行錦標(biāo)賽選擇前，首先定義偏序關(guān)系[24]：對(duì)于具有N個(gè)優(yōu)化目標(biāo)的多目標(biāo)最小化問(wèn)題，假設(shè)某解集P由M個(gè)個(gè)體組成，解xu、xv對(duì)應(yīng)的前沿層級(jí)分別為ranku、rankv，對(duì)應(yīng)的擁擠度分別為cdu、cdv，定義偏序符號(hào)為“”，則xuxv需滿足條件rankucdv。u，v=1,2,…,M。

由上述可知，若xuxv，則解xu優(yōu)于xv。

假設(shè)種群規(guī)模為M，競(jìng)賽個(gè)體總數(shù)為CN(CN

(1)從種群中隨機(jī)選擇CN個(gè)個(gè)體；

(2)依照上述偏序關(guān)系的定義，從該CN個(gè)個(gè)體中選出最優(yōu)個(gè)體作為一個(gè)預(yù)交叉?zhèn)€體；

(3)重新從種群中隨機(jī)選擇CN個(gè)個(gè)體；

(4)依照上述偏序關(guān)系的定義，從該CN個(gè)個(gè)體中選出最優(yōu)個(gè)體作為另一個(gè)預(yù)交叉?zhèn)€體。

2.4交叉操作

本文使用POX交叉(precedence operation crossover，POX)對(duì)多層編碼結(jié)構(gòu)的個(gè)體進(jìn)行交叉。以2種工件、3臺(tái)機(jī)器的MOIPPS問(wèn)題為例，假設(shè)要交叉的工件為工件2，POX交叉如圖1所示。

圖1　MOIPPS問(wèn)題的POX交叉操作

由于不同父代中相同工件可能選擇不同的工藝路線，可能會(huì)出現(xiàn)同一工件在不同父代中工序數(shù)不同的情況，因此，交叉后所產(chǎn)生的新個(gè)體的編碼長(zhǎng)度會(huì)有所變化，如圖1所示。

2.5變異操作

本文采用兩種變異方法，一種是依照Swap互換操作概率對(duì)某兩列編碼進(jìn)行Swap互換操作，另一種是依照機(jī)器層單點(diǎn)變異概率對(duì)機(jī)器層進(jìn)行單點(diǎn)變異操作。假設(shè)個(gè)體變異概率為Pm、Swap互換操作概率為Pm1、機(jī)器層單點(diǎn)變異概率為Pm2，變異操作的流程圖如圖2所示。

圖2　變異操作流程

由于在進(jìn)行Swap互換操作后所產(chǎn)生的新解可能出現(xiàn)同一工件的后道工序排在前道工序之前的情況，即產(chǎn)生非法解，因而，在Swap互換操作后，將對(duì)該個(gè)體中的非法編碼部分進(jìn)行修正，以得到合法解。假設(shè)工件J2選擇工藝路線4進(jìn)行加工，J2共有3道工序，各工序的加工方法依次為4→5→6，隨機(jī)產(chǎn)生兩互換位置，分別為1、4，則Swap互換操作及修正操作的示例如圖3所示。

圖3　Swap互換操作及修正操作示例

2.6Pareto解集構(gòu)建

多目標(biāo)優(yōu)化問(wèn)題很少存在絕對(duì)的最優(yōu)解[14]，對(duì)于多目標(biāo)優(yōu)化算法，其求解結(jié)果往往是一個(gè)Pareto解集。假設(shè)種群規(guī)模為M，迭代次數(shù)為D，初代種群為P，通過(guò)以下步驟對(duì)Pareto解集進(jìn)行構(gòu)建。

(1)初始化Pareto解集，命名為PA，且PA為空集，迭代次數(shù)計(jì)數(shù)器e←0；

(2)對(duì)初代種群P的個(gè)體進(jìn)行分層操作，并計(jì)算每個(gè)個(gè)體的擁擠度；

(3)對(duì)種群P進(jìn)行選擇、交叉及變異操作，形成下一代種群P′；

(4)建立臨時(shí)種群Q，Q=P∪P′；

(5)對(duì)種群Q中的個(gè)體進(jìn)行分層操作，并計(jì)算每個(gè)個(gè)體的擁擠度；

(6)將種群Q中前沿層級(jí)為1的個(gè)體與集合PA中的個(gè)體比較，將不重復(fù)的個(gè)體添加到PA；

(7)e←e+1，若e≤D，跳轉(zhuǎn)至步驟(8)；否則，跳轉(zhuǎn)至步驟(9)；

(8)選出種群Q中排名前M的個(gè)體，構(gòu)成新的父代P，跳轉(zhuǎn)至步驟(3)；

(9)對(duì)集合PA進(jìn)行分層操作，刪除前沿層級(jí)大于1的個(gè)體，形成最終Pareto解集。

2.7算法參數(shù)說(shuō)明及算法流程圖

M為種群規(guī)模，控制種群中個(gè)體的數(shù)量；CN為競(jìng)賽個(gè)體總數(shù)，為定值，CN

結(jié)合上述對(duì)算法的描述，可獲得非支配排序遺傳算法的流程圖，如圖4所示。

圖4　求解MOIPPS問(wèn)題的NSGA-Ⅱ算法流程

3　實(shí)例分析

3.1實(shí)例說(shuō)明

某企業(yè)有一筆訂單，共有8種不同工件(J1，J2，…，J8)需要加工，有8臺(tái)加工設(shè)備(M1，M2，…，M8)，8種加工方法(P1,P2,…,P8)，16條工藝路線(R1,R2,…,R16)。以makespan最小、加工成本最低及設(shè)備最大負(fù)載最小為優(yōu)化目標(biāo)，使用上述算法對(duì)該問(wèn)題進(jìn)行求解。各工件對(duì)應(yīng)的工藝路線及加工參數(shù)分別如表2～表9所示，各設(shè)備的加工成本如表10所示。

表2　工件J1對(duì)應(yīng)的工藝路線及加工參數(shù)

表3　工件J2對(duì)應(yīng)的工藝路線及加工參數(shù)

表4　工件J3對(duì)應(yīng)的工藝路線及加工參數(shù)

表5　工件J4對(duì)應(yīng)的工藝路線及加工參數(shù)

表6　工件J5對(duì)應(yīng)的工藝路線及加工參數(shù)

表7　工件J6對(duì)應(yīng)的工藝路線及加工參數(shù)

表8　工件J7對(duì)應(yīng)的工藝路線及加工參數(shù)

表9　工件J8對(duì)應(yīng)的工藝路線及加工參數(shù)

表10　各設(shè)備的加工成本

3.2假設(shè)條件

作如下假設(shè)：①所有加工設(shè)備從零時(shí)刻起均為空閑狀態(tài)；②工件嚴(yán)格按照工藝順序加工；③允許工件在工序之間等待，允許機(jī)器在工件未到達(dá)時(shí)閑置；④設(shè)備不出現(xiàn)故障。

3.3求解結(jié)果與分析

取D=1000、M=100、CN=2、Pc=0.8、Pm=0.1、Pm1=0.5、Pm2=0.5。使用C#語(yǔ)言實(shí)現(xiàn)算法編寫(xiě)，在CPU 1.81 GHz、RAM 2 GB的PC主機(jī)上運(yùn)行。算法耗時(shí)293 s，Pareto解集中解的個(gè)數(shù)為62，各解的分布情況如圖5所示。

圖5　Pareto解集中各解的分布情況

對(duì)Pareto解集中的解對(duì)應(yīng)的各目標(biāo)值進(jìn)行統(tǒng)計(jì)，如表11所示。

表11　Pareto解集中的解對(duì)應(yīng)各目標(biāo)值的統(tǒng)計(jì)結(jié)果

分別以makespan、加工成本及設(shè)備最大負(fù)載為單優(yōu)化目標(biāo)，各迭代計(jì)算50次，獲得50次迭代計(jì)算中對(duì)應(yīng)優(yōu)化目標(biāo)值最優(yōu)的解，各最優(yōu)解對(duì)應(yīng)的目標(biāo)值如表12所示。

表12　單目標(biāo)優(yōu)化所得最優(yōu)解對(duì)應(yīng)的目標(biāo)值匯總

以下分別從僅優(yōu)化makespan、僅優(yōu)化加工成本及僅優(yōu)化設(shè)備最大負(fù)載三個(gè)方面，對(duì)表11及表12的求解結(jié)果進(jìn)行分析。

(1)僅以makespan為優(yōu)化目標(biāo)。當(dāng)僅以makespan為優(yōu)化目標(biāo)時(shí)，對(duì)應(yīng)makespan為17.1 h，優(yōu)于Pareto解集中對(duì)應(yīng)的最低makespan。但由于僅以makespan為優(yōu)化目標(biāo)，導(dǎo)致了高額的加工成本，為3598.0元，高于Pareto解集中對(duì)應(yīng)的最高加工成本。

(2)僅以加工成本為優(yōu)化目標(biāo)。若僅以加工成本為優(yōu)化目標(biāo)，迭代計(jì)算時(shí)會(huì)優(yōu)先選取加工成本較低的工序，提高了這些工序?qū)?yīng)設(shè)備的使用頻率；而一些加工成本較高的設(shè)備，其使用頻率則相應(yīng)較低，導(dǎo)致資源利用不均。僅以加工成本為優(yōu)化目標(biāo)，所獲得的最優(yōu)解對(duì)應(yīng)的Gantt圖如圖6所示。由圖6可知，整個(gè)制造過(guò)程中，相對(duì)于其他設(shè)備，設(shè)備M4、M6及M8的使用頻率較高。由于僅以加工成本作為優(yōu)化目標(biāo)，對(duì)應(yīng)的makespan及設(shè)備最大負(fù)載均不低于Pareto解集中對(duì)應(yīng)的最高makespan及最高設(shè)備最大負(fù)載。

圖6　僅優(yōu)化加工成本所得最優(yōu)解對(duì)應(yīng)的Gantt圖

(3)僅以設(shè)備最大負(fù)載為優(yōu)化目標(biāo)。若僅以設(shè)備最大負(fù)載為優(yōu)化目標(biāo)，一定程度上可以克服僅以加工成本為優(yōu)化目標(biāo)導(dǎo)致的資源利用不均問(wèn)題。但是，由于沒(méi)有考慮到加工成本，最優(yōu)解對(duì)應(yīng)的加工成本高于Pareto解集中對(duì)應(yīng)的最高加工成本。

4　結(jié)論

(1) 針對(duì)MOIPPS問(wèn)題，同時(shí)以makespan、加工成本及設(shè)備最大負(fù)載為優(yōu)化目標(biāo)，建立了該問(wèn)題的數(shù)學(xué)模型。

(2) 針對(duì)該問(wèn)題，設(shè)計(jì)了一種非支配排序遺傳算法。以6層編碼結(jié)構(gòu)表示可行解；通過(guò)分層操作及擁擠度計(jì)算，結(jié)合偏序關(guān)系，使用錦標(biāo)賽選擇法對(duì)種群進(jìn)行選擇操作；設(shè)計(jì)了適用于MOIPPS問(wèn)題的交叉算子及變異算子。最后，給出了該遺傳算法的流程圖。

(3) 以實(shí)例驗(yàn)證了所建模型的正確性及算法的有效性。一方面，實(shí)際生產(chǎn)中，多種目標(biāo)需要權(quán)衡，若僅以單目標(biāo)作為優(yōu)化對(duì)象，往往導(dǎo)致企業(yè)在其他目標(biāo)上的巨大損失；另一方面，由于設(shè)備功能的相似性以及加工手段和技術(shù)的多樣性，為充分利用各種加工資源，同一道工序可以由多臺(tái)設(shè)備完成，同一工件可能制定多條工藝路線。因此，對(duì)MOIPPS問(wèn)題進(jìn)行研究，更加符合實(shí)際生產(chǎn)環(huán)境，通過(guò)求解獲得的Pareto解集，對(duì)于實(shí)際調(diào)度方案的確定，具有更好的參考與指導(dǎo)作用。

[1]呂盛坪，喬立紅．工藝規(guī)劃與車間調(diào)度及兩者集成的研究現(xiàn)狀和發(fā)展趨勢(shì)[J]．計(jì)算機(jī)集成制造系統(tǒng)，2014，20(2)：290-300．

Lü Shengping，Qiao Lihong．Current Status and Developing Trend of Process Planning and Job Shop Scheduling[J]．Computer Integrated Manufacturing Systems，2014，20(2)：290-300．

[2]高亮，李新宇．工藝規(guī)劃與車間調(diào)度集成研究現(xiàn)狀及進(jìn)展[J]．中國(guó)機(jī)械工程，2011，22(8)：1001-1007．

Gao Liang，Li Xinyu．Current Researches on Integrated Process Planning and Scheduling[J]．China Mechanical Engineering，2011，22(8)：1001-1007．

[3]Li Xinyu，Zhang Chaoyong，Gao Liang，et al．An Agent-based Approach for Integrated Process Planning and Scheduling[J]．Expert Systems with Applications，2010，37：1256-1264．

[4]呂盛坪，喬立紅．工藝規(guī)劃與調(diào)度復(fù)合式集成模型[J]．計(jì)算機(jī)集成制造系統(tǒng)，2014，20(1)：110-120．

Lü Shengping，Qiao Lihong．Hybrid Integration Model for Process Planning and Scheduling[J]．Computer Integrated Manufacturing Systems，2014，20(1)：110-120．

[5]Phanden R K，Jain A，Verma R．An Approach for Integration of Process Planning and Scheduling[J]．International Journal of Computer Integrated Manufacturing，2013，26(4)：284-302．

[6]Li Xinyu，Zhang Chaoyong，Gao Liang，et al．An Effective Hybrid Algorithm for Integrated Process Planning and Scheduling[J]．Int．J．Production Economics，2010，126：289-298．[7]Li Xinyu，Gao Liang，Shao Xinyu．Mathematical Modeling and Evolutionary Algorithm-based Approach for Integrated Process Planning and Scheduling[J]．Computers & Operations Research，2010，37：656-667．[8]Li Xinyu，Gao Liang，Shao Xinyu．An Active Learning Genetic Algorithm for Integrated Process Planning and Scheduling[J]．Expert Systems with Applications，2012，39：6683-6691．

[9]Wang Jinfei，F(xiàn)an Xiaoliang，Zhang Chaowei，et al．A Graph-based Ant Colony Optimization Approach for Integrated Process Planning and Scheduling[J]．Chinese Journal of Chemical Engineering，2014，22(7)：748-753．

[10]Seker A，Erol S，Botsali R．A Neuro-fuzzy Model for a New Hybrid Integrated Process Planning and Scheduling System[J]．Expert Systems with Applications，2013，40：5341-5351．

[11]彭建剛，劉明周，張銘鑫，等．基于改進(jìn)非支配排序的云模型進(jìn)化多目標(biāo)柔性作業(yè)車間調(diào)度[J]．機(jī)械工程學(xué)報(bào)，2014，50(12)：198-204．

Peng Jiangang，Liu Mingzhou，Zhang Mingxin，et al．Cloud Model Evolutionary Multi-objective Flexible Job-shop Scheduling Based on Improved Non-dominated Sorting[J]．Journal of Mechanical Engineering，2014，50(12)：198-204．

[12]張鐵男，韓兵，于渤．生產(chǎn)能力約束條件下的柔性作業(yè)車間調(diào)度優(yōu)化[J]．系統(tǒng)工程理論與實(shí)踐，2011，31(3)：505-510．

Zhang Tienan，Han Bing，Yu Bo．Flexible Job-shop Scheduling Optimization Based on Improved Genetic Algorithm[J]．Systems Engineering-Theory & Practice，2011，31(3)：505-510．

[13]劉愛(ài)軍，楊育，邢青松，等．多目標(biāo)模糊柔性車間調(diào)度中的多種群遺傳算法[J]．計(jì)算機(jī)集成制造系統(tǒng)，2011，17(9)：1954-1961．

Liu Aijun，Yang Yu，Xing Qingsong，et al．Multi-population Genetic Algorithm in Multiobjective Fuzzy and Flexible Job Shop Scheduling[J]．Computer Integrated Manufacturing Systems，2011，17(9)：1954-1961．

[14]施進(jìn)發(fā)，焦合軍，陳濤．交貨期懲罰下柔性車間調(diào)度多目標(biāo)Pareto優(yōu)化研究[J]．機(jī)械工程學(xué)報(bào)，2012，48(12)：184-191．

Shi Jinfa，Jiao Hejun，Chen Tao．Multi-objective Pareto Optimization on Flexible Job-shop Scheduling Problem about Due Punishment[J]．Journal of Mechanical Engineering，2012，48(12)：184-191．

[15]陳成，邢立寧．求解柔性作業(yè)車間調(diào)度問(wèn)題的遺傳—蟻群算法[J]．計(jì)算機(jī)集成制造系統(tǒng)，2011，17(3)：615-621．

Chen Cheng，Xing Lining．GA-ACO for Solving Flexible Job Shop Scheduling Problem[J]．Computer Integrated Manufacturing Systems，2011，17(3)：615-621．

[16]王云，馮毅雄，譚建榮，等．基于多目標(biāo)粒子群算法的柔性作業(yè)車間調(diào)度優(yōu)化方法[J]．農(nóng)業(yè)機(jī)械學(xué)報(bào)，2011，42(2)：190-195．Wang Yun，F(xiàn)eng Yixiong，Tan Jianrong，et al．Optimization Method of Flexible Job-shop Scheduling Based on Multiobjective Particle Swarm Optimization Algorithm[J]．Transactions of the Chinese Society for Agricultural Machinery，2011，42(2)：190-195．[17]Moslehi G，Mehnam M．A Pareto Approach to Multi-objective Flexible Job-shop Scheduling Problem Using Particle Swarm Optimization and Local Search[J]．Int．J．Production Economics，2011，129：14-22．[18]Shahsavari-Pour N，Ghasemishabankareh B．A Novel Hybrid Meta-heuristic Algorithm for Solving Multi Objective Flexible Job Shop Scheduling[J]．Journal of Manufacturing Systems，2013，32：771-780．[19]王偉玲，李俊芳，王晶．求解多目標(biāo)作業(yè)車間調(diào)度問(wèn)題的雙種群遺傳算法[J]．計(jì)算機(jī)集成制造系統(tǒng)，2011，17(4)：808-815．

Wang Weiling，Li Junfang，Wang Jing．Double-population Genetic Algorithm for Multi-objective Job Shop Scheduling Problem[J]．Computer Integrated Manufacturing Systems，2011，17(4)：808-815．

[20]Amin-Tahmasbi H，Tavakkoli-Moghaddam R．Solving a Bi-objective Flowshop Scheduling Problem by a Multi-objective Immune System and Comparing with SPEA2+ and SPGA[J]．Advances in Engineering Software，2011，42：772-779．

[21]Bandyopadhyay S，Bhattacharya R．Solving Multi-objective Parallel Machine Scheduling Problem by a Modified NSGA-Ⅱ[J]．Applied Mathematical Modelling，2013，37：6718-6729．[22]Panahi H，Tavakkoli-Moghaddam R．Solving a Multi-objective Open Shop Scheduling Problem by a Novel Hybrid Ant Colony Optimization[J]．Expert Systems with Applications，2011，38：2817-2822．

[23]曾強(qiáng)，楊育，王勇智，等．復(fù)合工藝流程下批量生產(chǎn)車間調(diào)度多目標(biāo)優(yōu)化[J]．中國(guó)機(jī)械工程，2011，22(2)：190-196．

Zeng Qiang，Yang Yu，Wang Yongzhi，et al．Multi-objective Optimization Scheduling for Job Shop of Batch Production with Multiple Process Flows[J]．China Mechanical Engineering，2011，22(2)：190-196．

[24]Deb K，Pratap A，Agrawal S，et al．A Fast and Elitist Multiobjective Genetic Algorithm：NSGA-Ⅱ [J]．IEEE Transactions on Evolutionary Computation，2002，6(2)：182-197．

(編輯王旻玥)

Research on Integrated Process Planning and Scheduling Problem with Consideration of Multi-objectives

Li YanBa LiCao YuanLiu YongYang Mingshun

Xi’an University of Technology,Xi’an,710048

Aiming at the shortage of IPPS problem in multi-objective optimization, multi-objective optimization was integrated into IPPS problem. The makespan, processing cost and maximum machine workload were the main targets which will be optimized. The model was built for multi-objective integrated process planning and scheduling problem. A non-dominated sorting genetic algorithm (NSGA-Ⅱ) was proposed for the problem. A multi-layer structure was used to represent solutions. Selection and genetic operators are designed in the algorithm. Finally, the model and algorithm were proved through an application case.

integrated process planning and scheduling; multi-objectives; non-dominated sorting genetic algorithm; selection

2015-02-09

國(guó)家自然科學(xué)基金資助項(xiàng)目(61402361)；陜西省教育廳科學(xué)研究計(jì)劃資助項(xiàng)目(14JK1521)；陜西省科學(xué)技術(shù)研究發(fā)展計(jì)劃資助項(xiàng)目(2012KJXX-34)；西安理工大學(xué)青年科技創(chuàng)新團(tuán)隊(duì)建設(shè)計(jì)劃資助項(xiàng)目(102-211408)

TH166；TH186DOI：10.3969/j.issn.1004-132X.2015.17.012

李言，男，1960年生。西安理工大學(xué)機(jī)械與精密儀器工程學(xué)院教授、博士研究生導(dǎo)師。主要研究方向?yàn)橄冗M(jìn)制造技術(shù)、精密加工技術(shù)及機(jī)電測(cè)控技術(shù)等。發(fā)表論文300余篇。巴黎(通信作者)，男，1986年生。西安理工大學(xué)機(jī)械與精密儀器工程學(xué)院博士研究生。曹源，男，1991年生。西安理工大學(xué)機(jī)械與精密儀器工程學(xué)院碩士研究生。劉永，男，1981年生。西安理工大學(xué)機(jī)械與精密儀器工程學(xué)院副教授。楊明順，男，1974年生。西安理工大學(xué)機(jī)械與精密儀器工程學(xué)院副教授。