考慮批量裝配的柔性作業(yè)車間調(diào)度問題研究

巴　黎　李　言　曹　源　楊明順　劉　永

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

?

考慮批量裝配的柔性作業(yè)車間調(diào)度問題研究

巴黎李言曹源楊明順劉永

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

摘要：柔性作業(yè)車間調(diào)度是生產(chǎn)調(diào)度領(lǐng)域中的一個(gè)重要組合優(yōu)化問題，由于取消了工序與加工設(shè)備的唯一性對(duì)應(yīng)關(guān)系，因而相較于作業(yè)車間調(diào)度問題，具有更高的復(fù)雜度。針對(duì)該問題在批量裝配方面的不足，考慮將批量因素與裝配環(huán)節(jié)同時(shí)集成到柔性作業(yè)車間調(diào)度問題當(dāng)中。以成品件的完工時(shí)間為優(yōu)化目標(biāo)，對(duì)該批量裝配柔性作業(yè)車間調(diào)度問題進(jìn)行了數(shù)學(xué)建模。針對(duì)該模型，提出一種多層編碼結(jié)構(gòu)的粒子群算法，并對(duì)該算法的各個(gè)模塊進(jìn)行了設(shè)計(jì)。最后，以實(shí)例驗(yàn)證了該數(shù)學(xué)模型的正確性及算法的有效性。

關(guān)鍵詞：柔性作業(yè)車間調(diào)度問題；批量；裝配；6層編碼結(jié)構(gòu)

0引言

作業(yè)車間調(diào)度問題(job-shop scheduling problem，JSP)作為生產(chǎn)調(diào)度領(lǐng)域的研究熱點(diǎn)，是最具普遍性的問題之一，屬于典型的NP-Hard問題[1]。柔性作業(yè)車間調(diào)度問題(flexible job-shop scheduling problem，F(xiàn)JSP)由Brucker和Schlie于1990年提出[2]，是JSP的擴(kuò)展，與JSP不同的是，F(xiàn)JSP取消了工序與加工設(shè)備的唯一性對(duì)應(yīng)關(guān)系，因而相較于JSP，具有更高的復(fù)雜度，已被證明為NP-Hard問題[3]。由于FJSP更加符合實(shí)際生產(chǎn)環(huán)境，因此研究FJSP具有重要的理論意義和實(shí)際價(jià)值[4]。

近年來(lái)，學(xué)者們對(duì)多目標(biāo)FJSP進(jìn)行了大量的研究。文獻(xiàn)[4]以makespan、加工成本和提前/拖期懲罰值為優(yōu)化目標(biāo)，建立了相應(yīng)的優(yōu)化模型，針對(duì)該問題，提出了一種多目標(biāo)粒子群算法，最后以實(shí)例對(duì)所建模型及算法進(jìn)行了驗(yàn)證；文獻(xiàn)[5]以makespan、機(jī)器總負(fù)載及機(jī)器最大負(fù)載為目標(biāo)，提出了一種基于Pareto優(yōu)化的離散自由搜索算法，并通過兩個(gè)實(shí)例驗(yàn)證了算法的有效性；文獻(xiàn)[6]以makespan及設(shè)備最大負(fù)載為目標(biāo)，將生產(chǎn)能力約束考慮到約束條件，對(duì)問題進(jìn)行建模，提出了一種改進(jìn)的遺傳算法，最后以標(biāo)準(zhǔn)算例對(duì)模型及算法進(jìn)行了驗(yàn)證；文獻(xiàn)[7]以makespan、設(shè)備總負(fù)載和設(shè)備最大負(fù)載為目標(biāo)，提出了一種基于粒子群算法和局部搜索算法的混合智能算法，并以實(shí)例對(duì)該算法進(jìn)行了驗(yàn)證；文獻(xiàn)[8]以makespan、設(shè)備總負(fù)載和設(shè)備最大負(fù)載為目標(biāo)，通過對(duì)各優(yōu)化目標(biāo)賦予相應(yīng)的權(quán)重，將多個(gè)優(yōu)化目標(biāo)合并成單一優(yōu)化目標(biāo)，提出了一種混合遺傳退火算法。

