面向云制造的混流混合車間調(diào)度問(wèn)題

魯建廈 胡慶輝 董巧英 湯洪濤

浙江工業(yè)大學(xué)機(jī)械工程學(xué)院，杭州，310014

面向云制造的混流混合車間調(diào)度問(wèn)題

魯建廈 胡慶輝 董巧英 湯洪濤

浙江工業(yè)大學(xué)機(jī)械工程學(xué)院，杭州，310014

為解決云制造環(huán)境下混流混合車間的生產(chǎn)調(diào)度優(yōu)化問(wèn)題，綜合考慮混流裝配與零部件加工的集成優(yōu)化以及外協(xié)云任務(wù)與自制任務(wù)的協(xié)同調(diào)度，建立了以最小化最大完工時(shí)間、均衡化零部件生產(chǎn)和最大化零件車間機(jī)器利用率為優(yōu)化指標(biāo)的多目標(biāo)車間調(diào)度模型。基于零件分批和車間調(diào)度的兩階段求解策略，設(shè)計(jì)了一種兩級(jí)遞階結(jié)構(gòu)的混合生物地理學(xué)優(yōu)化算法，采用在遷移算子中嵌入差分進(jìn)化算法的變異策略來(lái)提高算法的搜索效率。最后，通過(guò)實(shí)例驗(yàn)證了模型和算法的有效性。

云制造；混流混合車間；混合生物地理學(xué)優(yōu)化算法；零件分批；車間調(diào)度

0 引言

混流混合車間是一類具有多種類產(chǎn)品混流生產(chǎn)和多類別車間混合集成特征的車間，是目前裝配制造企業(yè)應(yīng)對(duì)多品種、小批量生產(chǎn)的較好車間形式。實(shí)際的離散裝配車間通常是由作業(yè)車間和流水車間組合而成的混合車間，產(chǎn)品生產(chǎn)過(guò)程一般包括零件加工、部件裝配和產(chǎn)品總裝。為適應(yīng)多品種、小批量生產(chǎn)，該類混合車間多采用混流裝配方式來(lái)平衡生產(chǎn)負(fù)荷，以減小流水車間產(chǎn)品切換對(duì)作業(yè)車間生產(chǎn)的影響，避免零件加工車間出現(xiàn)制造資源忙閑不均的現(xiàn)象。但是生產(chǎn)波動(dòng)難以完全消除，相比于單獨(dú)的作業(yè)車間，混流混合車間中的零件加工車間受后續(xù)流水車間混流裝配的需求約束，更易出現(xiàn)資源閑置的現(xiàn)象。近年來(lái)興起的云制造模式，為混流混合車間提升閑置資源的利用率提供了新的思路。云制造是一種利用網(wǎng)絡(luò)和云制造服務(wù)平臺(tái)，按用戶需求組織網(wǎng)上制造資源，為用戶提供各類按需制造服務(wù)的網(wǎng)絡(luò)化制造新模式[1]。通過(guò)云制造平臺(tái)的海量任務(wù)庫(kù)，車間中的制造資源可以充分利用閑置時(shí)段對(duì)外提供云服務(wù)，從而提高資源利用率。但隨著車間承接的外協(xié)云任務(wù)增多，企業(yè)自制任務(wù)受到的影響也越大，增加了自制產(chǎn)品零件加工與混流裝配的協(xié)調(diào)難度。要想通過(guò)云制造模式充分提高閑置資源的利用率，就需要協(xié)調(diào)好自制任務(wù)與外協(xié)云任務(wù)，避免盲目參與云制造而影響自制任務(wù)的生產(chǎn)。因此，面向云制造的混流混合車間調(diào)度必須將外協(xié)云任務(wù)與自制任務(wù)一起綜合考慮，進(jìn)行協(xié)同調(diào)度。

2015年國(guó)務(wù)院出臺(tái)了“中國(guó)制造2025”規(guī)劃，明確提出加快推動(dòng)信息化與工業(yè)化的深度融合，并把智能制造作為兩化融合的主攻方向[2]。作為我國(guó)智能制造的重點(diǎn)研究領(lǐng)域，云制造在理論架構(gòu)[3-4]和平臺(tái)實(shí)現(xiàn)[5-6]上已取得了較多成果。對(duì)于資源閑置現(xiàn)象明顯的混流混合車間，如何利用云制造模式提升制造資源利用率，構(gòu)建一個(gè)面向云制造的車間調(diào)度環(huán)境，己經(jīng)成為企業(yè)實(shí)施云制造模式轉(zhuǎn)型急需解決的關(guān)鍵問(wèn)題。

