基于改進BBO算法的多目標柔性作業(yè)車間調(diào)度研究

裴小兵++何倩男

摘要： 為了滿足市場的快速變化、降低生產(chǎn)成本，車間調(diào)度成為生產(chǎn)的關(guān)鍵環(huán)節(jié)。為解決作業(yè)車間分批調(diào)度問題，本文在企業(yè)資金收益率最大化、物料周轉(zhuǎn)速度最快的情況下，建立以生產(chǎn)周期、交貨期滿意度為指標的數(shù)學模型，并提出一種將DE算法與BBO算法相結(jié)合的多目標優(yōu)化算法模型。最后經(jīng)過實例仿真，求得的結(jié)果證明了算法的有效性。

Abstract： In order to meet the rapid change of the market， reduce production cost， the workshop scheduling becomes the key link in the process of production. In order to solve the job shop scheduling， this paper establishes a mathematical model based on the production cycle and the satisfaction of the delivery time in the case of the maximum rate of return on capital and the fastest rate of material turnover and proposes a multi-objective optimization model based on combining DE algorithm with BBO （Biogeography-Based optimization） algorithm. Finally， through the instance simulation， experimental results proves the effectiveness of this algorithm.

關(guān)鍵詞： BBO算法；子批量；作業(yè)車間；分批；調(diào)度

Key words： BBO algorithm；sub-batch；job-shop；lot-splitting；scheduling

中圖分類號：TH165 文獻標識碼：A 文章編號：1006-4311（2017）07-0065-03

0 引言

隨著激烈的市場競爭和客戶對產(chǎn)品多樣性的需求，以“小批量、多品種”為特征的均衡生產(chǎn)已然成為主流生產(chǎn)模式，即柔性生產(chǎn)模式。

以往文獻多集中于單目標批量生產(chǎn)的研究，常見以費用最小為優(yōu)化目標（Song，2005[1]），但費用相對于生產(chǎn)批量的變化是一個靜態(tài)指標，并不能作為衡量批量是否最優(yōu)的標準（裴小兵，2015[2]），且實際生產(chǎn)過程中的情況復(fù)雜多變。潘全科（2004）[3]等研究表明：在作業(yè)車間中，對工件進行分批加工，可有效減少后續(xù)設(shè)備空閑等待時間，縮短生產(chǎn)周期，提高整體效率，但并未提出分批的解決方案；而后等量分批方法（曾強，2012[4]）、柔性分批方法被相繼提出（Jia，2014[5]），但由于各子批批量等量分割，使得其無法根據(jù)設(shè)備的負載大小進行柔性調(diào)度，容易造成生產(chǎn)失衡。因而，使用柔性分批方法的學者較多，可使子批工藝路線選取及加工排序同時得到優(yōu)化。

文中結(jié)合批量變動法的思想，建立了以最早完工時間、交貨期滿意度等為指標的數(shù)學模型，采用批量編碼方法，解決工件劃分和子批量大小問題。最后，進行實例驗證。

1 多目標柔性作業(yè)車間調(diào)度問

1.1 問題描述

多目標柔性作業(yè)車間調(diào)度問題可以描述為：有N種工件在k臺機器上進行加工，每種工件有SPi個，并且包含道工序，能加工某一工序的機器至少有一臺，且同一工序的加工時間因機器的性能不同而發(fā)生變化。

1.2 數(shù)學模型

在分批調(diào)度問題中，過大或過小的批量都會導(dǎo)致較長的生產(chǎn)時間。當批量過大時，造成當前機床加工時間過長，后續(xù)機床處于空閑等待狀態(tài)，拉長整個生產(chǎn)周期；當批量過小時，批次增多，會導(dǎo)致設(shè)備換模頻繁，降低效率。因此，本文也考慮子批量這一因素對車間調(diào)度性能的影響。本文結(jié)合批量變動法的思想，從生產(chǎn)周期、交貨期滿意度、制造成本這三個方面來建立數(shù)學模型。其中，制造成本由加工成本、搬運成本、庫存成本、批量啟動成本來度量，這里假設(shè)設(shè)備按照加工工藝流程進行布局，減少搬運距離和搬運次數(shù)，所以不考慮搬運成本；庫存成本指工件子批加工之前的等待成本。生產(chǎn)周期用工件的最大完成時間f1度量；交貨期滿意度用拖期懲罰f2來衡量；制造成本用f3度量。假定設(shè)備利用率很高，且所有工件在零時刻均可以被加工且設(shè)備一旦啟動直到全部工序完成才能停下，則數(shù)學模型及其約束條件如下：

