1第14章布局設(shè)計(jì)的現(xiàn)代算法2車間設(shè)備布局問題是一種組合優(yōu)化問題,具有非線性等特性。車間設(shè)備平面布局問題可抽象為一維布局和二維布局問題。其中,一維布局可看作為單行設(shè)備布局問題,二維布局可歸結(jié)為多行設(shè)備布局問題。許多學(xué)者應(yīng)用遺傳算法、模擬退火算法等現(xiàn)代算法來解決車間設(shè)備布局問題并取得了一定的成果。14.1布局設(shè)計(jì)的數(shù)學(xué)建模求解算法3

從模型的數(shù)學(xué)特征來看,可分為兩種類型:一類是在給定的區(qū)域內(nèi)布置若干臺機(jī)器,要確定機(jī)器的位置坐標(biāo),這種問題本質(zhì)上是選址問題;另一類是預(yù)先確定若干個(gè)位置,將若干數(shù)目的機(jī)器分派到這些位置,如何派遣這些機(jī)器,才能使目標(biāo)函數(shù)最小,一般稱之為組合優(yōu)化問題。從設(shè)施的排列形式來看,有兩種形式:一種是單行布置,即設(shè)備排成一條直線;另一種為多行布置,設(shè)備排成兩行或多行。14.1.1設(shè)備布局問題數(shù)學(xué)模型41.單行布置的模型在建立單行布置的模型時(shí),首先要作如下假設(shè):假設(shè)機(jī)器的形狀是矩形,機(jī)器排成一列,機(jī)器的方位是預(yù)先確定的,如圖14-1所示。圖14-1單行布置示意圖5設(shè)有n臺機(jī)器排成一列,要確定各機(jī)器的位置坐標(biāo),使機(jī)器間運(yùn)送物料的成本最低。相關(guān)參數(shù)表示如下:

n——機(jī)器數(shù)量;

cij——在機(jī)器i、j間移動單位距離的成本;

fij——在機(jī)器i、j間的移動次數(shù);

dij——為機(jī)器i、j間的必要間隔距離;

Li——機(jī)器i水平方向長度;

xi——機(jī)器i相對于垂直基準(zhǔn)線OO'的坐標(biāo)。6則目標(biāo)函數(shù)為

（14-1）

約束條件為72.多行布置的模型

多行布置示意圖如圖14-2所示圖14-2多行布置示意圖8多行布置模型中的參數(shù)如下:

n——機(jī)器數(shù)量;

cij——在機(jī)器i、j間移動單位距離的成本;

fij——在機(jī)器i、j間的移動次數(shù);dLij——機(jī)器i、j間的水平必要間隔距離;dWij——機(jī)器i、j間的垂直必要間隔距離;

Li——機(jī)器i水平方向長度;

Wi——機(jī)器i垂直方向?qū)挾?

xi——機(jī)器i相對于坐標(biāo)原點(diǎn)O的x坐標(biāo);