當(dāng)前，面向云制造的車間調(diào)度研究主要是針對(duì)單獨(dú)的作業(yè)車間構(gòu)建云環(huán)境下的調(diào)度模型：王軍強(qiáng)等[7]基于聚類算法提出了面向云制造的機(jī)器能力界定方法，并提出了一種云環(huán)境下的作業(yè)車間調(diào)度模型。孫月洲[8]建立了云環(huán)境下作業(yè)車間生產(chǎn)資源的動(dòng)態(tài)調(diào)度模型，并采用改進(jìn)遺傳算法進(jìn)行求解。楊屹[9]提出了事件驅(qū)動(dòng)的云制造車間調(diào)度架構(gòu)，通過(guò)對(duì)事件模式的匹配來(lái)處理調(diào)度過(guò)程中出現(xiàn)的擾動(dòng)事件?，F(xiàn)有的混流混合車間調(diào)度研究也均基于傳統(tǒng)制造模式，簡(jiǎn)化了外協(xié)加工任務(wù)，在調(diào)度模型中只考慮自制任務(wù)。李修琳等[10]以在制品成本最小為目標(biāo)，運(yùn)用集成模擬退火算法的混合遺傳算法來(lái)求解混流混合車間協(xié)同調(diào)度問(wèn)題。胡恒等[11]運(yùn)用多群體并行遺傳算法求解混流混合車間模糊調(diào)度問(wèn)題。目前關(guān)于面向云制造的混流混合車間調(diào)度研究，以及綜合考慮外協(xié)云任務(wù)與自制任務(wù)的車間調(diào)度模型均未見(jiàn)報(bào)道。

本文選取與實(shí)際離散裝配生產(chǎn)契合度較高的混流混合車間，以云制造模式為背景，以提升制造資源整體利用率為切入點(diǎn)，綜合考慮車間承接的外協(xié)云任務(wù)與自制任務(wù)，探索一種云環(huán)境下混流混合車間協(xié)同調(diào)度問(wèn)題的模型和求解方法。

1 問(wèn)題描述

1.1 面向云制造的混流混合車間模型描述

云制造平臺(tái)上的外協(xié)任務(wù)按照粒度大小可分為產(chǎn)品級(jí)、部件級(jí)、零件級(jí)和工序級(jí)。本文研究的面向云制造的混流混合車間主要承接零件級(jí)和工序級(jí)的外協(xié)云任務(wù)。該車間由三部分構(gòu)成：第一部分為加工零件的作業(yè)車間，可對(duì)外提供云服務(wù)；第二、第三部分分別為裝配部件和成品的流水車間，以生產(chǎn)自制產(chǎn)品為主。圖1所示為面向云制造的混流混合車間簡(jiǎn)化模型。

圖1 面向云制造的混流混合車間簡(jiǎn)化模型Fig.1 Simplified model of cloud manufacturing- oriented mixed-model hybrid shop

自制任務(wù)與外協(xié)云任務(wù)在零件加工車間的主要區(qū)別在于生產(chǎn)批量的變動(dòng)性。自制零件的生產(chǎn)受混流裝配最小生產(chǎn)循環(huán)的需求約束，在一定時(shí)間段內(nèi)的需求量較為穩(wěn)定，通常采用等量分批的策略，即每個(gè)批次的批量相等且固定?，F(xiàn)有的混流混合車間調(diào)度研究在進(jìn)行零件加工車間生產(chǎn)排序時(shí)均采用固定的生產(chǎn)批量[10-11]。完成外協(xié)云任務(wù)時(shí)，由于沒(méi)有后續(xù)車間的約束，因此不同批次的生產(chǎn)批量可以變化。采用變動(dòng)批量進(jìn)行零件加工車間的生產(chǎn)排序有利于充分利用制造資源的閑置時(shí)段。

綜上可得面向云制造的混流混合車間主要特點(diǎn)：①零件加工車間可對(duì)外承接外協(xié)云任務(wù)，同時(shí)生產(chǎn)自制產(chǎn)品和云服務(wù)產(chǎn)品(分別采用等量分批和柔性分批策略)；②部件裝配車間和產(chǎn)品總裝車間都以混流方式組織生產(chǎn)，只生產(chǎn)自制產(chǎn)品；③零件加工車間以批為單位組織生產(chǎn)，部件裝配和產(chǎn)品總裝車間以個(gè)為單位組織生產(chǎn)；④各車間通過(guò)物料需求約束關(guān)聯(lián)，由緩沖區(qū)連接。

1.2 面向云制造的混流混合車間調(diào)度模型構(gòu)建

面向云制造的混流混合車間調(diào)度問(wèn)題數(shù)學(xué)描述如下：零件加工車間有M臺(tái)機(jī)器，加工Z種自制產(chǎn)品的零件和Y種外協(xié)云任務(wù)的零件，每種零件工藝順序已知，并且每種零件可分成若干批次，各個(gè)子批量當(dāng)作一個(gè)整體來(lái)處理，共享同一批次的啟動(dòng)時(shí)間(包括準(zhǔn)備時(shí)間和搬運(yùn)時(shí)間)，自制任務(wù)等量分批、批量相等，外協(xié)云任務(wù)柔性分批、批量變動(dòng)；部件裝配車間有一條含N個(gè)工位的部件裝配流水線，有R種不同型號(hào)的部件以相同順序依次通過(guò)流水線的所有工位完成裝配；產(chǎn)品總裝車間有一條含S個(gè)工位的總裝流水線，裝配I種訂單產(chǎn)品。生產(chǎn)調(diào)度就是確定產(chǎn)品總裝車間和部件裝配車間的裝配序列，以及零件加工車間自制任務(wù)零件和外協(xié)任務(wù)零件的批次分割和生產(chǎn)順序，使既定的調(diào)度目標(biāo)最優(yōu)。

