基于改進BBO算法的多目標柔性作業車間調度研究

裴小兵++何倩男

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

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.

關鍵詞： BBO算法；子批量；作業車間；分批；調度

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

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

0 引言

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

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

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

1 多目標柔性作業車間調度問

1.1 問題描述

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

1.2 數學模型

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

2 生物地理學優化算法

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

3 實例仿真

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

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

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

4 結束語

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

②從甘特圖中可以看出，分批意味著機床的換模次數會增多，可能會造成生產周期的延長。如果改變現有資源，縮短換模時間（一般當換模時間減少為原來的1/n時，則批量可減少為原來的1/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的作業車間生產批量優化研究[J].系統仿真學報，2015，27（7）：1458-1467.

[3]潘全科，朱劍英.多工藝路線的批量生產調度優化[J].機械工程學報，2004，40（4）：36-39.

[4]曾強，楊育，程博，等.平順移動下等量分批FJSP多目標優化研究[J].系統仿真學報，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]白俊杰，龔毅光，王寧生，等.多目標柔性作業車間分批優化調度[J].計算機集成制造系統，2010，16（2）：396-403.