yi——機(jī)器i相對于坐標(biāo)原點(diǎn)O的y坐標(biāo)。9則目標(biāo)函數(shù)為（14-2）約束條件為其中,i=1,2,…,n-1;j=i+1=2,3,…,n;M為使不等式成立的足夠大的正整數(shù);zij由式zij(1-zij)=0定義。這里引入了M和zij,當(dāng)兩臺機(jī)器位于同一行時(shí),在列方向沒有限制,此時(shí)zij為0;當(dāng)兩臺機(jī)器在同一列時(shí),zij=1。103.二次分派問題模型給定n個(gè)地點(diǎn),現(xiàn)要把n個(gè)設(shè)備分配到這n個(gè)地點(diǎn),這實(shí)際上是組合問題,共有n!種方案。在這n!種方案里找最佳方案使總的物料搬運(yùn)費(fèi)用最小。二次分派問題模型一般可表述為（14-3）式中n——機(jī)器數(shù)量; cij——在機(jī)器i、j間移動單位距離的成本; fij——在機(jī)器i、j間的移動次數(shù); dkh——地點(diǎn)k、h間的距離; xik——決策變量,取0或1。當(dāng)設(shè)施i被派遣到地點(diǎn)k,xik=1;否則為0。11約束條件為其中，xik,xjh為0或1。121.遺傳算法的結(jié)構(gòu)(1)編碼與譯碼。許多應(yīng)用問題結(jié)構(gòu)很復(fù)雜,但可以化為簡單的位串形式編碼表示,我們將問題結(jié)構(gòu)變換為位串形式編碼表示的過程叫編碼;而相反將位串形式編碼表示變換為原問題結(jié)構(gòu)的過程叫譯碼。(2)適應(yīng)度函數(shù)。(3)遺傳操作。簡單遺傳算法的遺傳操作主要有三種:選擇(selection)、交叉(crossover)、變異(mutation)。改進(jìn)的遺傳算法大量擴(kuò)充了遺傳操作,以達(dá)到更高的效率。(4)控制參數(shù)。一般在程序設(shè)計(jì)中交叉發(fā)生的概率要比變異發(fā)生的概率大若干個(gè)數(shù)量級,交叉概率取0.6~0.95之間的值;變異概率取0.001~0.01之間的值。14.1.2遺傳算法在布局設(shè)計(jì)中的應(yīng)用132.遺傳算法應(yīng)用舉例(1)問題的描述。假設(shè)有9臺設(shè)備M1~M9。在某個(gè)生產(chǎn)階段設(shè)備之間的物流矩陣(實(shí)際上就是從—至表)如圖14-6所示?，F(xiàn)需要將這9臺設(shè)備進(jìn)行布置,使其運(yùn)輸工具的總行程最小。設(shè)備布局用設(shè)備的位置向量w=[w1,w2,w3,w4,w5,w6,w7,w8,w9],其中w1~w9分別是設(shè)備M1~M9在布局中的位置。圖14-6設(shè)備之間的物流矩陣14目標(biāo)函數(shù)是

其中n為機(jī)器臺數(shù),w為當(dāng)前布局,qij為機(jī)器i和機(jī)器j間的物流量,見圖14-6,dij為機(jī)器i和機(jī)器j間的距離,隨機(jī)產(chǎn)生初始布局,計(jì)算其目標(biāo)函數(shù)值。15(2)遺傳算法的設(shè)計(jì)編碼方法。這里使用浮點(diǎn)數(shù)編碼方法,用設(shè)備的位置向量表示染色體,即xi=wi。適應(yīng)度函數(shù):因?yàn)檠芯吭O(shè)備布局問題的目的之一是使運(yùn)輸工具的總行程最小,即目標(biāo)函數(shù)是求問題的最小解,所以設(shè)適應(yīng)度函數(shù)F(x)為初始群體的產(chǎn)生:以隨機(jī)的方式將這9臺設(shè)備進(jìn)行排列,共得到M種設(shè)備布局形式。16選擇算子:這里使用比例選擇算子,即個(gè)體被選中并遺傳到下一代群體中的概率與該個(gè)體的適應(yīng)度大小成正比。交叉算子:將群體中M個(gè)個(gè)體以隨機(jī)的方式兩兩配對,組成M/2對配對個(gè)體組。每對配對個(gè)體組隨機(jī)選擇其中之一為Parent1,則另外一個(gè)個(gè)體為Parent2。為提高計(jì)算效率,需要設(shè)計(jì)一種新的交叉算子，這里采用的交叉算子如下,從Parent1中隨機(jī)地將一半數(shù)量的基因遺傳給Child1等位置的基因座上,按照Parent2的順序?qū)hild1缺少的另一半基因值依次賦給空基因座,用同樣的方法產(chǎn)生Child2,如圖14-7所示。17圖14-7交叉算子示意圖18變異算子:隨機(jī)地選取個(gè)體中兩個(gè)基因座,交換它們的基因,產(chǎn)生新個(gè)體。(3)運(yùn)算結(jié)果。在該算法中,采用保留最佳個(gè)體策略,加快了收斂速度,并且取得較優(yōu)的解。計(jì)算出最優(yōu)布局為(2,4,1,6,3,5,8,7,9)。在此布局下,目標(biāo)函數(shù)值為2530,而最劣布局的目標(biāo)函數(shù)值為3653。1914.1.3模擬退火算法在布局設(shè)計(jì)中的應(yīng)用1.模擬退火算法流程(1)隨機(jī)產(chǎn)生一個(gè)初始解x0,令xbest=x0,并計(jì)算目標(biāo)函數(shù)值E(x0)。(2)設(shè)置初始溫度T=T0。(3)當(dāng)T>Tmin時(shí),對應(yīng)某個(gè)具體的溫度T,重復(fù)執(zhí)行步驟(4)k次。(這時(shí)的Tmin與k要根據(jù)經(jīng)驗(yàn)設(shè)定)。20(4)對當(dāng)前最優(yōu)解xbest按照某一鄰域函數(shù),產(chǎn)生一新的解xnew。計(jì)算新的目標(biāo)函數(shù)值E(xnew),并計(jì)算目標(biāo)函數(shù)值的增量ΔE=E(xnew)-E(xbest)。如果ΔE<0,則xbest=xnew;如果ΔE>0,則p=e^(-ΔE/kT)。當(dāng)c=random[0,1]<p時(shí),xbest=xnew;否則xbest=xbest。(5)步驟(4)完成k次重復(fù)后,令T=Tnew。若T≤Tmin執(zhí)行步驟(6);若T>Tmin,回到步驟(3)。(6)輸出當(dāng)前最優(yōu)解,計(jì)算結(jié)束。212.模擬退火算法的簡單應(yīng)用考慮遺傳算法部分的例題,用模擬退火算法求解,要點(diǎn)如下:解空間S是所有布局方案的集合,S中的成員記為：(w1,w2,…,wk,…,wn),其中wk為第k臺機(jī)器所在的地點(diǎn),初始解可選為(1,2,…,n)。此時(shí)的目標(biāo)函數(shù)即為運(yùn)輸工具的總行程為:新解可以按