1.2.1 目標(biāo)函數(shù)

車間調(diào)度研究中常用的一個(gè)評(píng)價(jià)指標(biāo)是最大完工時(shí)間，它能夠體現(xiàn)出生產(chǎn)系統(tǒng)效率的高低，因此選取最小化最大完工時(shí)間為優(yōu)化目標(biāo)?；炝魃a(chǎn)的目的是使零部件的消耗速率盡可能穩(wěn)定，從而保證零件加工車間和部件裝配車間能夠勻速穩(wěn)定地進(jìn)行生產(chǎn)，因此將均衡化零部件生產(chǎn)作為混流混合車間調(diào)度的一個(gè)特殊優(yōu)化目標(biāo)。此外，零件車間參與云制造的目的在于充分提升制造資源的整體利用率，因此將最大化零件車間資源利用率也作為優(yōu)化目標(biāo)。

(1)最小化最大完工時(shí)間。系統(tǒng)中存在兩類生產(chǎn)任務(wù)，對(duì)于自制任務(wù)而言，產(chǎn)品總裝是最后一道工序，取總裝車間的最大完工時(shí)間為自制任務(wù)的最大完工時(shí)間；外協(xié)云任務(wù)只在零件加工車間生產(chǎn)，取外協(xié)任務(wù)在零件車間的最大完工時(shí)間為外協(xié)云任務(wù)的最大完工時(shí)間，建立最小化最大完工時(shí)間模型：

(1)

(2)均衡化零部件生產(chǎn)。參考文獻(xiàn)[12]，將總裝—部件兩級(jí)流水車間進(jìn)一步擴(kuò)展到總裝—部件—零件三級(jí)混合車間中，建立零部件消耗均衡化模型：

(2)

(3)

(4)

(5)

(6)

(7)

式中，Urj為完成裝配序列中前j個(gè)產(chǎn)品需要部件r的數(shù)量；Pr為完成裝配序列中所有產(chǎn)品需要部件r的總數(shù)量；Vzj為完成裝配序列中前j個(gè)產(chǎn)品需要自制零件z的數(shù)量；Qz為完成裝配序列中所有產(chǎn)品需要自制零件z的總數(shù)量；Gir為裝配一件產(chǎn)品i需要部件r的數(shù)量；Liz為裝配一件產(chǎn)品i需要自制零件z的數(shù)量；bi為產(chǎn)品i的需求數(shù)量；Wij為指示變量，用于判斷產(chǎn)品在生產(chǎn)序列中的順序。

(3)最大化零件加工車間機(jī)器利用率。為了與前述目標(biāo)一致，將其轉(zhuǎn)化成最小化機(jī)器閑置時(shí)間：

(8)

式中，F(xiàn)m為機(jī)器m的閑置時(shí)間；Tm為機(jī)器m的最大加工時(shí)間。

1.2.2 模型約束

針對(duì)產(chǎn)品總裝車間、部件裝配車間和零件加工車間的不同特點(diǎn)建立各自的約束條件。

(1)產(chǎn)品總裝車間約束?？傃b車間的調(diào)度主要是對(duì)投產(chǎn)序列進(jìn)行優(yōu)化，排序和調(diào)度的結(jié)果以第一個(gè)工位的投產(chǎn)序列表示。在生產(chǎn)序列中，每個(gè)位置只能出現(xiàn)一個(gè)產(chǎn)品；每種產(chǎn)品在序列中出現(xiàn)的次數(shù)等于該產(chǎn)品需要加工的數(shù)量，該約束表達(dá)式為

(9)

(10)

總裝車間的裝配工位只有在零部件齊套的情況下才能開(kāi)始裝配。此時(shí)，產(chǎn)品總裝完工時(shí)間等于該產(chǎn)品進(jìn)入工位的時(shí)間與裝配操作時(shí)間以及在該工位停工待料的時(shí)間之和，該約束表達(dá)式為

WijEis=max(Ei(s-1),Wk(j-1)Eks)+tis+Δis

(11)

(12)

式中，tis為產(chǎn)品i在工位s上的裝配時(shí)間；Δis為產(chǎn)品i在工位s上停工待料的時(shí)間；Azst、Azst′分別為在t和t′時(shí)刻產(chǎn)品總裝車間工位s含有自制零件z的數(shù)量；Arst、Arst′分別為在t和t′時(shí)刻產(chǎn)品總裝車間工位s含有部件r的數(shù)量；Cizs、Cirs分別為產(chǎn)品i在工位s上裝配需要自制零件z和部件r的數(shù)量。

(2)部件裝配車間約束。與總裝車間一樣，部件裝配車間也存在生產(chǎn)序列約束和零件齊套約束，約束表達(dá)式為

(13)

(14)

(15)

HrkErn=max(Er(n-1),Wr′(n-1)Er′n)+trn+Δrn

(16)

(17)

