段建國(guó)，李豪晨，張青雷

(1.上海海事大學(xué) 中國(guó)(上海)自貿(mào)區(qū)供應(yīng)鏈研究院，上海 201306；2.上海海事大學(xué) 物流工程學(xué)院，上海 201306)

0 引言

綠色制造是實(shí)現(xiàn)人與自然和諧共生的重要組成，是綜合考慮經(jīng)濟(jì)效益與資源能耗的新趨勢(shì)和新要求[1]。半組合式船用曲軸作為大型船舶的核心部件，其生產(chǎn)流程具有品種多、批量小、加工精度高、性能指標(biāo)苛刻、制造工藝復(fù)雜、高能耗、高污染以及交貨期嚴(yán)等特點(diǎn)，不合理的作業(yè)生產(chǎn)安排將導(dǎo)致企業(yè)制造過程成本高、效率低、碳排放量大、環(huán)境污染嚴(yán)重等問題。因此，良好的車間調(diào)度是實(shí)現(xiàn)半組合式船用曲軸結(jié)構(gòu)件制造車間節(jié)能減排、經(jīng)濟(jì)高效的綠色生產(chǎn)的關(guān)鍵。

作業(yè)車間調(diào)度問題(Job shop Scheduling Problem, JSP)自提出以來已被證明為NP-hard難題[2]，而綠色車間調(diào)度問題(Green Shop Scheduling Problem, GSSP)相比傳統(tǒng)調(diào)度問題更加復(fù)雜，需要取得經(jīng)濟(jì)指標(biāo)與綠色指標(biāo)的協(xié)同優(yōu)化，屬于典型的多目標(biāo)作業(yè)車間調(diào)度問題(Multi-Objective Job Shop Scheduling Problem, MOJSP)?？琢盏萚3]建立了混合流水車間調(diào)度的完工時(shí)間、能耗與成本優(yōu)化模型，提出基于機(jī)床加工特性的多目標(biāo)調(diào)度模型與改進(jìn)的遺傳算法，結(jié)合高效、經(jīng)濟(jì)、節(jié)能和綜合4種生產(chǎn)模式，為混合流水車間綠色制造提供了指導(dǎo)；任彩樂等[4]采用加入移動(dòng)和關(guān)機(jī)重啟策略的候鳥優(yōu)化算法，優(yōu)化了不相關(guān)并行機(jī)混合流水車間的能耗；YIN等[5]針對(duì)柔性作業(yè)車間調(diào)度問題，提出一種新的低碳調(diào)度數(shù)學(xué)模型，對(duì)車間能效、生產(chǎn)率和噪音等指標(biāo)進(jìn)行優(yōu)化；蔣增強(qiáng)等[6]以加工機(jī)器能耗曲線分布特征為依據(jù)，實(shí)現(xiàn)了對(duì)以加工時(shí)間、成本、能耗和工件質(zhì)量為目標(biāo)的柔性作業(yè)車間調(diào)度優(yōu)化；朱光宇等[7]基于直覺模糊集相似度的遺傳算法，以完工時(shí)間、空閑時(shí)間、加工質(zhì)量及機(jī)器能耗為目標(biāo)，對(duì)柔性作業(yè)生產(chǎn)車間進(jìn)行優(yōu)化；WU等[8]針對(duì)柔性作業(yè)車間調(diào)度問題，考慮機(jī)器啟停次數(shù)和加工速度兩種節(jié)能措施，采用非支配排序遺傳算法來優(yōu)化車間完工時(shí)間、能耗和機(jī)器開關(guān)次數(shù)；李聰波等[9]建立了柔性作業(yè)車間廣義能耗調(diào)度數(shù)學(xué)模型，并基于模擬退火算法優(yōu)化車間廣義能耗和總完工時(shí)間。

上述文獻(xiàn)中，學(xué)者們基于傳統(tǒng)車間調(diào)度問題，以機(jī)器資源為約束，考慮綠色制造的多目標(biāo)性，建立單資源約束、多目標(biāo)優(yōu)化的調(diào)度數(shù)學(xué)模型，深入分析了制造過程中機(jī)器加工對(duì)環(huán)境的影響。但上述研究并未考慮工件運(yùn)輸時(shí)間，或?qū)⑦\(yùn)輸時(shí)間歸加在機(jī)加時(shí)間內(nèi)，得到的調(diào)度結(jié)果并不能真實(shí)反映車間實(shí)際制造情況。工件的運(yùn)輸資源與機(jī)器資源相互沖突，需要合理權(quán)衡。例如工序選擇不同的加工機(jī)器，則存在不同的運(yùn)輸路徑，相應(yīng)產(chǎn)生不同的運(yùn)輸時(shí)間與運(yùn)輸能耗，運(yùn)輸時(shí)間影響后續(xù)工序開始時(shí)間與總完工時(shí)間，運(yùn)輸能耗影響車間總能耗。因此，解決考慮運(yùn)輸?shù)木G色集成調(diào)度問題成為當(dāng)前研究熱點(diǎn)之一。

