零件加工時(shí)間最優(yōu)化的動(dòng)態(tài)規(guī)劃模型

1、零件加工時(shí)間最優(yōu)的動(dòng)態(tài)規(guī)劃模型零件加工時(shí)間最優(yōu)的動(dòng)態(tài)規(guī)劃模型摘要摘要零件加工最有時(shí)間問題是典型的動(dòng)態(tài)規(guī)劃問題。建立一個(gè)動(dòng)態(tài)規(guī)劃模型，按照這類問題的基本思路，抓住等待時(shí)間這一關(guān)鍵要素，運(yùn)用計(jì)算機(jī)模擬求解（我們用C寫了一個(gè)程序（見附錄），可以模擬零件個(gè)數(shù)12以內(nèi)的所有情況，得出最優(yōu)時(shí)間和零件編號(hào)的順序。程序已做成文件，與論文的電子稿一起.exe放在ftp上）。關(guān)鍵詞：關(guān)鍵詞：動(dòng)態(tài)規(guī)劃；機(jī)床零件；時(shí)間最優(yōu)；1問題的重述問題的重述例題3(工件排

2、序問題)某修理車間因修理工作需要生產(chǎn)個(gè)不同的工件，每個(gè)工件都需要先在n機(jī)床，后在機(jī)床上進(jìn)行加工。不妨用編號(hào)分別代表不同的工件，AA123...n以、表示工件需在，機(jī)床上加工的時(shí)間。如果該車間只有一臺(tái)機(jī)iaibiABA床，一臺(tái)機(jī)床，且、不受加工工件順序的影響，問如何安排零件在，BiaibA機(jī)床上的加工順序，才能使機(jī)床加工總時(shí)間（從機(jī)床開始加工，至兩機(jī)床BA均將工件加工完為止）最短？2約定符號(hào)和名詞解釋約定符號(hào)和名詞解釋：為第階段選擇的零件

3、需要的等待時(shí)間。??max0kkkssTab??k：為零件通過機(jī)床的順序編號(hào)的集合；S：為順序集合中第個(gè)元素，即為第階段選擇的零件的編號(hào)。ksSkk3問題的分析問題的分析2第一個(gè)零件不需要等待，時(shí)間是，10T?從第二個(gè)零件起，等待時(shí)間：（5.1）????max023...kkkssTabkn???根據(jù)上圖，加工所有零件所需要的總時(shí)間是第一個(gè)零件的機(jī)床時(shí)間、Aia所有零件的機(jī)床加工時(shí)間、所有等待時(shí)間三者之和，為：B1niib??kT?，（

4、5.2）11knnsikiVabT??????根據(jù)窮舉法，通過C語言編程（程序見附錄），可解得最終數(shù)據(jù)。6模型的評(píng)價(jià)和推廣零件加工時(shí)間最優(yōu)問題，是最簡單最常用的動(dòng)態(tài)規(guī)劃問題。本問題中的模型就是針對(duì)這類問題建立的，模型的優(yōu)點(diǎn)：能準(zhǔn)確的計(jì)算住零件加工的順序，和所需的時(shí)間。模型的缺點(diǎn)：模型的時(shí)間復(fù)雜度是，當(dāng)零件個(gè)數(shù)較多時(shí)（從超過9個(gè)開始）!n，模型運(yùn)算所需的時(shí)間飆升，對(duì)零件個(gè)數(shù)較大的情況，這個(gè)模型無能為力。參考文獻(xiàn)參考文獻(xiàn)[1]張潤琦，《動(dòng)態(tài)

5、規(guī)劃》，1989：1018.[2]秦學(xué)志，《實(shí)用最優(yōu)方法》，第三版，大連：大連理工大學(xué)出版社，2007.附錄附錄C語言編寫的程序?yàn)椋?include#include#include#definecl((clock_t)1)計(jì)算時(shí)間函數(shù)#defineM23intnt=0s[M]re[M]doublea[M]b[M]tm=111111111tn=0.0wt=0.0doublemax(doublexdoubley)if(xy)returnxe