式中，Ern、Er′n分別為部件裝配車間部件r和r′在工位n上的完工時(shí)刻；trn為部件r在工位n上的裝配時(shí)間；Δrn為部件r在工位n上停工待料的時(shí)間；Aznt、Aznt′分別為在t和t′時(shí)刻部件裝配車間工位n含有自制零件z的數(shù)量；Crzn為部件r在工位n上裝配時(shí)需要自制零件z的數(shù)量。

(3)零件加工車間約束。零件加工車間中，同批零件之間存在工藝順序約束，即一批零件需完成前一道工序后，才能加工后一道工序，該約束表達(dá)式為

Edpm-tdpm+D(1-adpm′m)≥Edpm′

(18)

(19)

(20)

(21)

tdpm=wdm+Xdt″dm/cd

(22)

(23)

(24)

此外，不同批零件之間還存在資源約束，即在同一臺(tái)機(jī)器上，完成前一批零件的加工任務(wù)后才能開(kāi)始下一批加工，該約束表達(dá)式為

Ed′p′m-Edpm+D(1-bdpd′p′m)≥td′p′m

(25)

(26)

(27)

(28)

(29)

(30)

2 模型求解算法設(shè)計(jì)

生物地理學(xué)優(yōu)化(biogeography-based optimization，BBO)算法[13]是一種模擬自然界種群遷移規(guī)律的新型智能優(yōu)化算法，不同于其他智能算法每次迭代都要淘汰劣解、產(chǎn)生新解，它通過(guò)獨(dú)特的遷移機(jī)制在種群中分享較優(yōu)變量，并不直接產(chǎn)生新的子代，這種直接影響更有助于提高較差解的性能，加快全局搜索。本文研究的調(diào)度模型涉及多類型和多層級(jí)的混合車間，并且存在批量劃分問(wèn)題，解的搜索空間極大，需要搜索效率較高的求解算法。BBO全局高效搜索的特點(diǎn)對(duì)該問(wèn)題具有較好的優(yōu)化效果。目前，BBO在作業(yè)車間調(diào)度問(wèn)題上已得到成功應(yīng)用[14-15]，與差分進(jìn)化(differential evolution，DE)算法結(jié)合的混合算法也取得了良好的效果[16]。因此，本文建立一種混合算法，以BBO算法為主體，在遷移算子中嵌入DE算法。DE算法可有效提高鄰域搜索效率，彌補(bǔ)BBO算法在局部搜索方面的不足。

2.1 算法總體思想

面向云制造的混流混合車間調(diào)度模型涉及多個(gè)車間的調(diào)度策略，且零件加工車間中存在批量劃分問(wèn)題，批量劃分的結(jié)果直接影響到后續(xù)各車間調(diào)度排序的優(yōu)化效果，因此如何確定最佳批次以及各批次中的工件數(shù)量顯得至關(guān)重要。參照分層法將調(diào)度過(guò)程分為零件分批和車間調(diào)度兩個(gè)階段：第一階段考慮零件車間的加工任務(wù)如何分批；第二階段對(duì)各車間進(jìn)行調(diào)度排序。在分批階段的一次迭代過(guò)程中，分批方案確定后，各零件的批數(shù)以及各批次的工件數(shù)量均已確定，故第二階段的調(diào)度優(yōu)化可視為常規(guī)性的混流混合車間調(diào)度問(wèn)題，它以第一階段的分批結(jié)果為調(diào)度對(duì)象，搜索當(dāng)前分批結(jié)果的最優(yōu)排產(chǎn)方案。因此，該算法采用兩層嵌套的形式，外層產(chǎn)生分批方案，內(nèi)層相當(dāng)于解碼函數(shù)，被外層頻繁調(diào)用，產(chǎn)生調(diào)度方案。

2.2 算法關(guān)鍵及細(xì)節(jié)

2.2.1 算法編碼

針對(duì)零件分批和車間調(diào)度兩個(gè)階段，采用不同的編碼方式：第一階段分別采用整數(shù)編碼和二進(jìn)制編碼對(duì)零件車間中的自制任務(wù)和外協(xié)任務(wù)進(jìn)行批量劃分；第二階段采用整數(shù)編碼對(duì)3個(gè)車間進(jìn)行調(diào)度排序。

2.2.1.1 零件分批階段編碼

批次劃分的理想情況是將單個(gè)零件作為編碼的最小單位。但這種方式會(huì)使解的搜索空間很大，不利于算法運(yùn)行，而且考慮到機(jī)器調(diào)整時(shí)間，以單個(gè)零件為一個(gè)批次的情況不現(xiàn)實(shí)。因此，參考實(shí)際生產(chǎn)中的最小生產(chǎn)批量以某個(gè)固定量為編碼的最小單位。

2.2.1.2 車間調(diào)度階段編碼

