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

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

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

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

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

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

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

0 引言

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

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

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

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

1 問題描述

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

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

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

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

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

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

面向云制造的混流混合車間調(diào)度問題數(shù)學(xué)描述如下：零件加工車間有M臺機(jī)器，加工Z種自制產(chǎn)品的零件和Y種外協(xié)云任務(wù)的零件，每種零件工藝順序已知，并且每種零件可分成若干批次，各個子批量當(dāng)作一個整體來處理，共享同一批次的啟動時間(包括準(zhǔn)備時間和搬運時間)，自制任務(wù)等量分批、批量相等，外協(xié)云任務(wù)柔性分批、批量變動；部件裝配車間有一條含N個工位的部件裝配流水線，有R種不同型號的部件以相同順序依次通過流水線的所有工位完成裝配；產(chǎn)品總裝車間有一條含S個工位的總裝流水線，裝配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)度研究中常用的一個評價指標(biāo)是最大完工時間，它能夠體現(xiàn)出生產(chǎn)系統(tǒng)效率的高低，因此選取最小化最大完工時間為優(yōu)化目標(biāo)?；炝魃a(chǎn)的目的是使零部件的消耗速率盡可能穩(wěn)定，從而保證零件加工車間和部件裝配車間能夠勻速穩(wěn)定地進(jìn)行生產(chǎn)，因此將均衡化零部件生產(chǎn)作為混流混合車間調(diào)度的一個特殊優(yōu)化目標(biāo)。此外，零件車間參與云制造的目的在于充分提升制造資源的整體利用率，因此將最大化零件車間資源利用率也作為優(yōu)化目標(biāo)。

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

(1)

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

(2)

(3)

(4)

(5)

(6)

(7)

式中，Urj為完成裝配序列中前j個產(chǎn)品需要部件r的數(shù)量；Pr為完成裝配序列中所有產(chǎn)品需要部件r的總數(shù)量；Vzj為完成裝配序列中前j個產(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ī)器閑置時間：

(8)

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

1.2.2 模型約束

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

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

(9)

(10)

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

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

(11)

(12)

式中，tis為產(chǎn)品i在工位s上的裝配時間；Δis為產(chǎn)品i在工位s上停工待料的時間；Azst、Azst′分別為在t和t′時刻產(chǎn)品總裝車間工位s含有自制零件z的數(shù)量；Arst、Arst′分別為在t和t′時刻產(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上的完工時刻；trn為部件r在工位n上的裝配時間；Δrn為部件r在工位n上停工待料的時間；Aznt、Aznt′分別為在t和t′時刻部件裝配車間工位n含有自制零件z的數(shù)量；Crzn為部件r在工位n上裝配時需要自制零件z的數(shù)量。

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

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

(18)

(19)

(20)

(21)

tdpm=wdm+Xdt″dm/cd

(22)

(23)

(24)

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

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

(25)

(26)

(27)

(28)

(29)

(30)

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

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

2.1 算法總體思想

面向云制造的混流混合車間調(diào)度模型涉及多個車間的調(diào)度策略，且零件加工車間中存在批量劃分問題，批量劃分的結(jié)果直接影響到后續(xù)各車間調(diào)度排序的優(yōu)化效果，因此如何確定最佳批次以及各批次中的工件數(shù)量顯得至關(guān)重要。參照分層法將調(diào)度過程分為零件分批和車間調(diào)度兩個階段：第一階段考慮零件車間的加工任務(wù)如何分批；第二階段對各車間進(jìn)行調(diào)度排序。在分批階段的一次迭代過程中，分批方案確定后，各零件的批數(shù)以及各批次的工件數(shù)量均已確定，故第二階段的調(diào)度優(yōu)化可視為常規(guī)性的混流混合車間調(diào)度問題，它以第一階段的分批結(jié)果為調(diào)度對象，搜索當(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 算法編碼

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

2.2.1.1 零件分批階段編碼

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

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

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

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

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

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

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

(31)

(32)

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

(33)

(34)

(35)

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

2.2.3 遷移策略

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

(36)

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

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

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

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

2.2.4 變異策略

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

2.3 算法流程

針對零件分批和車間調(diào)度兩個階段采用兩層嵌套結(jié)構(gòu)，外層算法產(chǎn)生分批方案，針對每個分批結(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 兩階段變異操作過程Fig.4 Two stage variant process

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

3 實例驗證

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

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

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

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

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

計劃期內(nèi)，自制任務(wù)產(chǎn)品P1、P2、P3的生產(chǎn)任務(wù)分別為100、200、100。將其分解為部件級和零件級，則部件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為算法平臺進(jì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}。對應(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，最小完成時間為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

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

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

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

4 結(jié)語

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

[1] 李伯虎，張霖，王時龍，等.云制造——面向服務(wù)的網(wǎng)絡(luò)化制造新模式[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ì).智能制造——“中國制造2025”的主攻方向[J].中國機(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ù)平臺[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ū)動的云制造服務(wù)平臺[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ī)集成制造系統(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ū)動的云制造車間調(diào)度研究[D].廣州：華南理工大學(xué)，2014. YANG Yi. Study on Event Driven Cloud Manufacturing Shop Scheduling[D]. Guangzhou：South China University of Technology，2014.

[10] 李修琳，魯建廈，柴國鐘，等. 基于混合遺傳算法的混流混合車間協(xié)同調(diào)度問題[J]. 中國機(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é)報，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é)報，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] 張國輝，聶黎，毛學(xué)港.生物地理學(xué)算法求解柔性作業(yè)車間調(diào)度問題[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] 葉開文，劉三陽，高衛(wèi)峰.基于差分進(jìn)化的生物地理學(xué)優(yōu)化算法[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é)基金資助項目(LY15G010009，LQ14E050004)

TB491

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

魯建廈，男，1963年生。浙江工業(yè)大學(xué)機(jī)械工程學(xué)院教授、博士研究生導(dǎo)師。主要研究方向為精益生產(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é)院副教授。