針對(duì)包含運(yùn)輸?shù)募烧{(diào)度優(yōu)化，部分學(xué)者采用先優(yōu)化工序調(diào)度，再進(jìn)行運(yùn)輸路徑規(guī)劃的動(dòng)態(tài)規(guī)劃方法[10-14]，但并未真正達(dá)到集成調(diào)度的目的。賀長(zhǎng)征等[15]建立了多AGV和機(jī)器的雙資源調(diào)度數(shù)學(xué)模型，采用基于時(shí)間窗的混合遺傳算法優(yōu)化了柔性作業(yè)車間總完工時(shí)間；劉二輝等[16]提出改進(jìn)的花授粉算法解決了以AGV為運(yùn)輸設(shè)備的集成作業(yè)車間調(diào)度問題，并優(yōu)化了車間總完工時(shí)間；LU等[17]針對(duì)置換流水車間調(diào)度問題，建立了一個(gè)考慮可控運(yùn)輸時(shí)間的節(jié)能調(diào)度數(shù)學(xué)模型，并采用回溯搜索算法求解；ESPINOUSE等[18]研究了由一臺(tái)機(jī)器、一個(gè)倉(cāng)庫(kù)和一輛運(yùn)輸小車組成的簡(jiǎn)單調(diào)度問題的復(fù)雜性；NOURI等[19]建立以機(jī)器人為運(yùn)輸設(shè)備的柔性作業(yè)車間集成調(diào)度優(yōu)化模型，提出考慮運(yùn)輸資源與機(jī)器資源的集成調(diào)度問題比傳統(tǒng)車間調(diào)度問題求解更為困難，并驗(yàn)證了集成調(diào)度模型的優(yōu)越性。

上述文獻(xiàn)中，學(xué)者們針對(duì)不同運(yùn)輸設(shè)備，考慮運(yùn)輸資源與機(jī)器資源對(duì)車間調(diào)度結(jié)果的相互影響，建立了雙資源約束集成調(diào)度數(shù)學(xué)模型，優(yōu)化了車間完工時(shí)間等經(jīng)濟(jì)指標(biāo)，但缺乏對(duì)車間能耗或碳排放等綠色指標(biāo)的協(xié)同優(yōu)化。同時(shí)，目前考慮運(yùn)輸?shù)募烧{(diào)度問題，研究對(duì)象多采用以AGV或機(jī)器人為運(yùn)輸設(shè)備的制造車間，對(duì)于以橋式起重機(jī)為運(yùn)輸設(shè)備的大重型工件制造車間研究還很少。因此，建立以橋式起重機(jī)為運(yùn)輸設(shè)備的雙資源約束集成綠色調(diào)度數(shù)學(xué)模型，對(duì)于我國(guó)實(shí)現(xiàn)重工業(yè)綠色制造具有積極意義。

針對(duì)以上不足，本文以橋式起重機(jī)為運(yùn)輸設(shè)備的船用曲軸結(jié)構(gòu)件制造車間為對(duì)象，在考慮機(jī)器加工與運(yùn)輸設(shè)備雙資源約束的基礎(chǔ)上，以最大完工時(shí)間、機(jī)器加工能耗和運(yùn)輸設(shè)備能耗為優(yōu)化目標(biāo)，研究了綠色車間集成調(diào)度建模與優(yōu)化方法，并通過將集成化優(yōu)化結(jié)果與不考慮運(yùn)輸狀態(tài)的傳統(tǒng)車間調(diào)度結(jié)果進(jìn)行比對(duì)，驗(yàn)證了集成化數(shù)學(xué)模型在解決此類綠色車間調(diào)度問題方面的實(shí)用性和有效性。

1 問題描述及數(shù)學(xué)模型

本文研究對(duì)象是以橋式起重機(jī)為運(yùn)輸設(shè)備的柔性作業(yè)生產(chǎn)車間，如圖1所示。待加工工件n個(gè)，加工機(jī)器m臺(tái)，每個(gè)工件有qi道工序，工件i工序j用Oij表示，工序Oij可選加工機(jī)器集為M(Oij)，是典型的柔性作業(yè)車間調(diào)度問題。機(jī)器間工件運(yùn)輸采用橋式起重設(shè)備完成，橋式起重設(shè)備運(yùn)輸工件分為大車沿車間x軸方向移動(dòng)、小車沿車間y軸方向移動(dòng)、提升機(jī)構(gòu)沿車間z軸方向移動(dòng)3個(gè)步驟，3個(gè)機(jī)構(gòu)分步進(jìn)行操作完成工件運(yùn)輸任務(wù)。

為方便問題研究，作出如下假設(shè)，同時(shí)表1給出了文中涉及的參數(shù)及定義：

(1)每臺(tái)機(jī)器同一時(shí)刻只可加工一個(gè)工件；

(2)每個(gè)工件同一時(shí)刻只可被一臺(tái)機(jī)器加工；

(3)每個(gè)工件工序加工開始不允許被中斷；

(4)不同工件之間工序沒有約束，同一工件之間有工序順序約束；

(5)每個(gè)工件的第一道工序無需起重設(shè)備運(yùn)輸；

(6)起重設(shè)備同一時(shí)間只可運(yùn)輸一個(gè)工件；

(7)起重設(shè)備運(yùn)輸完一個(gè)工件后，立即進(jìn)行下一步運(yùn)輸任務(wù)；

(8)起重設(shè)備3個(gè)運(yùn)行機(jī)構(gòu)需各自依次完成移動(dòng)，不可同時(shí)操作；

(9)起重設(shè)備初始位置在第一道工序加工機(jī)器處；

(10)工件緩沖區(qū)無限大，工件在機(jī)器加工完成后，置于機(jī)旁運(yùn)輸?shù)却齾^(qū)，等待起重設(shè)備運(yùn)輸而不占用當(dāng)前機(jī)器資源；

(11)工件前后工序不存在機(jī)器轉(zhuǎn)換，則起重設(shè)備不運(yùn)輸工件；