以上一階段確定的分批結(jié)果為輸入，建立一個(gè)三段式編碼：第一部分為零件加工車間編號(hào)，第二部分為部件裝配車間編號(hào)，第三部分為產(chǎn)品總裝車間編號(hào)。其中，產(chǎn)品總裝車間和部件裝配車間是流水車間，可以根據(jù)各產(chǎn)品/部件的數(shù)量比例來(lái)確定最小生產(chǎn)循環(huán)，采用基于工件的編碼方式對(duì)一個(gè)循環(huán)中的裝配序列進(jìn)行編號(hào)，相同數(shù)字代表相同工件，維度為工件數(shù)量。零件加工車間采用基于工序的編碼方式，每位編碼由兩位數(shù)字組成，第一位數(shù)字代表零件，第二位數(shù)字代表批次，如“11”表示零件1的第一個(gè)批次。相同編碼代表相同零件及批次，且出現(xiàn)次序表示加工順序，如首先出現(xiàn)的“11”表示零件1第一個(gè)批次的第一道工序，第二個(gè)出現(xiàn)的“11”表示零件1第一個(gè)批次的第二道工序，維度為零件批次總數(shù)和工序總數(shù)的乘積。圖2所示為兩階段編碼的一個(gè)示例，第一階段產(chǎn)生分批結(jié)果，第二階段產(chǎn)生調(diào)度結(jié)果。

圖2 兩階段棲息地編碼示例Fig.2 Example of two level hierarchical structures coding

2.2.2 棲息地適宜指數(shù)

針對(duì)多目標(biāo)優(yōu)化問(wèn)題，結(jié)合Pareto排序和密度信息來(lái)確定棲息地適宜指數(shù)：

IHS(i)=R(i)+D(i)

(31)

(32)

S(i)=|{j|j∈P+Q∧i?j}|

(33)

(34)

(35)

其中，R(i)為原始適應(yīng)度，表示有多少個(gè)解比該解更優(yōu)；D(i)為密度值，用來(lái)比較具有相同R(i)值的解的優(yōu)劣；符號(hào)|·|表示集合的規(guī)模；符號(hào)?表示Pareto支配關(guān)系；S(i)為個(gè)體強(qiáng)度，代表其所支配個(gè)體的數(shù)目；σik為個(gè)體i與第k個(gè)相鄰個(gè)體的歐氏距離。

2.2.3 遷移策略

為提高算法的搜索能力，在標(biāo)準(zhǔn)遷移算子中通過(guò)交叉參數(shù)的方式引入DE的變異策略?，F(xiàn)有的BBO-DE混合算法研究主要是針對(duì)獨(dú)立的連續(xù)型變量，而文本研究的調(diào)度問(wèn)題中，棲息地編碼是存在約束關(guān)系的離散變量?？紤]到調(diào)度問(wèn)題的特點(diǎn)，不對(duì)特征向量本身而是對(duì)其在編碼中所處的位置進(jìn)行差分?jǐn)_動(dòng)，混合遷移算子為

(36)

式中，h(k)為隨機(jī)選取的工件k在編碼中首次出現(xiàn)的位置；rbest為最優(yōu)解；r1、r2為隨機(jī)選擇的兩個(gè)不同解；rj為根據(jù)遷出概率選取的較優(yōu)解；g為縮放因子；RC為交叉參數(shù)；ceil(·)表示向上取整函數(shù)。

針對(duì)零件分批和車間調(diào)度兩階段的編碼特點(diǎn)，設(shè)計(jì)不同的遷移操作，具體如下：在零件分批階段，隨機(jī)選擇一種零件，將遷出個(gè)體中該零件的分批編碼整段替換到遷入個(gè)體中，如圖3a所示；在車間調(diào)度階段，分別對(duì)三段編碼各自進(jìn)行遷移，防止不同車間調(diào)度工件的串碼。針對(duì)每一段車間編碼，首先隨機(jī)選擇一種工件，再按式(36)確定該組工件首次出現(xiàn)的位置。該組工件的其余個(gè)體按其在遷出個(gè)體向量中的相應(yīng)距離插入到遷入個(gè)體中，最后將剩余工件按在遷入個(gè)體向量中的順序依次重新排列，如圖3b所示。

(a)零件分批階段遷移操作

(b)車間調(diào)度階段遷移操作圖3 兩階段遷移操作過(guò)程Fig.3 Two stage migration process

2.2.4 變異策略

針對(duì)零件分批和車間調(diào)度兩個(gè)階段分別設(shè)計(jì)不同的變異操作，具體如下：零件分批階段，采用單點(diǎn)變異的方式，如圖4a所示；車間調(diào)度階段，分別對(duì)三段編碼各自進(jìn)行變異操作，采用子序列隨機(jī)變異的方式，即從整段編碼中任選兩個(gè)編號(hào)不同的位置，將這兩個(gè)位置之間的子序列進(jìn)行隨機(jī)排列，形成新的個(gè)體，如圖4b所示。

2.3 算法流程

針對(duì)零件分批和車間調(diào)度兩個(gè)階段采用兩層嵌套結(jié)構(gòu)，外層算法產(chǎn)生分批方案，針對(duì)每個(gè)分批結(jié)果調(diào)用內(nèi)層算法，產(chǎn)生相應(yīng)的調(diào)度方案。圖5所示為算法的整體流程，P、Q分別表示算法中零件分批階段的內(nèi)外部種群；P′、Q′分別表示車間調(diào)度階段的內(nèi)外部種群。

(a)零件分批階段變異操作

