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

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

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

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

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

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