在FJSP的算法改進(jìn)方面，文獻(xiàn)[9]提出了一種基于遺傳算法及啟發(fā)式規(guī)則的混合遺傳算法，通過啟發(fā)式規(guī)則，對(duì)不符合約束的解進(jìn)行修正，最后，以實(shí)例對(duì)該算法進(jìn)行了驗(yàn)證；文獻(xiàn)[10]提出了一種基于知識(shí)的可變鄰域搜索算法，最后以實(shí)例對(duì)該算法進(jìn)行了驗(yàn)證；為提高種群質(zhì)量，文獻(xiàn)[11]提出了一種基于Bayesian統(tǒng)計(jì)推理的分布估計(jì)算法，最后，采用標(biāo)準(zhǔn)算例對(duì)該算法進(jìn)行了驗(yàn)證。

目前，F(xiàn)JSP的相關(guān)研究主要集中在多目標(biāo)FJSP以及FJSP的算法改進(jìn)方面。實(shí)際生產(chǎn)中，由于訂單的多樣性以及各工件加工數(shù)量上的不同，為提高生產(chǎn)效率，往往對(duì)工件進(jìn)行分批加工。顯然，若對(duì)所有工件都默認(rèn)整批加工，并不符合實(shí)際生產(chǎn)要求。

文獻(xiàn)[12]針對(duì)多目標(biāo)柔性作業(yè)車間批量調(diào)度問題，以完工時(shí)間、機(jī)器總負(fù)載、機(jī)器最大負(fù)載、總加工成本及工件拖期懲罰為優(yōu)化目標(biāo)，建立了該問題的數(shù)學(xué)模型，并提出了一種基于差分進(jìn)化算法的多目標(biāo)柔性批量調(diào)度算法對(duì)該問題進(jìn)行求解；文獻(xiàn)[13]針對(duì)考慮模糊交貨期的多目標(biāo)批量生產(chǎn)柔性作業(yè)車間調(diào)度問題，以加工批次完工時(shí)刻的加權(quán)平均隸屬度及加工批次流程時(shí)間價(jià)值總量為優(yōu)化目標(biāo)，對(duì)該問題進(jìn)行建模，并提出了一種改進(jìn)的非支配排序遺傳算法對(duì)該問題進(jìn)行求解；文獻(xiàn)[14]同時(shí)將機(jī)器、模具及操作人員作為調(diào)度資源，針對(duì)多資源作業(yè)車間批量調(diào)度問題，以生產(chǎn)周期為優(yōu)化目標(biāo)，建立了該問題的數(shù)學(xué)模型，提出了一種由多目標(biāo)混合差分進(jìn)化算法與多目標(biāo)局部搜索策略相結(jié)合的混合算法；文獻(xiàn)[15]針對(duì)以makespan為優(yōu)化目標(biāo)的柔性作業(yè)車間批量調(diào)度問題，將粒子群算法與模擬退火算法相結(jié)合，提出了一種改進(jìn)的粒子群算法。

近年來(lái)，已有一些文獻(xiàn)將批量因素考慮到柔性作業(yè)車間調(diào)度問題當(dāng)中。但是，相關(guān)文獻(xiàn)大都以工件的加工過程作為問題的主要考慮環(huán)節(jié)，并未考慮到其他可能影響到生產(chǎn)過程的環(huán)節(jié)。實(shí)際生產(chǎn)中，工件制造僅為制造過程的最底層，完工的各類工件將會(huì)通過設(shè)備或人工的方式組裝成組件，最后總裝成成品。無(wú)論是組件，還是成品件的組裝，都有其BOM(bill of material)需求及相關(guān)的裝配設(shè)備，而各組件及成品的BOM需求，以及裝配環(huán)節(jié)的相關(guān)設(shè)備必然會(huì)對(duì)生產(chǎn)流程產(chǎn)生影響，顯然，若僅考慮工件制造環(huán)節(jié)，難以符合實(shí)際的生產(chǎn)情況。

綜上所述，為使FJSP更加貼合實(shí)際，本文將批量因素及裝配環(huán)節(jié)同時(shí)考慮到FJSP當(dāng)中，將制造環(huán)節(jié)從僅考慮工件制造擴(kuò)展到由工件制造、組件裝配及完成件裝配組成的完整制造過程，提出一種批量裝配柔性作業(yè)車間調(diào)度方法。以成品件的完工時(shí)間為優(yōu)化目標(biāo)，對(duì)該批量裝配柔性作業(yè)車間調(diào)度問題進(jìn)行數(shù)學(xué)建模，提出一種多層編碼粒子群算法，對(duì)該算法的各個(gè)模塊進(jìn)行設(shè)計(jì)，最后，以一個(gè)實(shí)例對(duì)模型及算法進(jìn)行了驗(yàn)證。

1問題描述