表1 參數(shù)定義

1.1 運(yùn)輸時(shí)間函數(shù)

以橋式起重機(jī)為運(yùn)輸設(shè)備的車間，工序在機(jī)器間運(yùn)輸包括空載運(yùn)輸與負(fù)載運(yùn)輸兩部分，如圖2所示。現(xiàn)需完成工序Oij運(yùn)輸任務(wù)，將工件i由機(jī)器k運(yùn)輸至機(jī)器k2，起重設(shè)備先由前置運(yùn)輸工序Oi1j1所在機(jī)器k1移動(dòng)至機(jī)器k，即為工序Oij的運(yùn)輸空載過程，機(jī)器k所在位置稱為工序Oij的空載運(yùn)輸目的位置，起重運(yùn)輸設(shè)備分別完成大車機(jī)構(gòu)車間x軸方向移動(dòng)與小車機(jī)構(gòu)車間y軸方向移動(dòng)。移動(dòng)至機(jī)器k，若工序Oi(j-1)未加工完成，則存在空載運(yùn)輸?shù)却龝r(shí)間。

工序Oi(j-1)加工完成后，負(fù)載運(yùn)輸過程開始，機(jī)器k2所在位置稱為工序Oij的負(fù)載運(yùn)輸目的位置，若工序Oij在機(jī)器k2上的前置工序Oi2j2未加工完成，則存在負(fù)載運(yùn)輸?shù)却龝r(shí)間。為保證運(yùn)輸過程的安全有序，負(fù)載運(yùn)輸?shù)拈_始時(shí)間應(yīng)保證工件i運(yùn)輸至機(jī)器k2時(shí)，其處于空閑狀態(tài)，起重設(shè)備分別由提升機(jī)構(gòu)完成工件i沿車間z軸方向提升，大車機(jī)構(gòu)與小車機(jī)構(gòu)車間x軸方向與y軸方向移動(dòng)，工件沿車間z軸方向下降釋放至機(jī)器k2，至此工序Oij運(yùn)輸過程結(jié)束。

考慮大重型工件加工車間占地面積廣，機(jī)器間距離大，忽略橋式起重運(yùn)輸設(shè)備各機(jī)構(gòu)啟動(dòng)時(shí)間與制動(dòng)時(shí)間，各機(jī)構(gòu)運(yùn)輸時(shí)間公式如下：

空載運(yùn)輸大車機(jī)構(gòu)運(yùn)行時(shí)間

(1)

空載運(yùn)輸小車機(jī)構(gòu)運(yùn)行時(shí)間

(2)

工序Oij空載運(yùn)輸總時(shí)間

(3)

空載運(yùn)輸?shù)却龝r(shí)間

(4)

負(fù)載運(yùn)輸大車機(jī)構(gòu)運(yùn)行時(shí)間

(5)

負(fù)載運(yùn)輸小車機(jī)構(gòu)運(yùn)行時(shí)間

(6)

負(fù)載運(yùn)輸提升機(jī)構(gòu)提升時(shí)間

(7)

負(fù)載運(yùn)輸提升機(jī)構(gòu)釋放時(shí)間

(8)

工序Oij負(fù)載運(yùn)輸總時(shí)間

(9)

負(fù)載運(yùn)輸?shù)却龝r(shí)間

(10)

工序Oij運(yùn)輸?shù)却倳r(shí)間

Wt(Oij)=Wtnl(Oij)+Wtl(Oij)。

(11)

1.2 機(jī)器加工能耗函數(shù)

車間機(jī)器能耗主要分為加工能耗與待機(jī)能耗兩部分，根據(jù)船用曲軸結(jié)構(gòu)件加工精度要求高、工藝繁雜、加工時(shí)間長(zhǎng)等特點(diǎn)，將工件在機(jī)器上的加工時(shí)間分為準(zhǔn)備時(shí)間(主要包括刀具更換時(shí)間)、工件裝夾、工件加工(主要包括工件切削過程)、工件卸夾4個(gè)時(shí)間流程，機(jī)器切削過程中給刀空切和退刀空切因運(yùn)行時(shí)間遠(yuǎn)小于切削時(shí)間，故不在本文考慮范圍之內(nèi)。機(jī)器功率—時(shí)間曲線如圖3所示，功率狀態(tài)分為待機(jī)功率和切削功率，對(duì)應(yīng)工件加工4個(gè)時(shí)間流程分別產(chǎn)生：刀具更換能耗、工件裝夾能耗、機(jī)器切削能耗、工件卸夾能耗以及空閑時(shí)間產(chǎn)生的待機(jī)能耗。

刀具更換能耗

(12)

工件裝夾能耗

(13)

工件切削能耗

(14)

工件卸夾能耗

(15)

機(jī)床總待機(jī)能耗

(16)

綜上所述,機(jī)床能耗

Emachine=Estep1+Estep2+Estep3+Estep4+Eidle。

(17)

1.3 橋式起重機(jī)運(yùn)輸能耗