(b)車間調(diào)度階段變異操作圖4 兩階段變異操作過(guò)程Fig.4 Two stage variant process

圖5 兩階段混合生物地理學(xué)優(yōu)化算法流程圖Fig.5 Flow chart of two-stage hybrid biogeography-based optimization

3 實(shí)例驗(yàn)證

以某裝配制造企業(yè)在云制造環(huán)境下的生產(chǎn)調(diào)度為例，對(duì)模型和算法進(jìn)行驗(yàn)證。該企業(yè)的生產(chǎn)系統(tǒng)是由零件加工車間、部件裝配車間和產(chǎn)品總裝車間組成的混流混合車間。產(chǎn)品總裝車間共有10個(gè)工位，裝配P1、P2、P3三種產(chǎn)品，對(duì)應(yīng)的工藝和作業(yè)時(shí)間如表1所示。裝配1個(gè)產(chǎn)品P1分別需要零件Z1、零件Z2和部件R1各1個(gè)；裝配1個(gè)產(chǎn)品P2分別需要零件Z2、零件Z3和部件R2各1個(gè)；裝配1個(gè)產(chǎn)品P3分別需要零件Z1、零件Z3和部件R3各1個(gè)。部件裝配車間有5個(gè)工位，裝配R1、R2、R3三種部件，對(duì)應(yīng)的工藝和作業(yè)時(shí)間如表2所示。裝配1個(gè)部件R1需要1個(gè)零件Z4；裝配1個(gè)部件R2需要1個(gè)零件Z5；裝配1個(gè)部件R3需要1個(gè)零件Z6。零件加工車間除生產(chǎn)6種自制零件外，還參與云制造服務(wù)，并在此計(jì)劃期內(nèi)承接了3種外協(xié)零件的訂單。表3、表4所示分別為外協(xié)零件和自制零件的工藝及作業(yè)時(shí)間，逗號(hào)前后分別為批次啟動(dòng)時(shí)間和單個(gè)零件加工時(shí)間。

表1 產(chǎn)品總裝車間工藝及時(shí)間Tab.1 Process and time of product assembly shop s

表2 部件裝配車間工藝及時(shí)間Tab.2 Process and time of parts assembly shop s

表3 零件加工車間外協(xié)零件工藝及時(shí)間Tab.3 Process and time of cloud service task in parts shop

表4 零件加工車間自制零件工藝及時(shí)間Tab.4 Process and time of self-made task in parts shop

計(jì)劃期內(nèi)，自制任務(wù)產(chǎn)品P1、P2、P3的生產(chǎn)任務(wù)分別為100、200、100。將其分解為部件級(jí)和零件級(jí)，則部件R1、R2、R3的生產(chǎn)任務(wù)分別為100、200、100；自制零件Z1、Z2、Z3、Z4、Z5、Z6的生產(chǎn)任務(wù)分別為200、300、300、100、200、100。外協(xié)云任務(wù)產(chǎn)品Y1、Y2、Y3的生產(chǎn)任務(wù)分別為150、200、200。各零件的最小生產(chǎn)批量均設(shè)為50。

設(shè)定算法參數(shù)：內(nèi)部種群數(shù)量為50，外部種群數(shù)量為20，最大遷入率為1，最大遷出率為1，最大變異率為0.05，最大迭代次數(shù)為100，交叉參數(shù)為0.1。以MATLAB為算法平臺(tái)進(jìn)行求解運(yùn)算。取最佳結(jié)果之一，得到分批編碼{2-3-3-1-2-1}、{1-0-1-1-0-0-1-0}和三段式調(diào)度編碼{11-11-11-51-51-21-21-51-51- 61-61-61-81-82-91-91-21-31-31-52-52-92-52-52-31-32-12-32-32-91-91-41-41-41-41-12-71-71-71-33-33-22-22-23-23-22-23-23-33-81-82-12-72-72-72-92-92-92-83-83}-{2-3-2-1}-{2-3-2-1}。對(duì)應(yīng)6種自制零件的批次分別為2、3、3、1、2、1，批量均為100；外協(xié)零件Y1分為2批，批量分別為50和100；外協(xié)零件Y2分為3批，批量分批為50、50和100；外協(xié)零件Y3分為2批，批量均為100；最小化均衡系數(shù)為4.9375，最小完成時(shí)間為7926 s，零件車間設(shè)備最小閑置率為13.8%。其中，總裝車間最小生產(chǎn)循環(huán)為{P2-P3-P2-P1}，部件車間最小生產(chǎn)循環(huán)為{R2-R3-R2-R1}，零件車間調(diào)度結(jié)果如圖6所示。

圖6 零件加工車間調(diào)度甘特圖Fig.6 Parts shop scheduling Gantt chart

針對(duì)上述實(shí)例，分別采用基于矩陣編碼的標(biāo)準(zhǔn)BBO算法與本文提出的兩階段混合BBO算法，求解結(jié)果如表5所示。

表5 求解結(jié)果對(duì)比表Tab.5 Results comparison table

