巴　黎　李　言　曹　源　楊明順　劉　永

西安理工大學，西安，710048

?

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

巴黎李言曹源楊明順劉永

西安理工大學，西安，710048

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

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

0引言

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

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

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

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

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

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

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

1問題描述

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

2問題建模

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

minTFEuu=1,2,…,s

(1)

對上述模型，考慮以下約束。

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

(2)

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

若RJPi′lv′j=1，則有

(3)

針對約束(2)，需計算以下參數(shù)的數(shù)據(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)

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

NFJi′←NFJi′+bSi′l

(6)

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

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

(7)

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

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

(8)

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

(9)

更新裝配設備u的可開工時間TASu：

TASu=TFAe′u

(10)

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

NFJi←NFJi-NSAe′BOMAJe′i

(11)

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

NFAe′←NFAe′+NSAe′

(12)

若BOMGAe′>0，計算當前可預裝的成品的數(shù)量：

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

(13)

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

TSEu=max(TASu，TFAe′u)

(14)

TFEu=TSEu+TMEuNSG

(15)

更新裝配設備u的可開工時間TASu：

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

TASu=TFEu

(16)

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

NFJi←NFJi-NSGBOMGJi

(17)

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

NFAe←NFAe-NSGBOMGAe

(18)

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

NFG←NFG+NSG

(19)

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

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

3算法設計

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

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

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

圖1　位置更新操作

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

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

圖3　加工設備的位置變換操作

圖4　粒子群算法流程

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

4實例分析

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

圖5　成品G的BOM

加工方法加工設備M1M2M3M4M5M6M7M8M9M10P11111P2111P311P41P511P611

表3　各工件對應的加工路線

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

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

表4　各加工方法對應的單件加工時間　min

表5　各組件及成品對應各裝配設備的

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

圖6　迭代圖

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

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

圖7　最優(yōu)解對應的甘特圖

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

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

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

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

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

5結(jié)論

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

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

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

參考文獻：

[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]王云, 馮毅雄, 譚建榮, 等. 基于多目標粒子群算法的柔性作業(yè)車間調(diào)度優(yōu)化方法[J]. 農(nóng)業(yè)機械學報, 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)化的離散自由搜索算法求解多目標柔性作業(yè)車間調(diào)度問題[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)工程理論與實踐, 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)計推理的分布估計算法求解柔性作業(yè)車間調(diào)度問題[J]. 系統(tǒng)工程理論與實踐, 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]王萬良, 范麗霞, 徐新黎, 等. 多目標差分進化算法求解柔性作業(yè)車間批量調(diào)度問題[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]曾強, 楊育, 沈玲, 等. 基于準時交貨的批量生產(chǎn)FJSP多目標優(yōu)化[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]王海燕, 趙燕偉, 王萬良, 等. 兩級差分進化算法求解多資源作業(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]張靜, 王萬良, 徐新黎, 等. 基于改進粒子群算法求解柔性作業(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

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

收稿日期：2015-06-12

中圖分類號：TH166；TH186DOI：10.3969/j.issn.1004-132X.2015.23.014

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