佟昕葉彭偉峰

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

i每個(gè)機(jī)器只占一個(gè)位置，故j

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

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

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

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

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

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

,

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

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

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

七、模型的評(píng)價(jià)與推第五，利用問(wèn)題一巧妙地驗(yàn)證了遺傳算法的度其中，01型整數(shù)規(guī)劃是整數(shù)規(guī)劃中的特殊情形，它的變量xi僅取值01。這時(shí)xi稱(chēng)為01變量，或稱(chēng)二進(jìn)制變量。01規(guī)劃主要用于求解互斥的計(jì)劃問(wèn)題、約束條件遺傳算法是模擬生物進(jìn)化論的自然選擇和遺傳學(xué)機(jī)理的生物進(jìn)化過(guò)程的計(jì)索空間的知識(shí)或其它輔助信息，而僅用適應(yīng)度函數(shù)值來(lái)評(píng)估傳并八、參考文劉暉，多生產(chǎn)線(xiàn)車(chē)間設(shè)備布局問(wèn)題研究 姜啟源，謝金星，，數(shù)學(xué)模型，：高等教育，2006機(jī)電工程學(xué)報(bào)，第26卷（2期），2006。張琨，，，2010從入門(mén)到精通，：電子工業(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)));!任意兩臺(tái)機(jī)器之間!每種產(chǎn)品對(duì)應(yīng)的每條線(xiàn)路的長(zhǎ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