橋式起重機(jī)作為我國(guó)制造業(yè)廣泛應(yīng)用的特種設(shè)備，其能耗是衡量我國(guó)能源管理水平的重要標(biāo)志。據(jù)統(tǒng)計(jì)，我國(guó)起重設(shè)備能耗是國(guó)外的5～8倍，因此，開展起重機(jī)械能耗分析和節(jié)能優(yōu)化符合國(guó)家政策要求，對(duì)于使用特種設(shè)備進(jìn)行生產(chǎn)的企業(yè)具有極大的經(jīng)濟(jì)效益。本文結(jié)合橋式起重機(jī)械在“全生命周期”能耗狀況中的電能因素分析[20-22]，主要考慮運(yùn)行機(jī)構(gòu)和提升機(jī)構(gòu)中電動(dòng)機(jī)、變頻器、制動(dòng)器等主要部件能效，如表2所示。同時(shí)，利用粗級(jí)理論屬性簡(jiǎn)約知識(shí)剔除冗余指標(biāo)[23-24]，確定權(quán)重，提高評(píng)價(jià)效率。橋式起重機(jī)在運(yùn)輸任務(wù)中產(chǎn)生的能耗主要分為自身能耗與等待能耗兩部分，自身能耗分為大車機(jī)構(gòu)、小車機(jī)構(gòu)、提升機(jī)構(gòu)3個(gè)部分;等待能耗由空載運(yùn)輸?shù)却龝r(shí)間與負(fù)載運(yùn)輸?shù)却龝r(shí)間產(chǎn)生的待機(jī)能耗組成。由上述可知，不同的工序調(diào)度方案產(chǎn)生的運(yùn)輸能耗與等待能耗也各不相同，因此優(yōu)化起重設(shè)備能耗在縮短運(yùn)輸時(shí)間的同時(shí)，也可提高運(yùn)輸效率，達(dá)到節(jié)能減排的綠色制造要求。

表2 橋式起重設(shè)備能效分析

由上表可知橋式起重運(yùn)輸設(shè)備總能效：

θ=ωgθg+ωtθt+ωsθs，ωg+ωt+ωs=1。

(18)

結(jié)合圖2所示橋式起重設(shè)備運(yùn)輸工件流程及空載運(yùn)輸大、小車單位距離能耗εg1、εt1，空載運(yùn)輸過程各機(jī)構(gòu)能耗及空載運(yùn)輸?shù)却芎挠?jì)算公式如下：

工序Oij空載運(yùn)輸大車機(jī)構(gòu)能耗

(19)

工序Oij空載運(yùn)輸小車機(jī)構(gòu)能耗

(20)

工序Oij空載運(yùn)輸總能耗

(21)

工序Oij空載運(yùn)輸?shù)却芎模?/p>

WEnl(Oij)=Wtnl(Oij)×Ps。

(22)

綜上所述，空載運(yùn)輸總能耗

(23)

空載運(yùn)輸總等待能耗

(24)

負(fù)載運(yùn)輸過程需橋式起重設(shè)備完成工件在機(jī)器k處提升與機(jī)器k2處釋放的過程，同時(shí)也包括大車與小車機(jī)構(gòu)運(yùn)輸流程，結(jié)合負(fù)載運(yùn)輸大、小車單位距離能耗εg2、εt2，各機(jī)構(gòu)能耗及負(fù)載運(yùn)輸?shù)却芎挠?jì)算公式如下：

工序Oij負(fù)載運(yùn)輸大車機(jī)構(gòu)能耗

(25)

工序Oij負(fù)載運(yùn)輸小車機(jī)構(gòu)能耗

(26)

工序Oij負(fù)載運(yùn)輸提升機(jī)構(gòu)能耗

(27)

工序Oij負(fù)載運(yùn)輸總能耗

(28)

工序Oij負(fù)載運(yùn)輸?shù)却芎?/p>

WEl(Oij)=Wtl(Oij)×Ps。

(29)

綜上所述,負(fù)載運(yùn)輸總能耗

(30)

負(fù)載運(yùn)輸總等待能耗

WEl(Oij)×c(ki(j-1),k2ij)×d(k2i2j2,k2ij)。

(31)

綜上所述,橋式起重設(shè)備運(yùn)輸總能耗

(32)

1.4 優(yōu)化目標(biāo)及約束條件

本文以面向綠色制造為基礎(chǔ)，建立基于工件運(yùn)輸、工序機(jī)器選擇的雙資源約束調(diào)度數(shù)學(xué)模型，以工件最大完工時(shí)間作為經(jīng)濟(jì)優(yōu)化目標(biāo)，機(jī)器加工能耗和起重運(yùn)輸設(shè)備能耗作為綠色優(yōu)化目標(biāo)。式(33)和式(34)為優(yōu)化目標(biāo)函數(shù)，式(35)～式(41)為多資源約束、多目標(biāo)優(yōu)化綠色調(diào)度數(shù)學(xué)模型約束條件。

最大完工時(shí)間最小：

Tmin=min[max(Ti)](i∈1,2,…,n)；

(33)

機(jī)器加工能耗和起重運(yùn)輸設(shè)備能耗最?。?/p>

Emin=min(Ecrane+Emachine)。

(34)

s.t.

St(Oi(j+1))-Ft(Oij)≥0；

(35)

(36)

St(ki+1)-Ft(ki)≥0；

(37)

(38)

Pnl(Oi1)=Pl(Oi1)=Pl(Oi1j1)；

(39)

Pnl(Oij)=Pl(Oij)=Pl(Oi1j1)；

(40)

Ft(Oij)+Wtl(Oij)≥Ft(Oi2j2)。

(41)