如下方式產(chǎn)生,隨機(jī)產(chǎn)生1和n之間的兩個(gè)相異的整數(shù)k和m。若k<m,則將(w1,w2,…,wk,wk+1,…,wm,…,wn)變?yōu)?w1,w2,…,wm,wm-1,…,wk+1,wk,…,wn);若k>m,則將(w1,w2,…,wm,wm+1,…,wk-1,wk,…,wn)變?yōu)?wm,wm-1,…,w1,wm+1,…,wk-1,wn,wn-1,…,wk)。223.模擬退火算法的參數(shù)控制問題(1)溫度T的初始值設(shè)置問題。(2)退火速度問題。(3)冷卻進(jìn)度表T(t)。假設(shè)時(shí)刻t的溫度用T(t)來表示,則經(jīng)典模擬退火算法的降溫方式為T(t)=T0/(lg(1+t))(14-5)而快速模擬退火算法的降溫方式為T(t)=T0/(1+t)(14-6)2314.2布置圖的設(shè)計(jì)算法1.算法的輸入數(shù)據(jù)類型有些算法只接受像相關(guān)圖之類定性的“物流”數(shù)據(jù),而有些接受由從—至表表示的定量物流數(shù)據(jù),還有一些算法同時(shí)接受相關(guān)圖和從—至表兩種數(shù)據(jù)(如BLOCPLAN)。布置算法也可以按其目標(biāo)函數(shù)來分類。布置有兩種基本目標(biāo):一個(gè)是使流量與距離乘積的和最小,另一個(gè)是使相鄰值最大。14.2.1布置圖設(shè)計(jì)算法的分類與原理242.以“量距積的和最小”為目標(biāo)的算法首先考慮基于距離的目標(biāo),設(shè)m為部門數(shù),fij為從部門i到部門j的物流量(以單位時(shí)間移動的集裝單元數(shù)來衡);cij為將一個(gè)單元的物料從部門i移動到部門j單位距離的成本。于是目標(biāo)函數(shù)是使單位時(shí)間內(nèi)部門間物料的移動總成本最小化,用數(shù)學(xué)式表達(dá)為式中dij——部門i到j(luò)的距離。在很多布置算法中,dij以部門矩心(Centroid)的最近直線距離來度量,但也可以按特定的通道結(jié)構(gòu)來量取。253.基于相近程度目標(biāo)函數(shù)的算法考慮基于相近程度的目標(biāo)函數(shù),其中相近程度的分值是按布置中所有相鄰兩個(gè)部門物流量值(或關(guān)系值)的總和來計(jì)算的。如果部門i和j相鄰(即共邊)就令xij=1,否則xij=0,目標(biāo)是求相鄰值最大,即式(14-8)所得相鄰值有利于比較不同方案的好壞。但經(jīng)常要評價(jià)一個(gè)特定布置在某個(gè)上下邊界的相對效率(相對優(yōu)劣)時(shí),設(shè)施規(guī)劃人員可采用以下“歸一化”的相鄰值,即2614.2.2CRAFT算法CRAFT是指計(jì)算機(jī)化的設(shè)施關(guān)系分配法。它采用從—至表作為流動的輸入數(shù)據(jù)。布置“成本”按式(14-7)所示的基于“量距積的和最小”的目標(biāo)函數(shù)值來衡量。這里的部門并不局限于矩形,布置表現(xiàn)方式為離散式。1.CRAFT算法的初始條件CRAFT是一種改進(jìn)型布置算法,所以先要給它一定的基礎(chǔ),如從一個(gè)已有設(shè)施的實(shí)際布置或由另一種算法給出的初始布置開始,先確定初始布置中各部門的矩心,然后計(jì)算兩兩部門矩心之間直角距離,并存儲在距離矩陣之中。272.CRAFT算法的迭代過程3.迭代結(jié)果依賴于路徑CRAFT是一種高度依賴于路徑的啟發(fā)式算法。要有效使用它,一般要盡可能找出幾種不同的初始方案,或在每次迭代時(shí)試試不同的二相或三相交換方式。4.CRAFT用于非矩形廠房的策略CRAFT一般僅限用于矩形廠房,但通過引入“虛”部門它也可以用于非矩形廠房。虛部門與其他部門沒有任何物流或相互作用,但要由布置規(guī)劃人員指定它的面積。5.CRAFT布置的修改2814.2.3CRAFT算法案例考慮有7個(gè)部門的制造廠,它各個(gè)部門的面積和從—至表如表14-1所示。假設(shè)所有的cij均為1,廠房及當(dāng)前的布置(作為CRAFT的初始布置)如圖14-8所示,其中每一方格代表20ft×20ft。因?yàn)榭捎玫目偯娣e72000ft2超出了總需求(70000ft2),所以就設(shè)一個(gè)虛作業(yè)部門H,面積為2000ft2(大多數(shù)情況下,根據(jù)超出的面積大小,對分布不均的空間需求可設(shè)置2~3個(gè)虛部門,設(shè)施中多余空間的分配對確定部門的未來擴(kuò)展很重要)。從實(shí)用角度考慮,我們假設(shè)收貨區(qū)A和發(fā)貨區(qū)G這兩部門的位置固定。291.從—至表該制造廠各部門的面積和從—至表如表14-1所示。302.計(jì)算它們矩心間的直角距離CRAFT首先計(jì)算圖14-8所示各部門的矩心,然后對每一個(gè)部門單位對計(jì)算它們矩心間的直角距離,并乘上從—至表中相應(yīng)的數(shù)據(jù)。圖14-8初始CRAFT布置及各部門的矩心313.迭代與交換隨后,CRAFT進(jìn)行第一次迭代,交換部門E和F的位置,所得布置如圖14-9所示。部門E和F面積并不相等,但位置相鄰,因此可以想像用一個(gè)框架將E和F框起來,不包括其他部門(如果E和F不相鄰就找不到這樣的框子)。CRAFT就在這個(gè)框架里交換E和F的位置。布置成本降低值的估算由交換部門E和F的矩心得到,為202單位。在交換部門E和F并計(jì)算出新的部門矩心后,CRAFT計(jì)算出圖14-9所示布置的實(shí)際成本為2953單位。因此實(shí)際減少的布置成本為21單位而不是202單位。32圖14-9交換部門E和F的位置所得布置33下一次迭代時(shí),估算的布置成本降低值是95單位,CRAET交換部門B和C的位置后的結(jié)果如圖14-10所示。該布置成本為2833.50單位,實(shí)際降低119.50單位。這清楚地說明估算的誤差在每一個(gè)方向都有。按估算成本,CRAFT確定再沒有其他的兩兩交換(等面積或相鄰)能進(jìn)一步降低布置成本。圖14-10交換B、C位置所得布置34圖14-11修改打磨后所得的布置4.布置的修改對圖14-10所示的布置打磨后,所得的布置如圖14-11所示。除了虛部門H,對其他部門沒有大改,但此布置比打磨前更合理、實(shí)用。3514.2.4MCRAFT算法案例MICRO-CRAFT(或簡稱MCRAFT)類似于CRAFT,只是上述約束放松了(即MCRAFT可以不管兩個(gè)部門是否相鄰就進(jìn)行換位)。這種改進(jìn)是采用一種布置形成技術(shù),它能在兩個(gè)面積不等、位置不相鄰的部門換位時(shí)“自動”地調(diào)整其他部門。MCRAFT不是將每個(gè)方格都分配給某個(gè)部門,而是先將設(shè)