佟昕葉彭偉峰

有可選加工路線的多產(chǎn)品生產(chǎn)車間機器布局生產(chǎn)組織重構(gòu)時必須解決的重要問題之一。本文根據(jù)生產(chǎn)各產(chǎn)品可供選擇的各加工路小的前提下，建立數(shù)學(xué)模型求解產(chǎn)品對應(yīng)的加工路線以及所有機器相應(yīng)的放置位置。L，求出機器i,j之間的距離M(i,j)，然后求出生產(chǎn)每件產(chǎn)品每種路線下的材料移動距離dij，并求出每種產(chǎn)品的材料移動最小距離Si，以總材料移動距離最短8minSiRi為目標(biāo)函數(shù)，建立分布優(yōu)化方程模型，利用 問題二，考慮到有20個機器，傳統(tǒng)的方法因運算量太大而不再適用，遂采用啟發(fā)分布優(yōu)化問題。本文首先構(gòu)造出與不同的位置排列方式一一對應(yīng)的向量a，建立函數(shù)yD(a)，y為該種排列方式下最短的距離，然后應(yīng)用遺傳算法，依次得到父代、遺傳線為 ，機器M1M20對應(yīng)位置為L2,L11,L15,L4,L1,L16,L13,L20,,01一、問題重產(chǎn)線上沒有停留的零件和交叉搬運，從而減少了搬業(yè)，保證安全：由于生產(chǎn)設(shè)備能求所有產(chǎn)品P1P10對應(yīng)的加工路線以及所有機器M1M20相應(yīng)的放置位置附錄2：各不同位置間的距離（含兩個表格；二、問題分問題一旨在研究在該車間生產(chǎn)過材料移動總距離最小的情況下，所有產(chǎn)該問題屬于組合優(yōu)化問題并具有NP完全屬性,而任何NP完全問題只有通過列舉所有可能的組合，才能得到最優(yōu)解，由于問題1的求解規(guī)模不大，所以本文01規(guī)劃首先,對于機器的不同擺放位置，本文通過一個1010的01矩陣來表示，然后利Li間的距離矩陣構(gòu)造出機器i,j之間的距離，后求出每件產(chǎn)品在不同路線下的材問題二旨在研究車間在生產(chǎn)過材料移動的總距離最小時的所有產(chǎn)品P1P10對應(yīng)的加工路線以及所有機器M1M20相應(yīng)的放置位置。 三、模型假 的比例為1 的比例為0.4四、符號說第i個機器（問題一中i1, ,10,問題二中i1, ,20第i個位置（問題一中i1, ,10,問題二中i1, ,20第i種產(chǎn)品（問題一中i1, ,8,問題二中i1, ,10LLi間的距離矩X01xij0或M機器MiM(ij為機器MiMj產(chǎn)品i的產(chǎn)量（問題一中i1, ,8,問題二中i1, ,10S101矩陣，每行Si表示對某一放置位置，生產(chǎn)一件產(chǎn)品Pia位置所對應(yīng)的行向量，問題一中a=(li,li ,li)，問題二中a=(li,li ,li b機器所對應(yīng)的向量，問題一中b ,m10)，問題二中b ,m20yABC五、模型的建立與求放機器。廣義地講，車間布置包括物料的運送和存放、機器、工作的位置以及其他NP-完全問題，本文采用01規(guī)劃來求解該多元整數(shù)規(guī)劃問題，并用模擬位置與機器一一對應(yīng)，由此，本文考慮使用一個1010的01X來表示。令行代表機器，列代表位置，0、1代表機器是否在該位置，即：令

i每個機器只占一個位置，故j

1M(i,j—機器i,j之間的距離任意兩機器i,j之間的距離為

xikLknn1kxikLknX中第iL矩陣中第nXk1nxij中第i行元素中第m那么該式等于Lmn。故上式可簡化 Lmnxjn，該式只保留了L矩陣中以X第j行中素1所在列為列數(shù)的第m行元素，設(shè)X中第j行元素中第o個元素不為0，LmnxjnLmoM(i,產(chǎn)品ij線j1,23P1P62,1d13d62d63。M(dijM(ja,ja)M(ja,ja)M(

a123j表示i產(chǎn)品在第a條路線下的第nj 1234567123578123456783456789表---產(chǎn)品i的最短每件產(chǎn)品的材料移動距離最短，由此得到：Simin每件產(chǎn)品有三種生產(chǎn)路線，取使距離最短的加工路線，其機器移動距離即為Si的和，其中權(quán)值為各產(chǎn)品的產(chǎn)量，即：8minSi其中，Ri為產(chǎn)品i的產(chǎn)量88minSi

10 M(i,j)xikLknxmindmind

n1k

M(ja,ja)M(ja,ja)

M(

,jaSSi

jx x 根據(jù)上述分布優(yōu)化方程，本lingo（4），由于程序運行時間太長，MMMMMMMM表12321111表10出最優(yōu)解，若機器時，使用該方法幾乎不可能算出全局最優(yōu)解。由此可見，0-1規(guī)雖然0-1規(guī)劃法無法得全局最優(yōu)解，但能得到一個較好地局部最優(yōu)解，于是本文使結(jié)構(gòu)對應(yīng)于子的不同量水平在高溫下，粒子的量較高可以動和重（被稱為退火，粒子就可以在每個溫度下達(dá)到熱平衡。當(dāng)系統(tǒng)完全被冷卻時，最終形成計算目標(biāo)函數(shù)確定初始溫度和降溫是否是否否是否滿足終件是3變換產(chǎn)生新解計算目標(biāo)函圖構(gòu)造函yD(a（附9）a為一與位置排列一一對應(yīng)的向y為在該種排列由于位置排列方式和a向量之間構(gòu)成了一一對應(yīng)的關(guān)系，當(dāng)取定一組a列方式也確定了。不妨令a向量對應(yīng)的矩陣為a`，其中a向量的各分量為110的矩陣a`的個各元素。令機器排列方式和b向量之間構(gòu)成了一一對應(yīng)的關(guān)系，令b向量對應(yīng)的矩陣為b`，其中b向量的各分量為110的矩陣b`的個各元素.機器矩陣為b`(M1M2 M20)那么必存在一個矩陣Q使得b`a`Q且Q每行每列只有一個元素為1，其它元素為0。那么Mi距離矩陣MQTLQT作，得到矩陣S S3,DRS即為最短距離，以此建立函數(shù)yD(a)T解空間a可表為al1,,l10 ,l10為1，1的一個排列其中每一個數(shù)的排列（7,5,8,2,9,10,4,1,6,3

liji在位置ja09min ,l10)dli2任選序號uv（uv為1~10之間的整數(shù)，交換u與v之間的順序，此時的新路徑如圖2所示：圖②3任選序號uvw（uvw，且uvw為1~10之間的整數(shù)，將u和v之間的路徑插到w之后，對應(yīng)的新路徑如圖3所示：圖對于23DD(a)D(a0

P1,Dexp(exp(D/T),D如果D0,則接受新的路徑。否則，以概率exp(DT)接受新的路徑，即若exp(DT大于0到1之間的隨機數(shù)則接受，初始溫度T為1利用選定的降溫系數(shù)進行降溫即：0.999

，得到新的溫度，這 二，用選定的終止溫度e1030，判斷退火過程是否結(jié)束。若Te，算法結(jié)束，輸出5，11MMMMMMMM表23112121表問題問題二中有20個機器，而01規(guī)劃程序運行效率低且不能用于機器數(shù)大于15的問執(zhí)行突執(zhí)行突執(zhí)行交根據(jù)適應(yīng)度選擇個執(zhí)根據(jù)適應(yīng)度選擇個 生下一代，經(jīng)過數(shù)代遺傳后產(chǎn)生優(yōu)化，產(chǎn)生接近最優(yōu)解的位置安排方式。應(yīng)用范圍過向量a表示不同的排列方式。a向量的第i個分量，即代表Mi的位置。當(dāng)a向量變化時，M的位置也相應(yīng)的變化。這樣排列方式與a向量構(gòu)成了一一對應(yīng)的關(guān)系。輸出結(jié)滿足終止條件i=50否輸出結(jié)滿足終止條件i=50否隨機隨機產(chǎn)生初始種圖行了改良，以一行隨機產(chǎn)生的a向量開始，通過改良圈算法選取1000個，帶入設(shè)a0為一位置向量，若li在a0j列，那么編碼的第ij10a 圖體記為b1、b2。具體操作過程為：

,

,...,li 20a2lj,li,...,li,...,li 20隨機生成交叉位k,1k20遺傳操作生成b1、b2，若k10，其表達(dá)式b1li,li,...,lj,...,lj 20b1lj,lj,...,li,...,li 20將準(zhǔn)備進行變異的父代表示a

lili ,li,li1 1920變異后產(chǎn)生的記為c1隨機生成一個150的向量，其中每個元素在0110.1A1行的元素作為T中第一行的元素，若大于0.1，則對隨機矩陣的第二列做相同的變換。即若隨機矩陣的第2.5.8列大于0.1A的第2.5.8行作為T的第1.2.3行，由此的得到T，這樣的T也可能不存在。隨機不重復(fù)的選取110間的三個數(shù)，u、v、w，令uvw。對T中的一行，uv間的元素放置w列后10a向量為例，若u2,v4w7，變換如圖6所示。圖這樣生成的矩陣叫做變異得到的子代，記做C令GA CT,將每行帶入yD(a)，對y升序排列，取前50項 對這 本文采用第一類方法，然后計算出D(a，直到第50代，循環(huán)迭代結(jié)束，輸出利用程序（附錄6，12）對遺傳進行實現(xiàn)，并計算加工路線。由于遺傳算法最小的一組位置放置方式，結(jié)果表6,7所示。MMMMMMMMM表1111111112表

六、以及加工路線，得到與上述一樣的結(jié)果?？梢?，綜合運用0-1規(guī)劃模型和模擬算法MMMMMMMM表23112121表

七、模型的評價與推第五，利用問題一巧妙地驗證了遺傳算法的度其中，01型整數(shù)規(guī)劃是整數(shù)規(guī)劃中的特殊情形，它的變量xi僅取值01。這時xi稱為01變量，或稱二進制變量。01規(guī)劃主要用于求解互斥的計劃問題、約束條件遺傳算法是模擬生物進化論的自然選擇和遺傳學(xué)機理的生物進化過程的計索空間的知識或其它輔助信息，而僅用適應(yīng)度函數(shù)值來評估傳并八、參考文劉暉，多生產(chǎn)線車間設(shè)備布局問題研究 姜啟源，謝金星，，數(shù)學(xué)模型，：高等教育，2006機電工程學(xué)報，第26卷（2期），2006。張琨，，，2010從入門到精通，：電子工業(yè)，2011謝金星，薛毅，優(yōu)化建模與LINDO/LINGO， ，2005九、附產(chǎn)加工路123---（3,4,表加工路123-----表

00000000000000000000表產(chǎn)產(chǎn)表產(chǎn)產(chǎn)表!0-1規(guī)劃products/1..8/:q,s;places/1..10/;machines/1..10/;roads/123/;l=0l=04115204554393631391237 152430382539 3356244435491230 254044501150020 51121238263136 4547194913225851q=282261277218397451388enddata@for(link4(i,j)|i#ne#@sum(machines(k)|k#ne#n:x(i,k)*l(k,n))*x(j,n)));!任意兩臺機器之間!每種產(chǎn)品對應(yīng)的每條線路的長度S0=[75829104163];%初始解fork=1:Nifdf<0ifT<e

forwhileforif

fork=1:wforforifdf<0

fori=1:Nforj=1:Lfori=1:2:Niflength(by)==0forj=1:L3form=1:TL

clearDs;clearDZ;forallorder_m=1:n_1

forforallorder_i=1:n-if(allorder_K(n-allorder_i)~=0)ifD1(allorder_P)<dforwhileforif

fork=1:wforkkk=1:Nforifdf<0

fori=1:Nforj=1:Lfori=1:2:Niflength(by)==0forj=1:L3form=1:TLclearDs;clear附錄functionfori=1:length(X