式(35)表示工件工序順序約束，St(Oi(j+1))為工序Oi(j+1)開始時(shí)間，F(xiàn)t(Oij)為工序Oij結(jié)束時(shí)間；式(36)表示同一時(shí)刻一道工序只可被一臺(tái)機(jī)器加工；式(37)表示同一機(jī)器同一時(shí)刻只可加工一道工序，St(ki+1)表示機(jī)器k上第i+1道流程開始時(shí)間，F(xiàn)t(ki)表示機(jī)器k上第i道流程結(jié)束時(shí)間；式(38)表示工件加工開始不允許被中斷；式(39)表示工件第一道工序不需要起重設(shè)備運(yùn)輸；式(40)表示同一工件前后工序在同一機(jī)器上加工則不需要運(yùn)輸；式(41)表示負(fù)載運(yùn)輸開始時(shí)間需在目的機(jī)器空閑后開始。

2 算法流程

NSGA-II算法是由DEB等[25]提出的改進(jìn)的快速非支配排序遺傳算法，因具有廣泛的種群分布與較快的運(yùn)算收斂速度而被多數(shù)學(xué)者運(yùn)用于多目標(biāo)車間調(diào)度問題的求解，本文依據(jù)所建立的雙資源約束、多目標(biāo)優(yōu)化綠色集成調(diào)度數(shù)學(xué)模型要求，在算法編碼、解碼、交叉、變異等步驟上進(jìn)行改進(jìn)，并融合兩種啟發(fā)式選擇策略遍歷每一次迭代得到的新種群，對(duì)種群中滿足策略要求的調(diào)度方案進(jìn)行二次優(yōu)化。通過求解上述綠色調(diào)度數(shù)學(xué)模型，得到一組符合生產(chǎn)要求的Pareto前沿解集，算法流程如圖4所示。

2.1 種群初始化

為保證種群多樣性，盡量遍布解空間，以尋求一組符合生產(chǎn)要求的Pareto解集，采用隨機(jī)生成染色體的方式構(gòu)建初始種群。染色體編碼是算法成功的前提，本文提出一種融合工件工序、加工機(jī)器、機(jī)器集機(jī)器排序、空載運(yùn)輸機(jī)器位置、負(fù)載運(yùn)輸機(jī)器位置的五段式編碼，將工件加工信息與運(yùn)輸信息綜合在一個(gè)染色體中，保證每一個(gè)染色體都是一個(gè)調(diào)度可行解。以表3所示加工信息為例說明編碼過程。

表3 加工信息

如圖5所示，染色體第一段編碼為工序排序，每個(gè)數(shù)字出現(xiàn)的先后次序分別表示該工件的工序次序，如第一次出現(xiàn)數(shù)字1表示工序O11，第二次出現(xiàn)數(shù)字1表示工序O12；染色體第二段編碼表示工序機(jī)器選擇，數(shù)字5表示工序O11選擇加工機(jī)器為5號(hào)機(jī)器；染色體第三段編碼表示工序選擇機(jī)器在相應(yīng)機(jī)器集中排序，如工序O11為5號(hào)機(jī)器；第四、五段編碼表示工件的運(yùn)輸信息，數(shù)字表示運(yùn)輸位置所在機(jī)器號(hào)。

空載和負(fù)載運(yùn)輸目的機(jī)器編碼段是由工序排序和機(jī)器選擇編碼段形成，形成過程如圖6所示。由假設(shè)條件可知工件第一道工序不需要運(yùn)輸，則工序O11空載目的機(jī)器與負(fù)載目的機(jī)器相同，均為其加工機(jī)器5號(hào)，分別由圖中虛線和實(shí)線表示；工序排序第二位為O31，工件3第一道工序不需要運(yùn)輸，則其相應(yīng)三、四編碼段機(jī)器與前置工序O11機(jī)器相同，由圖中弧線表示；工序排序第三位為O32，工件3第二道工序，其空載目的機(jī)器為工序O31加工機(jī)器3號(hào)，負(fù)載目的機(jī)器為其自身機(jī)器選擇6號(hào)，由圖中虛線和實(shí)線表示；工序排序第四位為O21，工件2第一道工序無需運(yùn)輸，其空載目的機(jī)器與負(fù)載目的機(jī)器相同，均為前置工序O32加工機(jī)器6號(hào)，由圖中虛線和實(shí)線表示；后續(xù)工序以此類推形成四、五段編碼。

該方法有效避免了后續(xù)交叉、變異等操作不可行解的產(chǎn)生，使得交叉、變異操作只對(duì)工序排序和機(jī)器選擇編碼段進(jìn)行，子代的運(yùn)輸編碼段依據(jù)形成的前兩段編碼更新即可。

2.2 快速非支配排序與個(gè)體擁擠度計(jì)算

初始種群生成后對(duì)個(gè)體進(jìn)行快速非支配排序，個(gè)體函數(shù)值為F(x)={Tmin,Emin}，判別準(zhǔn)則為當(dāng)且僅當(dāng)x1目標(biāo)函數(shù)值均小于等于x2時(shí)，為個(gè)體x1支配個(gè)體x2，記為x1x2。生成Pareto第一層后，將其中個(gè)體從種群中排除，對(duì)剩余個(gè)體依據(jù)非劣解水平繼續(xù)進(jìn)行分層排序，直至種群所有個(gè)體都具有相應(yīng)的排列序號(hào)。同時(shí)，對(duì)同層的個(gè)體進(jìn)行擁擠度距離計(jì)算，每層各目標(biāo)函數(shù)最大的個(gè)體視為邊界個(gè)體，并將其擁擠度設(shè)為無窮大，其余個(gè)體擁擠度則為與相鄰兩個(gè)體目標(biāo)函數(shù)差值之和。

2.3 交叉操作