表5所示結(jié)果表明，兩階段混合BBO比標(biāo)準(zhǔn)BBO求解效果更好、搜索時(shí)間更短。兩階段混合BBO算法先分批、后調(diào)度的策略避免了每次迭代時(shí)批次變動(dòng)對(duì)調(diào)度編碼長(zhǎng)度的調(diào)整，且多階段的搜索降低了重復(fù)搜索的概率，提高了搜索效率。混合遷移算子的設(shè)計(jì)也增強(qiáng)了算法局部搜索的能力，避免陷入局部最優(yōu)。

4 結(jié)語(yǔ)

結(jié)合云制造模式，關(guān)注混流混合車間閑置資源制造能力的提升，研究外協(xié)云任務(wù)和自制任務(wù)的協(xié)同調(diào)度問(wèn)題。以最小化最大完工時(shí)間、均衡化零部件生產(chǎn)和最大化零件車間機(jī)器利用率為目標(biāo)建立調(diào)度模型，在零件車間中采用不同的批量劃分策略，協(xié)調(diào)外協(xié)任務(wù)與自制任務(wù)。在求解算法上，采用先分批、后調(diào)度的兩階段求解策略，設(shè)計(jì)了一種集成差分進(jìn)化的混合生物地理學(xué)優(yōu)化算法。通過(guò)某離散裝配制造企業(yè)在云制造環(huán)境下的車間調(diào)度實(shí)例，驗(yàn)證了所建模型和算法的有效性。所研究的面向云制造的混流混合車間協(xié)同調(diào)度問(wèn)題，為車間協(xié)調(diào)自制任務(wù)和外協(xié)云任務(wù)的生產(chǎn)調(diào)度提供了有效方法，為提升車間整體效率提供了新的思路。云制造環(huán)境下，企業(yè)間的資源共享與協(xié)作十分頻繁，不僅可以為其他企業(yè)提供本單位的閑置能力，也可以對(duì)外尋求本單位不足的加工資源。本文只考慮了對(duì)外提供云服務(wù)時(shí)，外協(xié)云任務(wù)與自制任務(wù)的協(xié)同調(diào)度問(wèn)題?？紤]同時(shí)接受和提供云服務(wù)情況下的協(xié)同調(diào)度問(wèn)題將是下一步研究方向。

[1] 李伯虎，張霖，王時(shí)龍，等.云制造——面向服務(wù)的網(wǎng)絡(luò)化制造新模式[J].計(jì)算機(jī)集成制造系統(tǒng)，2010，16(1)：1-7，16. LI Bohu，ZHANG Lin，WANG Shilong，et al. Cloud Manufacturing：A New Service-oriented Networked Manufacturing Model[J]. Computer Integrated Manufacturing Systems，2010，16(1)：1-7，16.

[2] 周濟(jì).智能制造——“中國(guó)制造2025”的主攻方向[J].中國(guó)機(jī)械工程，2015，26(17)：2273-2284. ZHOU Ji. Intelligent Manufacturing—Main Direction of “Made in China 2025” [J].China Mechanical Engineering， 2015，26(17)：2273-2284.

[3] ADAMSON G，WANG L H，HOLMA M，et al.Cloud Manufacturing—A Critical Review of Recent Development and Future Trends[J]. International Journal of Computer Integrated Manufacturing，2015：1-34.DOI: 10.1080/0951192x.2015.1031704.

[4] WANG X V，XU X W.An Interoperable Solution for Cloud Manufacturing[J]. Robotics and Computer-Integrated Manufacturing，2013，29(4)：232-247.

[5] 戰(zhàn)德臣，趙曦濱，王順強(qiáng)，等.面向制造及管理的集團(tuán)企業(yè)云制造服務(wù)平臺(tái)[J].計(jì)算機(jī)集成制造系統(tǒng)，2011，17(3)：487-494. ZHAN Dechen，ZHAO Xibin，WANG Shungqiang，et al. Cloud Manufacturing Service Platform for Group Enterprises-oriented to Manufacturing and Management[J]. Computer Integrated Manufacturing Systems，2011，17(3)：487-494.

[6] 顧新建，黃沈權(quán)，陳笈熙，等. 模具行業(yè)需求驅(qū)動(dòng)的云制造服務(wù)平臺(tái)[J]. 計(jì)算機(jī)集成制造系統(tǒng)，2012，18(7)：1650-1656. GU Xinjian，HUANG Shenquan，CHEN Jixi，et al. Cloud Manufacturing Service Platform Driven by Mold Manufacturing Industry Demand [J]. Computer Integrated Manufacturing Systems，2012，18(7)：1650-1656.

[7] 王軍強(qiáng)，崔福東，張承武，等.面向云制造作業(yè)車間的機(jī)器能力界定方法[J]. 計(jì)算機(jī)集成制造系統(tǒng)，2014，20(9)：2146-2163. WANG Junqiang，CUI Fudong，ZHANG Chengwu，et al. Capacity Partition Method of Machines in Cloud Manufacturing-oriented Job Shops[J]. Computer Integrated Manufacturing Systems，2014，20(9)：2146-2163.

[8] 孫月洲.云制造車間資源調(diào)度與配置模型及優(yōu)化研究[D].哈爾濱：哈爾濱理工大學(xué)，2012. SUN Yuezhou. Study on Modeling and Optimization Method of Resource Scheduling and Allocation in Cloud Manufacturing Workshop[D]. Harbin：Harbin University of Science and Technology，2012.