2 生物地理學優(yōu)化算法

2008年Dan Simon提出生物地理學優(yōu)化（Biogeography-Based optimization，BBO）算法，該算法雖然在迭代初期由于遷移操作的特殊性收斂快速，但在迭代后期由于各島嶼的信息趨于不變，變異操作效果不大使得算法的開采能力較差，極易陷入局部最優(yōu)，本文用DE算法的變異算子代替BBO算法的隨機變異，不僅改善了變異效果且能增加種群多樣性，避免早熟現(xiàn)象，從而保證整體算法的有效性。改進的BBO算法流程如圖1所示。

3 實例仿真

算法在Intel（R） Core（TM） i3-2310M CPU @ 2.10GHz、2.00G內(nèi)存，Windows 7環(huán)境下運行，并采用C++ 語言編程。其中，主要的運行參數(shù)為：島嶼數(shù)量100，迭代次數(shù)為200，移入率和移出率的函數(shù)最大值I=E=1，變異概率0.01，試驗運行5次。為驗證該算法的性能，本文以一個 8×6規(guī)模作業(yè)車間分批調(diào)度實例來進行仿真實驗。

某汽車公司一條生產(chǎn)線有8臺機床，要生產(chǎn)6種零件，每種零件批量為10，每種零件包含三道工序，每道工序都有三臺不同的可選機床進行加工，如表1所示。

為了驗證算法的性能，本文將此調(diào)度問題分為非等量分批、等量分批及不分批三種情況，解決同一個調(diào)度問題，非等量分批方案比等量分批和不分批方案更能有效地平衡機床負荷、縮短生產(chǎn)周期，提高生產(chǎn)效率，減少加工成本。非等量分批方案的甘特圖如圖2所示。該方案將工件分成了10批，其中B、C、D、E四種工件分別分為2（7，3），2（6，4），2（4，6），2（3，7）個子批，A、F兩種工件不分批，黑色部分表示批次啟動時間。

4 結(jié)束語

①本文針對多目標作業(yè)車間分批調(diào)度問題的特點，提出用DE變異策略改進的BBO算法及與之相適應(yīng)的編碼方法。算法利用機床的負載能力、工序的加工時間對工件進行非等量分批處理，使其工藝路線和加工順序同時得到優(yōu)化。通過實例仿真，對其性能進行分析，也證明了算法的可行性。

②從甘特圖中可以看出，分批意味著機床的換模次數(shù)會增多，可能會造成生產(chǎn)周期的延長。如果改變現(xiàn)有資源，縮短換模時間（一般當換模時間減少為原來的1/n時，則批量可減少為原來的1/n），在生產(chǎn)周期最短的目標下，還可以增加子批批次。

參考文獻：

[1]Song Y， Chan GH. Single item lot-sizing problems with backlogging on a single machine at a finite production rate[J].EurJOperRes2005；161（1）：191-202.

[2]裴小兵，譚林林.基于eM_plant的作業(yè)車間生產(chǎn)批量優(yōu)化研究[J].系統(tǒng)仿真學報，2015，27（7）：1458-1467.

[3]潘全科，朱劍英.多工藝路線的批量生產(chǎn)調(diào)度優(yōu)化[J].機械工程學報，2004，40（4）：36-39.

[4]曾強，楊育，程博，等.平順移動下等量分批FJSP多目標優(yōu)化研究[J].系統(tǒng)仿真學報，2012（5）：1046-1052.

[5]Shuai Jia， ZhiHua Hu. Path-relinking Tabu search for the multi-objective flexible job shop scheduling problem [J]. Computers & Operations Research， 2014（47）：11-26.

[6]白俊杰，龔毅光，王寧生，等.多目標柔性作業(yè)車間分批優(yōu)化調(diào)度[J].計算機集成制造系統(tǒng)，2010，16（2）：396-403.