某制造企業(yè)有一筆訂單，需要加工多種工件，并將其中的一些工件組裝成不同的組件，最終將各組件及工件組裝成成品。各工件的批量不盡相同，每道工序?qū)?yīng)多臺(tái)可用的加工設(shè)備，組件及成品的裝配由若干臺(tái)裝配設(shè)備完成。在此情況下，以成品的完工時(shí)間為優(yōu)化目標(biāo)，通過確定批次數(shù)、各道工序在加工序列中的位置以及各工序?qū)?yīng)的加工設(shè)備，以獲得完工時(shí)間最小的調(diào)度方案。該問題中各變量及其符號(hào)表示如下：n表示工件數(shù)；d表示組件數(shù)；f表示成品數(shù)，默認(rèn)所有工件/組件組裝成一種成品；nG表示訂單需求的成品數(shù)量；m表示加工設(shè)備數(shù)；s表示裝配設(shè)備數(shù)；pS表示工序數(shù)；bi表示工件i的總批量，i=1,2,…,n；bCi表示工件i的批次數(shù)；bSil表示工件i的第l批次工件對(duì)應(yīng)的批量，l=1,2,…,bCi；TMSj表示加工設(shè)備j的可開工時(shí)間，j=1,2,…,m；TSJilvj表示工件i的第l批次工件的第v道工序在加工設(shè)備j上的開工時(shí)間，v=1,2,…,pS；TMJilvj表示工件i的第l批次工件的第v道工序在加工設(shè)備j上的單件加工時(shí)間；TFJilvj表示工件i的第l批次工件，第v道工序在加工設(shè)備j上的完工時(shí)間；TFFJil表示工件i的第l批次工件的完工時(shí)間；TASu表示裝配設(shè)備u的可開工時(shí)間，u=1,2,…,s；TMAeu表示組件e在裝配設(shè)備u上的單件裝配時(shí)間，e=1,2,…,d；TSAeu表示組件e在裝配設(shè)備u上的開工時(shí)間；TFAeu表示組件e在裝配設(shè)備u上的完工時(shí)間；TMEu表示成品在裝配設(shè)備u上的單件裝配時(shí)間；TSEu表示成品在裝配設(shè)備u上的開工時(shí)間；TFEu表示成品在裝配設(shè)備u上的完工時(shí)間；BOMGJi表示單件成品與工件i的數(shù)量對(duì)應(yīng)關(guān)系；BOMGAe表示單件成品與組件e的數(shù)量對(duì)應(yīng)關(guān)系；BOMAJei表示單件組件e與工件i的數(shù)量對(duì)應(yīng)關(guān)系；NSAe表示當(dāng)前可進(jìn)行預(yù)裝的組件數(shù)，初始狀態(tài)下為0；NSG表示當(dāng)前可進(jìn)行預(yù)裝的成品數(shù)，初始狀態(tài)下為0；NFJi表示當(dāng)前已完工的工件i的數(shù)量，初始狀態(tài)下為0；NFAe表示當(dāng)前已完工的組件e的數(shù)量，初始狀態(tài)下為0；NFG表示當(dāng)前已完工的成品的數(shù)量，初始狀態(tài)下為0；RJPilvj為布爾變量，表示工件工序與加工設(shè)備的對(duì)應(yīng)關(guān)系，若工件i的第l批次工件的第v道工序選擇加工設(shè)備j進(jìn)行加工，其值為1，否則為0；RAAeu為布爾變量，表示組件與裝配設(shè)備的關(guān)系，若組件e由裝配設(shè)備u裝配，其值為1，否則為0；REAu為布爾變量，表示成品與裝配設(shè)備的關(guān)系，若成品由裝配設(shè)備u裝配，其值為1，否則為0。

2問題建模

以成品完工時(shí)間最小為目標(biāo)，可得目標(biāo)函數(shù)：

minTFEuu=1,2,…,s

(1)

對(duì)上述模型，考慮以下約束。

(1)各工件分批后工件對(duì)應(yīng)的批量總和等于相應(yīng)分批前工件的總批量，即

(2)

(2)假設(shè)工件i′的第l批次工件的第v′道工序在加工設(shè)備j上加工，若本道工序?qū)?yīng)加工設(shè)備的可開工時(shí)間大于該批次工件上道工序的完工時(shí)間，則該批次工件第v′道工序的開工時(shí)間等于設(shè)備j的可開工時(shí)間；否則，該批次工件第v′道工序的開工時(shí)間等于該批次工件上道工序的完工時(shí)間。表達(dá)式如下：

若RJPi′lv′j=1，則有

(3)

針對(duì)約束(2)，需計(jì)算以下參數(shù)的數(shù)據(jù)。