本文采用基于工序排序的IPOX交叉與基于機(jī)器選擇的單點(diǎn)交叉，由于工件工序約束，IPOX交叉在保證染色體各工件工序不變的前提下，可良好地繼承父代基因，保證交叉后的子代染色體仍為一組調(diào)度可行解。IPOX交叉如圖7所示，具體步驟為：所有工件隨機(jī)生成兩個(gè)集合N1、N2，N1={1,3}，N2={2}。將父代染色體P1包括N1的所有工件復(fù)制在子代C1中，P2包括N2的所有工件復(fù)制在子代C2中，并保留它們的相應(yīng)位置；同時(shí)復(fù)制P1包含N1的工件至C2，P2包含N2的工件至C1，并保留它們的相應(yīng)順序。上述交叉均保留工序機(jī)器選擇，交叉完成后更新子代空載運(yùn)輸目的機(jī)器編碼和負(fù)載運(yùn)輸目的機(jī)器編碼。

基于機(jī)器選擇單點(diǎn)交叉，如圖8所示，具體步驟為：隨機(jī)生成一個(gè)交叉點(diǎn)，保留父代P1、P2工序排序不變，分別復(fù)制到子代染色體C1、C2中，對(duì)選定的父代染色體P1、P2位于交叉點(diǎn)前共同工序的機(jī)器選擇進(jìn)行交換，交叉點(diǎn)后的工序機(jī)器選擇不變。交叉完成后的新染色體依據(jù)工序排序編碼段與機(jī)器選擇編碼段對(duì)機(jī)器集排序編碼、空載運(yùn)輸目的機(jī)器與負(fù)載運(yùn)輸目的機(jī)器進(jìn)行更新，得到兩個(gè)新子代染色體。

2.4 變異操作

基于工序排序的變異采用插入式變異，在父代染色體中將工序排序編碼段中的一個(gè)基因提出來，在保證該工件工序順序約束的前提下，隨機(jī)插入染色體中另外一個(gè)位置，如圖9所示?；跈C(jī)器選擇的變異操作因工序存在加工機(jī)器集，每道工序均有其他機(jī)器可供選擇，在父代染色體中隨機(jī)選定一個(gè)基因位，在其相應(yīng)加工工序機(jī)器集中選擇加工時(shí)間最短的一個(gè)進(jìn)行替換即可。

2.5 啟發(fā)式優(yōu)化策略

2.5.1 策略1

策略1旨在滿足調(diào)度方案最優(yōu)的前提下，優(yōu)化各工序加工能耗與負(fù)載運(yùn)輸過程，因工序加工柔性的特點(diǎn)，存在加工機(jī)器集可供選擇，不同的加工機(jī)器產(chǎn)生不同的加工能耗；同時(shí)，工件相鄰工序加工機(jī)器的不同也會(huì)導(dǎo)致負(fù)載運(yùn)輸路徑的不同，若相鄰工序加工機(jī)器距離過遠(yuǎn)，將造成過多不必要的能耗浪費(fèi)與過長(zhǎng)的運(yùn)輸時(shí)間，從而影響整個(gè)制造流程。啟發(fā)式優(yōu)化策略1具體步驟如下：

步驟1假設(shè)工序Oij需由機(jī)器k運(yùn)輸至機(jī)器k1加工，存在機(jī)器集M(Oij)，通過式(5)～式(8)計(jì)算M(Oij)中所有機(jī)器與機(jī)器k負(fù)載運(yùn)輸時(shí)間，判定是否存在相對(duì)與機(jī)器k1運(yùn)輸時(shí)間更小或相等的機(jī)器集合M1(Oij)，若存在，則轉(zhuǎn)步驟2;否則轉(zhuǎn)步驟4。

Emachine(Oij,k2)]。

(42)

步驟3若機(jī)器集M2(Oij)中存在k2滿足判定邏輯式(43)，則進(jìn)行機(jī)器替換;否則轉(zhuǎn)步驟4，Ecrane(Oij,k1)表示Oij選擇機(jī)器k1時(shí)的調(diào)度總運(yùn)輸能耗。

Ecrane(Oij,k1)≥Ecrane(Oij,k2)。

(43)

步驟4對(duì)每道工序重復(fù)進(jìn)行步驟1～步驟3，遍歷染色體所有工序。

2.5.2 策略2

策略2旨在滿足調(diào)度方案最優(yōu)的前提下，優(yōu)化負(fù)載運(yùn)輸?shù)却龝r(shí)間來提高設(shè)備利用效率，以均衡各機(jī)器負(fù)載，同時(shí)有效降低運(yùn)輸過程總時(shí)間，進(jìn)而優(yōu)化整個(gè)工藝流程，縮短工件完工時(shí)間，對(duì)經(jīng)濟(jì)與資源效益均有積極作用，具體步驟如下：

步驟1通過式(10)，判定工序Oij由機(jī)器k運(yùn)輸至機(jī)器k1加工是否存在負(fù)載運(yùn)輸?shù)却龝r(shí)間，若存在，則轉(zhuǎn)步驟2;否則轉(zhuǎn)步驟5。

步驟2判定負(fù)載運(yùn)輸?shù)却_始時(shí)，工序Oij機(jī)器集M(Oij)中是否存在空閑機(jī)器集M1(Oij)，若存在，則轉(zhuǎn)步驟3;否則轉(zhuǎn)步驟5。