[9] 楊屹.事件驅(qū)動(dòng)的云制造車間調(diào)度研究[D].廣州：華南理工大學(xué)，2014. YANG Yi. Study on Event Driven Cloud Manufacturing Shop Scheduling[D]. Guangzhou：South China University of Technology，2014.

[10] 李修琳，魯建廈，柴國(guó)鐘，等. 基于混合遺傳算法的混流混合車間協(xié)同調(diào)度問(wèn)題[J]. 中國(guó)機(jī)械工程，2012，23(8)：935-940. LI Xiulin，LU Jiansha，CHAI Guozhong，et al. Hybrid Genetic Algorithm for Mixed-model Hybrid-shop Scheduling Problem[J]. China Mechanical Engineering，2012，23(8)：935-940.

[11] 胡恒，魯建廈，李英德，等.基于多群體并行遺傳算法的混流混合車間模糊調(diào)度研究[J].浙江工業(yè)大學(xué)學(xué)報(bào)，2012，40(5)：554-558. HU Heng，LU Jiansha，LI Yingde, et al. Study of Mixed-mode Hybrid Shop Fuzzy Scheduling Problem Based on Multi-populations Parallel Genetic Algorithm[J]. Journal of Zhejiang University of Technology，2012，40(5)：554-558.

[12] 王炳剛. 混流加工/裝配系統(tǒng)集成優(yōu)化研究[J]. 機(jī)械工程學(xué)報(bào)，2010，46(17)：114-121.

WANG Binggang. Research on Integrated Optimization for Mixed-model Fabrication/assembly Systems[J]. Journal of Mechanical Engineering，2010，46(17)：114-121.

[13] SIMON D. Biogeography-based Optimization[J]. IEEE Transactions on Evolutionary Computation，2008，12(6)：702-713.

[14] RAHMATI S H A，ZANDIEH M.A New Biogeography-based Optimization (BBO) Algorithm for the Flexible Job Shop Scheduling Problem [J]. The International Journal of Advanced Manufacturing Technology，2012，58(9/12)：1115-1129.

[15] 張國(guó)輝，聶黎，毛學(xué)港.生物地理學(xué)算法求解柔性作業(yè)車間調(diào)度問(wèn)題[J].計(jì)算機(jī)應(yīng)用研究，2014，31(4)：1005-1008. ZHANG Guohui，NIE Li，MAO Xuegang. Solving Flexible Job-shop Scheduling Problem Based on Biogeography-based Optimization Algorithm[J]. Application Research of Computers，2014，31(4)：1005-1008.

[16] 葉開(kāi)文，劉三陽(yáng)，高衛(wèi)峰.基于差分進(jìn)化的生物地理學(xué)優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用，2012，32(11)：2981-2984. YE Kaiwen，LIU Sanyang，GAO Weifeng. Biogeography-based Optimization Algorithm of Differential Evolution[J]. Journal of Computer Applications，2012，32(11)：2981-2984.

(編輯 張 洋)

Cloud Manufacturing-oriented Mixed-model Hybrid Shop-scheduling Problem

LU Jiansha HU Qinghui DONG Qiaoying TANG Hongtao

College of Mechanical Engineering,Zhejiang University of Technology,Hangzhou,310014

To solve the scheduling problems for cloud manufacturing-oriented mixed-model hybrid shop, considering the integrated optimization of mixed flow assembly and part processing, and collaborative scheduling of cloud service tasks and self-made tasks, the model was presented based on three objectives: minimizing the makespan, production smoothing of parts, and maximizing the utilization rate of the job shop. Then, a hybrid BBO algorithm with two level hierarchical structures was proposed to solve the model. In the hybrid algorithm, batching strategy was put forward in the first level and hybrid shop scheduling was designed in the second level. Moreover, a mutation strategy of differential evolution algorithm was introduced to the transport operator of BBO to improve the searching efficiency. Finally, an example was given to test the model and algorithm, and the results demonstrat the feasibility and effectiveness of the method.

cloud manufacturing； mixed-model hybrid shop； hybrid biogeography-based optimization(BBO)； part batching； shop-scheduling

2016-03-02

浙江省自然科學(xué)基金資助項(xiàng)目(LY15G010009，LQ14E050004)

TB491

10.3969/j.issn.1004-132X.2017.02.011

魯建廈，男，1963年生。浙江工業(yè)大學(xué)機(jī)械工程學(xué)院教授、博士研究生導(dǎo)師。主要研究方向?yàn)榫嫔a(chǎn)、智能制造。發(fā)表論文97篇。E-mail：ljx@zjut.edu.cn。胡慶輝，男，1991年生。浙江工業(yè)大學(xué)機(jī)械工程學(xué)院碩士研究生。董巧英，女，1977年生。浙江工業(yè)大學(xué)機(jī)械工程學(xué)院講師、博士后研究人員。湯洪濤，男，1976年生。浙江工業(yè)大學(xué)機(jī)械工程學(xué)院副教授。