計(jì)算TFJi′lv′j及更新TMSj：

TFJi′lv′j=TMSj=TSJi′lv′j+TMJi′lv′jbSi′l

(4)

若v′=pS，則記錄TFFJi′l：

TFFJi′l=TFJi′lv′j

(5)

更新當(dāng)前已完工的工件i′的數(shù)量：

NFJi′←NFJi′+bSi′l

(6)

若BOMAJe′i′>0，計(jì)算當(dāng)前可預(yù)裝的組件e′的數(shù)量。約定符號(hào)“//”，對(duì)于兩個(gè)非負(fù)整數(shù)a、b，若a>b且b>0，則a//b表示a除以b，其得數(shù)只取整數(shù)部分；若a0，則a//b=0；若b=0，則a//b=+∞。得到當(dāng)前可預(yù)裝的組件e′的數(shù)量：

NSAe′=min(NFJi//BOMAJe′i)

(7)

對(duì)于任意裝配設(shè)備u，若RAAe′u=1，則更新組件e′在裝配設(shè)備u上的開工及完工時(shí)間：

TSAe′u=max(TASu，TFFJi′l)

(8)

TFAe′u=TSAe′u+TMAe′uNSAe′

(9)

更新裝配設(shè)備u的可開工時(shí)間TASu：

TASu=TFAe′u

(10)

對(duì)于任意工件i，若BOMAJe′i>0，更新已完工的工件的數(shù)量NFJi：

NFJi←NFJi-NSAe′BOMAJe′i

(11)

更新當(dāng)前已完工的組件e′的數(shù)量NFAe′：

NFAe′←NFAe′+NSAe′

(12)

若BOMGAe′>0，計(jì)算當(dāng)前可預(yù)裝的成品的數(shù)量：

NSG=min(min(NFJi//BOMGJi)，min(NFAe//BOMGAe))

(13)

對(duì)于任意裝配設(shè)備u，若REAu=1，則更新成品在裝配設(shè)備u上的開工及完工時(shí)間：

TSEu=max(TASu，TFAe′u)

(14)

TFEu=TSEu+TMEuNSG

(15)

更新裝配設(shè)備u的可開工時(shí)間TASu：

相比日本和韓國(guó)，同樣作為中國(guó)的鄰居，國(guó)人對(duì)印度這個(gè)國(guó)家卻始終顯得有些陌生，神秘，宗教是對(duì)它的印象，說(shuō)到美食，遠(yuǎn)不如對(duì)日韓美食那樣如數(shù)家珍。頓頓吃咖喱？吃飯直接用手？印度愛吃米飯還是面食？素食國(guó)度，不能吃肉？各種各樣的局限印象和疑問，使得游客無(wú)法好好審視一下印度的食物。

TASu=TFEu

(16)

對(duì)于任意工件i，若BOMGJi>0，更新已完工的工件的數(shù)量NFJi：

NFJi←NFJi-NSGBOMGJi

(17)

對(duì)于任意組件e，若BOMGAe>0，更新已完工的組件的數(shù)量NFAe：

NFAe←NFAe-NSGBOMGAe

(18)

更新當(dāng)前已完工的成品的數(shù)量NFG：

NFG←NFG+NSG

(19)

若NFG=nG，則獲得到最終完工時(shí)間，即TFEu。

由于考慮了批量因素，因而，提出約束(1)對(duì)各工件的批量進(jìn)行約束；對(duì)于各批次工件各道工序的開工時(shí)間，則通過約束(2)進(jìn)行確定；對(duì)于分批后工件的加工環(huán)節(jié)，通過式(4)~式(6)分別確定分批后工件各道工序的完工時(shí)間及加工設(shè)備的可開工時(shí)間、分批后工件的最終完工時(shí)間、已完工工件的數(shù)量；對(duì)于組件裝配環(huán)節(jié)，通過式(7)~式(12)分別確定可進(jìn)行組裝的組件的數(shù)量、各組件的開工時(shí)間、各組件的完工時(shí)間、裝配設(shè)備的可開工時(shí)間、剩余工件的數(shù)量、已完工組件的數(shù)量；對(duì)于成品組裝環(huán)節(jié)，通過式(13)~式(19)分別確定可進(jìn)行組裝的成品的數(shù)量、成品的開工時(shí)間、成品的完工時(shí)間、裝配設(shè)備的可開工時(shí)間、剩余工件的數(shù)量、剩余組件的數(shù)量、已完工成品的數(shù)量。

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

由上述問題描述及建?？芍紤]批量裝配的FJSP屬NP-Hard問題，通常的整數(shù)線性規(guī)劃難以對(duì)其進(jìn)行求解。本文針對(duì)考慮批量裝配的FJSP，提出一種新的粒子群優(yōu)化算法，以下針對(duì)該算法的編碼、位置更新操作、位置變換操作及相關(guān)參數(shù)依次進(jìn)行說(shuō)明，并給出算法的流程圖。

(1) 編碼。本文提出一種6層編碼結(jié)構(gòu)，對(duì)可行方案進(jìn)行編碼。該結(jié)構(gòu)由原工件層、分批后工件層、批量層、加工設(shè)備層、加工方法層及加工時(shí)間層組成。①原工件層為工件的原始編碼；②分批后工件層為分批后不同批次工件的編碼，由工件原始編碼和分批批次組成。例如，對(duì)于工件2，其被分為了兩批，則一批的編碼將命名為21，另一批則命名為22，其他工件依此類推；③批量層為工件不同批次的批量，其總和應(yīng)等于該工件的總批量，即對(duì)應(yīng)第2節(jié)中的約束(1)，本文將對(duì)各工件進(jìn)行等批劃分，即不同工件對(duì)應(yīng)的批次數(shù)相同，同一工件對(duì)應(yīng)的各子批工件的批量相同；④加工方法層為分批后工件各道工序選擇的加工方法，如車、銑、刨、磨、鉆等；⑤加工設(shè)備層為不同批次工件對(duì)應(yīng)的加工設(shè)備編碼；⑥加工時(shí)間層為各設(shè)備對(duì)應(yīng)不同工件各道工序的單件加工時(shí)間，將單件加工時(shí)間乘以對(duì)應(yīng)的批量，即可獲得分批后工件在相應(yīng)工序上的整批加工時(shí)間。基于上述定義，以2種工件、3道工序、3種加工方法、6臺(tái)加工設(shè)備的批量裝配FJSP為例，其編碼示例如表1所示。表1中，各層第1個(gè)位置上的碼值解釋為：分批后工件21所屬原工件為2，批量為10件，由于分批后工件編碼21第1次出現(xiàn)在分批后工件層，即代表該工件的第1道工序，對(duì)于分批后工件21的第1道工序，選擇加工設(shè)備5進(jìn)行加工，加工方法為3，對(duì)應(yīng)的單件加工時(shí)間為0.8分鐘/件。其他依此類推。裝配工序不體現(xiàn)在編碼部分，隨著各分批工件被加工完畢，將按照BOM需求實(shí)時(shí)對(duì)已完工的工件進(jìn)行裝配操作。

表1　批量裝配FJSP完整編碼示例

圖1　位置更新操作

圖2　加工順序的位置變換及修正操作

假設(shè)隨機(jī)產(chǎn)生一個(gè)位置為3，該位置對(duì)應(yīng)工序的可選設(shè)備為1、2，則加工設(shè)備的位置變換操作實(shí)例如圖3所示。

圖3　加工設(shè)備的位置變換操作

圖4　粒子群算法流程

基于上述對(duì)算法相關(guān)模塊的描述，繪制算法流程圖，如圖4所示。其中，M表示種群規(guī)模，控制種群中個(gè)體的數(shù)量；D表示迭代次數(shù)，控制算法進(jìn)行迭代的次數(shù)，若迭代達(dá)到該次數(shù)，則算法停止；PAlpha表示當(dāng)前個(gè)體與全局最優(yōu)解進(jìn)行位置更新操作的概率，為(0，1)區(qū)間的小數(shù)；Pbeta表示當(dāng)前個(gè)體與個(gè)體歷史最優(yōu)解進(jìn)行位置更新操作的概率，為(0，1)區(qū)間的小數(shù)，本文取Pbeta=1-PAlpha；Pm表示對(duì)種群中的個(gè)體進(jìn)行位置變換操作的概率，為(0，1)區(qū)間的小數(shù)；Ps表示對(duì)當(dāng)前個(gè)體所對(duì)應(yīng)的加工順序進(jìn)行位置變換的概率，為(0，1)區(qū)間的小數(shù)；Pa表示對(duì)當(dāng)前個(gè)體所對(duì)應(yīng)的設(shè)備進(jìn)行位置變換概率，為(0，1)區(qū)間的小數(shù)。

4實(shí)例分析

(1) 實(shí)例說(shuō)明。某企業(yè)有一筆訂單，共需要加工5種工件，表示為J1~J5，各工件對(duì)應(yīng)批量依次為20、10、10、30、20。共有10臺(tái)加工設(shè)備，表示為M1~M10，3臺(tái)裝配設(shè)備MA1~MA3，6種加工方法P1~P6。以成品的完工時(shí)間最小為目標(biāo)，使用上述算法對(duì)該問題進(jìn)行求解。成品G的BOM如圖5所示，括號(hào)中所示數(shù)字即為單件成品或組件需求的組件或工件的數(shù)量。加工方法與加工設(shè)備對(duì)應(yīng)關(guān)系、各工件對(duì)應(yīng)的加工路線、各加工方法對(duì)應(yīng)的單件加工時(shí)間及各組件及成品對(duì)應(yīng)各裝配設(shè)備的單件組裝時(shí)間分別如表2~表5所示。

圖5　成品G的BOM

加工方法加工設(shè)備M1M2M3M4M5M6M7M8M9M10P11111P2111P311P41P511P611

表3　各工件對(duì)應(yīng)的加工路線

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

(3) 求解結(jié)果與分析。取種群規(guī)模為500、迭代次數(shù)為300、批次數(shù)為4、PAlpha為0.5、Pbeta為0.5、Pm為0.1。使用C#語(yǔ)言實(shí)現(xiàn)算法編寫，在以上參數(shù)不變，取等批分批的批次數(shù)分別為4、3、2，以及不分批的情況，各分批情況分別計(jì)算50次，匯總結(jié)果如表6所示。

表4　各加工方法對(duì)應(yīng)的單件加工時(shí)間　min

表5　各組件及成品對(duì)應(yīng)各裝配設(shè)備的

CPU 1.81 GHz、RAM 2 GB的PC主機(jī)上運(yùn)行，所得最優(yōu)完工時(shí)間為162.6 min，迭代圖見圖6，最優(yōu)解對(duì)應(yīng)甘特圖見圖7。

圖6　迭代圖

以下根據(jù)圖7及表6所示的求解結(jié)果，從考慮裝配環(huán)節(jié)及考慮分批加工兩個(gè)角度，對(duì)求解結(jié)果進(jìn)行分析。

(1) 考慮裝配環(huán)節(jié)。由圖7可知，將裝配環(huán)節(jié)考慮到FJSP中，各裝配設(shè)備及加工設(shè)備均被智能調(diào)度。若不考慮裝配環(huán)節(jié)，僅會(huì)得到工件的最終完工時(shí)間，而實(shí)際的完工時(shí)間卻是成品的完工時(shí)間，由于缺少了對(duì)裝配環(huán)節(jié)的調(diào)度，使調(diào)度方案無(wú)法充分契合實(shí)際的生產(chǎn)情況，因而，對(duì)完整的制造過程進(jìn)行調(diào)度更為合適。

圖7　最優(yōu)解對(duì)應(yīng)的甘特圖

(2) 考慮分批加工。①分批與不分批情況。由圖7可知，當(dāng)已完工的工件或組件的數(shù)量滿足BOM時(shí)，即可安排進(jìn)行組件或成品的裝配，而并非是在加工環(huán)節(jié)全部完工后，再進(jìn)行裝配環(huán)節(jié)。

表6　求解結(jié)果匯總　min

若不對(duì)工件進(jìn)行分批加工，一方面，將導(dǎo)致一些設(shè)備的持續(xù)使用時(shí)間過長(zhǎng)，被加工的工件須等到整批被加工完畢，才可進(jìn)入下一道工序，因而延后了工件的完工時(shí)間；另一方面，須等到所需工件及組件整批加工完畢，才可進(jìn)行對(duì)應(yīng)的組件或成品的裝配，從而導(dǎo)致了裝配工序的延后，延長(zhǎng)了最終的完工時(shí)間。由表6可知，不分批情況下所獲得的最優(yōu)完工時(shí)間為303 min，劣于表6中考慮分批情況所獲得的最優(yōu)完工時(shí)間。對(duì)工件進(jìn)行分批加工，一方面，實(shí)現(xiàn)了所屬原工件相同的各分批后工件的并行加工，從而有效縮短了工件的完工時(shí)間；另一方面，只要當(dāng)前完成的工件滿足對(duì)應(yīng)組件的BOM需求、或當(dāng)前完成的工件及組件滿足對(duì)應(yīng)成品的BOM需求，即進(jìn)行裝配，使裝配操作不必等到整批工件完工后進(jìn)行，從而縮短了最終的完工時(shí)間。

②等批分批情況。由表6可知，對(duì)工件進(jìn)行等批4批加工，所獲得的最優(yōu)完工時(shí)間為162.6 min，優(yōu)于表中其他分批情況。若工件的批次數(shù)過小，無(wú)法充分對(duì)各分批工件進(jìn)行并行加工，因而無(wú)法充分縮短工件的完工時(shí)間，從而延后了組件及成品的裝配。但是，若批次數(shù)過大，則可能不符合實(shí)際的分批要求，因而，實(shí)際生產(chǎn)中，可根據(jù)實(shí)際的分批要求進(jìn)行模擬調(diào)度，以獲得合適的分批調(diào)度方案。

此外，對(duì)工件進(jìn)行等批4批加工，算法平均耗時(shí)為3.7 min，劣于表6中其他分批情況。若增加工件的批次數(shù)，則會(huì)同時(shí)增加搜索域的范圍，提高了問題的復(fù)雜度，從而增加了算法的計(jì)算時(shí)間。

5結(jié)論

(1) 針對(duì)批量裝配FJSP，以成品件的完工時(shí)間最小為目標(biāo)，建立了該問題的數(shù)學(xué)模型。

(2) 鑒于該問題的復(fù)雜性及離散性，提出了一種6層編碼結(jié)構(gòu)的粒子群算法，對(duì)算法的各個(gè)模塊進(jìn)行設(shè)計(jì)，給出了該算法的流程圖。

(3) 以實(shí)例驗(yàn)證了所建模型的正確性及算法的有效性。求解結(jié)果表明，一方面，對(duì)工件進(jìn)行分批加工，實(shí)現(xiàn)了所屬原工件相同的各分批后工件的并行加工，提前了組件及成品的裝配時(shí)間，因而縮短了最終的完工時(shí)間；另一方面，將裝配環(huán)節(jié)考慮到FJSP中，使制造環(huán)節(jié)從僅工件制造擴(kuò)展到從工件、至組件、乃至最終成品的完整制造過程。若不考慮裝配環(huán)節(jié)，僅會(huì)得到工件的最終完工時(shí)間，而實(shí)際的完工時(shí)間卻是成品的完成時(shí)間，因而，對(duì)完整的制造過程進(jìn)行調(diào)度更為合適。綜上所述，將批量因素及裝配環(huán)節(jié)考慮到FJSP中是必要的，對(duì)于實(shí)際調(diào)度方案的制定，其優(yōu)化結(jié)果具有更好的參考及指導(dǎo)作用。

參考文獻(xiàn)：

[1]Garey M R, Johnson D S, Sethi R. The Complexity of Flow Shop and Job Shop Scheduling[J]. Mathematics of Operations Research, 1976, 1(2): 117-129.

[2]Bruker P, Schlie R. Job-shop Scheduling with Multi-purpose Machines[J]. Computing, 1990, 45(4): 369-375.

[3]Binh Ho N, Cing Tay J, MKLai E. An Effective Architecture for Learning and Evolving Flexible Job-shop Schedules[J]. European Journal of Operational Research, 2007, 179(2): 316-333.

[4]王云, 馮毅雄, 譚建榮, 等. 基于多目標(biāo)粒子群算法的柔性作業(yè)車間調(diào)度優(yōu)化方法[J]. 農(nóng)業(yè)機(jī)械學(xué)報(bào), 2011, 42(2): 190-195.

Wang Yun, Feng 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.

[5]彭建剛, 劉明周, 張璽, 等. 基于Pareto優(yōu)化的離散自由搜索算法求解多目標(biāo)柔性作業(yè)車間調(diào)度問題[J]. 中國(guó)機(jī)械工程, 2015, 26(5): 620-626.

Peng Jiangang, Liu Mingzhou, Zhang Xi, et al.Discrete Free Search Based on Pareto-optimality for Multi-objective Flexible Job-shop Scheduling Problem[J]. China Mechanical Engineering, 2015, 26(5): 620-626.

[6]張鐵男, 韓兵, 于渤. 生產(chǎn)能力約束條件下的柔性作業(yè)車間調(diào)度優(yōu)化[J]. 系統(tǒng)工程理論與實(shí)踐, 2011, 31(2): 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(2): 505-510.

[7]Moslehi G, Mahnam 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.

[8]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.

[9]Gutierrez C, Garcia-Magarino I. Modular Design of a Hybrid Genetic Algorithm for a Flexible Job-shop Scheduling Problem[J]. Knowledge-based Systems, 2011, 24: 102-112.

[10]Karimi H, Rahmati S H A, Zandieh M. An Efficient Knowledge-based Algorithm for the Flexible Job Shop Scheduling Problem[J]. Knowledge-based Systems, 2012, 36: 236-244.

[11]何小娟, 曾建潮. 基于Bayesian統(tǒng)計(jì)推理的分布估計(jì)算法求解柔性作業(yè)車間調(diào)度問題[J]. 系統(tǒng)工程理論與實(shí)踐, 2012, 32(2): 380-387.

He Xiaojuan, Zeng Jianchao.Solving Flexible Job-shop Scheduling Problems with Bayesian Statistical Inference-based Estimation of Distribution Algorithm[J]. Systems Engineering-Theory & Practice, 2012, 32(2): 380-387.

[12]王萬(wàn)良, 范麗霞, 徐新黎, 等. 多目標(biāo)差分進(jìn)化算法求解柔性作業(yè)車間批量調(diào)度問題[J]. 計(jì)算機(jī)集成制造系統(tǒng), 2013, 19(10): 2481-2492.

Wang Wanliang, Fan Lixia, Xu Xinli, et al. Multi-objective Differential Evolution Algorithm for Flexible Job-shop Batch Scheduling Problem[J]. Computer Integrated Manufacturing Systems, 2013, 19(10): 2481-2492.

[13]曾強(qiáng), 楊育, 沈玲, 等. 基于準(zhǔn)時(shí)交貨的批量生產(chǎn)FJSP多目標(biāo)優(yōu)化[J]. 計(jì)算機(jī)集成制造系統(tǒng), 2011, 17(8): 1780-1789.

Zeng Qiang, Yang Yu, Shen Ling, et al. Mutiobjective Optimization for Batch Production FJSP Based on Just in Time Delivery[J]. Computer Integrated Manufacturing Systems, 2011, 17(8): 1780-1789.

[14]王海燕, 趙燕偉, 王萬(wàn)良, 等. 兩級(jí)差分進(jìn)化算法求解多資源作業(yè)車間批量調(diào)度問題[J]. 控制與決策, 2010, 25(11): 1635-1644.

Wang Haiyan, Zhao Yanwei, Wang Wanliang, et al. New Parallel Algorithm Based on DE for Batch Splitting Job Shop Scheduling under Multiple-resource Constraints[J]. Control and Decision, 2010, 25(11): 1635-1644.

[15]張靜, 王萬(wàn)良, 徐新黎, 等. 基于改進(jìn)粒子群算法求解柔性作業(yè)車間批量調(diào)度問題[J]. 控制與決策, 2012, 27(4): 513-518.

Zhang Jing, Wang Wanliang, Xu Xinli, et al.Improved Particle Swarm Algorithm for Batch Splitting Flexible Job Shop Scheduling[J]. Control and Decision, 2012, 27(4): 513-518.

(編輯袁興玲)

Research on Flexible Job-shop Scheduling Problem with Consideration of Batch Splitting and Assembly

Ba LiLi YanCao YuanYang MingshunLiu Yong

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

Abstract：FJSP was a quite important combinatorial optimization problem in the field of production scheduling. Because of the one-to-one relationship among processes and machines was canceled in FJSP, FJSP was more complex than job-shop scheduling problem (JSP). Aiming at the shortages of FJSP in batch and assembly, batch factor and assembling processes were integrated in FJSP simultaneously. Makespan of finished product was the main target which will be optimized. A particle swarm optimization (PSO) with a multi-layer encoding structure was proposed. Each module of the PSO was designed. Finally, the model and algorithm were proved through an application case.

Key words：flexible job-shop scheduling problem(FJSP); batch; assembly; 6-layer encoding structure

基金項(xiàng)目：國(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)

收稿日期：2015-06-12

中圖分類號(hào)：TH166；TH186DOI：10.3969/j.issn.1004-132X.2015.23.014

作者簡(jiǎn)介：巴黎，男，1986年生。西安理工大學(xué)機(jī)械與精密儀器工程學(xué)院博士研究生。主要研究方向?yàn)樯a(chǎn)計(jì)劃與調(diào)度。發(fā)表論文8篇。李言，男，1960年生。西安理工大學(xué)機(jī)械與精密儀器工程學(xué)院教授、博士研究生導(dǎo)師。曹源，男，1991年生。西安理工大學(xué)機(jī)械與精密儀器工程學(xué)院碩士研究生。楊明順，男，1974年生。西安理工大學(xué)機(jī)械與精密儀器工程學(xué)院副教授。劉永，男，1981年生。西安理工大學(xué)機(jī)械與精密儀器工程學(xué)院副教授。