步驟3若空閑機(jī)器集M1(Oij)中存在符合判定邏輯式(44)的機(jī)器集M2(Oij)，則轉(zhuǎn)步驟4;否則轉(zhuǎn)步驟5，El(Oij,k1)、WEl(Oij,k1)分別表示Oij選擇機(jī)器k1時(shí)的負(fù)載運(yùn)輸能耗與等待能耗，Emachine(Oij,k1)表示Oij選擇機(jī)器k1時(shí)的調(diào)度總機(jī)器能耗。

[El(Oij,k1)+WEl(Oij,k1)≥El(Oij,k2)]&&

[Emachine(Oij,k1)≥Emachine(Oij,k2)]。

(44)

步驟4若機(jī)器集M2(Oij)中存在k2滿足判定邏輯式(45)，則進(jìn)行機(jī)器替換;否則轉(zhuǎn)步驟5，T(Oij,k1)表示Oij選擇機(jī)器k1時(shí)的調(diào)度總完工時(shí)間。

T(Oij,k1)≥T(Oij,k2)。

(45)

步驟5對(duì)每道工序重復(fù)進(jìn)行步驟1～步驟4，遍歷染色體所有工序。

3 案例分析

3.1 工藝參數(shù)

半組合式船用曲軸的生產(chǎn)過程主要包括曲拐、主軸頸、自由端、輸出端等結(jié)構(gòu)件的加工與熱套裝過程。本文主要研究包含起重運(yùn)輸約束的曲軸結(jié)構(gòu)件機(jī)械加工過程調(diào)度問題，忽略后續(xù)單套、復(fù)套等復(fù)雜熱套裝工藝。以上海某船用曲軸有限公司結(jié)構(gòu)件生產(chǎn)制造車間為例，車間各設(shè)備工藝能力信息及位置如表4所示，現(xiàn)需制造一批G45、G50兩種典型船用曲軸結(jié)構(gòu)件曲拐、主軸頸與自由端，表5給出了各結(jié)構(gòu)件工藝組成、工序類型、可選機(jī)器及相應(yīng)機(jī)器上的工藝時(shí)間。

表4 車間機(jī)器信息

表5 工件信息 min

續(xù)表5

曲軸結(jié)構(gòu)件制造車間橋式起重運(yùn)輸設(shè)備基本信息如下：大車、小車、提升機(jī)構(gòu)能效分別為0.845、0.881、0.897，同時(shí)利用粗級(jí)理論確定的權(quán)重分別為0.318、0.407、0.275；空載運(yùn)輸單位距離(單位：m)大車、小車能耗分別為3.18 kW·h、2.09 kW·h，負(fù)載運(yùn)輸單位距離(單位：m)大車、小車能耗分別為4.39 kW·h、3.16 kW·h，提升機(jī)構(gòu)單位距離(單位：m)能耗為48.23 kW·h；起重機(jī)待機(jī)功率為650 W，大車、小車額定勻速運(yùn)行速度均為20 m/min；提升機(jī)構(gòu)起升、釋放勻速速度均為2 m/min；規(guī)定車間工件運(yùn)輸統(tǒng)一提升高度為10 m。

3.2 優(yōu)化結(jié)果

將上述曲軸結(jié)構(gòu)件工藝參數(shù)帶入改進(jìn)的快速非支配排序遺傳算法，以種群數(shù)300，迭代數(shù)150，兩種交叉操作概率各45%，兩種變異操作各2%進(jìn)行優(yōu)化求解，得到Pareto前沿如圖10所示。前沿中符合要求的調(diào)度方案為15個(gè)，具體優(yōu)化目標(biāo)函數(shù)值如表6所示，進(jìn)化過程中完工時(shí)間、機(jī)器加工能耗、起重機(jī)運(yùn)輸能耗最優(yōu)值分別如圖11～圖13所示。

表6 Pareto解集目標(biāo)函數(shù)表

由表6可知，當(dāng)最小完工時(shí)間為1 822 min時(shí)，機(jī)器能耗也為最大8 521.35 kW·h，比最大完工時(shí)間2 182 min產(chǎn)生的加工能耗8 405.42 kW·h多消耗115.93 kW·h。由此可知，車間完工時(shí)間與加工能耗是相互沖突的優(yōu)化目標(biāo)，很難同時(shí)達(dá)到最優(yōu)，決策者需要依據(jù)實(shí)際制造情況合理選擇相應(yīng)的調(diào)度方案。同時(shí)，序號(hào)3調(diào)度方案的總能耗最低為8 852.42 kW·h，但其加工能耗與運(yùn)輸能耗并不均為最小，說明單獨(dú)優(yōu)化某一方面的能耗，并不能使車間總能耗達(dá)到最低。

由圖14可知，Pareto前沿中15個(gè)調(diào)度方案的機(jī)器加工能耗變化不大，但起重機(jī)運(yùn)輸能耗變化較大。這是因?yàn)榧庸つ芎呐c工件工序機(jī)器選擇和切削因素密切相關(guān)，工序調(diào)度對(duì)其影響不大；而起重機(jī)運(yùn)輸能耗則主要由工件工序排序和機(jī)器位置決定。

現(xiàn)從Pareto前沿中分別生成完工時(shí)間最小(序號(hào)13)、總能耗最小(序號(hào)3)與位于排序第1位的基因(序號(hào)1)3種調(diào)度方案進(jìn)行對(duì)比決策。圖15為加工時(shí)間最小調(diào)度方案、圖16為總能耗最小方案、圖17為位于排序第1位的調(diào)度方案。甘特圖包括各工件加工流程與橋式起重設(shè)備運(yùn)輸路線，白色代表工序加工時(shí)間，灰色代表空載運(yùn)輸時(shí)間，虛線代表橋式起重機(jī)等待時(shí)間，黑色代表負(fù)載運(yùn)輸時(shí)間。數(shù)字分別代表相應(yīng)工件工序，如1-1為工件1工序1的加工與運(yùn)輸時(shí)間。

