裴小兵++何倩男

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

中圖分類號(hào)：TH165 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1006-4311（2017）07-0065-03

0 引言

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

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

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

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

1.1 問題描述

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

1.2 數(shù)學(xué)模型

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

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

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

3 實(shí)例仿真

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

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

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

4 結(jié)束語

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

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

參考文獻(xià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)仿真學(xué)報(bào)，2015，27（7）：1458-1467.

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

[4]曾強(qiáng)，楊育，程博，等.平順移動(dòng)下等量分批FJSP多目標(biāo)優(yōu)化研究[J].系統(tǒng)仿真學(xué)報(bào)，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]白俊杰，龔毅光，王寧生，等.多目標(biāo)柔性作業(yè)車間分批優(yōu)化調(diào)度[J].計(jì)算機(jī)集成制造系統(tǒng)，2010，16（2）：396-403.