分析上述圖中3種調(diào)度方案形成的甘特圖可知：因機(jī)器1相對(duì)加工能耗最低，總能耗最小調(diào)度方案中工序多集中在1號(hào)機(jī)器上加工，造成機(jī)器加工負(fù)載不均勻，1號(hào)機(jī)器超負(fù)荷運(yùn)行，并造成完工時(shí)間過長(zhǎng)，這并不符合實(shí)際制造要求，為不可行調(diào)度方案；完工時(shí)間最小調(diào)度方案與非支配排序第一位調(diào)度方案，完工時(shí)間相差173 min，這是因?yàn)楣ば?-6、1-7由機(jī)器3改變至機(jī)器1加工所致，但兩種調(diào)度方案總能耗僅相差45.4 kW·h，且最小完工時(shí)間方案機(jī)器負(fù)載相對(duì)均勻，綜合考慮更為符合實(shí)際制造要求。

3.3 對(duì)比驗(yàn)證

以往對(duì)包含運(yùn)輸設(shè)備的車間調(diào)度問題為降低求解難度，常采用忽略運(yùn)輸時(shí)間或?qū)⑵錃w加在機(jī)器加工時(shí)間內(nèi)的方法，得到的調(diào)度方案并不符合實(shí)際生產(chǎn)需求。為驗(yàn)證本文所提集成調(diào)度數(shù)學(xué)模型的有效性，先不考慮運(yùn)輸狀態(tài)，以完工時(shí)間與機(jī)器加工能耗為優(yōu)化目標(biāo)對(duì)3.1節(jié)中工件批次進(jìn)行調(diào)度求解，得到如表7所示符合生產(chǎn)要求的Pareto解集。表7中完工時(shí)間最小、機(jī)器能耗最大的調(diào)度方案序號(hào)1的甘特圖如圖18所示。

表7 不考慮運(yùn)輸狀態(tài)的Pareto解集目標(biāo)函數(shù)表

表7中不包含運(yùn)輸時(shí)間的調(diào)度方案序號(hào)1完工時(shí)間為1 741 min，機(jī)器能耗為8 715.9 kW·h，結(jié)合其工序排序與機(jī)器選擇得到包含起重機(jī)運(yùn)輸?shù)恼{(diào)度方案甘特圖如圖19所示，完工時(shí)間增長(zhǎng)至1 981 min，機(jī)器能耗增長(zhǎng)至8 940.1 kW·h，起重機(jī)運(yùn)輸能耗為555.91 kW·h，機(jī)器能耗增加的原因?yàn)榭紤]運(yùn)輸時(shí)間后，機(jī)器空閑時(shí)間有所變化，空載能耗增加。相比于表6中集成調(diào)度方案序號(hào)13，完工時(shí)間增加了159 min，機(jī)器能耗增長(zhǎng)了418.75 kW·h，起重機(jī)運(yùn)輸能耗增長(zhǎng)了119.58 kW·h，從而證明了考慮橋式起重機(jī)運(yùn)輸?shù)募苫{(diào)度數(shù)學(xué)模型的有效性。

4 結(jié)束語(yǔ)

本文針對(duì)半組合式船用曲軸結(jié)構(gòu)件規(guī)格多、批量小、體積質(zhì)量大、加工精度高、生產(chǎn)能耗大、交貨期要求嚴(yán)等特點(diǎn)，以制造車間實(shí)際工藝流程為依據(jù)，細(xì)化了工件工藝為準(zhǔn)備、裝夾、加工、卸夾的時(shí)間流程，建立了集成橋式起重運(yùn)輸設(shè)備與機(jī)器加工的雙資源約束、多目標(biāo)優(yōu)化的綠色調(diào)度數(shù)學(xué)模型。基于快速非支配排序遺傳算法，結(jié)合實(shí)際車間調(diào)度問題，提出融合加工信息與運(yùn)輸信息的五段式編碼方法，并通過在算法流程中融入兩種啟發(fā)式選擇算子改進(jìn)整個(gè)調(diào)度工藝流程，以優(yōu)化車間全局目標(biāo)。

最后，以上海某船用曲軸公司G45、G50曲軸生產(chǎn)過程為例，用本文所提模型與算法進(jìn)行調(diào)度求解，并將雙資源約束集成化數(shù)學(xué)模型優(yōu)化結(jié)果，與不考慮運(yùn)輸狀態(tài)的單資源機(jī)器約束數(shù)學(xué)模型優(yōu)化結(jié)果進(jìn)行比對(duì)，驗(yàn)證了所建立模型的優(yōu)越性。

現(xiàn)實(shí)生產(chǎn)制造的情況是復(fù)雜多變的，本文的研究是基于無突發(fā)情況的制造車間，今后需要對(duì)具有不確定因素的制造車間進(jìn)行深入分析，例如，機(jī)器故障、人員擾動(dòng)、緊急訂單等情況。同時(shí)，多資源約束、多目標(biāo)優(yōu)化作業(yè)車間集成調(diào)度問題模型復(fù)雜，未來的研究中需要設(shè)計(jì)出求解精度更高、收斂速度更快的智能算法來解決此類集成調(diào)度問題。