學(xué)生建模報告-工件加工順序問題.doc

1、Importa nt & Selected Docume nts工件加工的排序問題問題提出現(xiàn)在社會是建立在龐大的工業(yè)體系之上的。每天我們的社會都需要消耗大量的工 業(yè)產(chǎn)品，而在工業(yè)品生產(chǎn)中又存在著許多這樣那樣的問題， 如如何提高生產(chǎn)效率， 如何在一定的時間內(nèi)生產(chǎn)出最大的產(chǎn)品價值等等。 下面的問題就是一個具體的例 子。計劃排序問題中的車間作業(yè)問題，研究n個工件在每個工件都有完工的日期（DD，Duedate）,加工的時間（PT, Process in gtime ）和工件的價值（VAL, Valueifjobisselected ）.車間作業(yè)計劃研究一個工廠生產(chǎn)工序的計劃和安排，需 要計劃與合理安排

2、各個工件在機(jī)器上加工的先后次序，即擬訂加工工序，通過各個工件在機(jī)器上加工次序的合理安排，或要求整個選擇加工的工件價值最大。有一個工廠現(xiàn)在有12種工件（編號為工件1，工件2，工件12 ）需要 在車床加工?？紤]下面的工件加工的排序問題：這12種工件都要求在車床上加工，車床一次只能加工一種工件，這12種工件加工所需時間，每個工件的完工時間和每個工件的價值如表所示：工件加工時間（h）完工時間（h）工件價值12.89823.27.5431.215164423352.710760.9222072.51717Importa nt & Selected Docume nts83.3331191.777102.

3、51812113.6255124.71118由于工件必須在它們要求的時間內(nèi)完工，按照表的數(shù)據(jù)，為該工廠安排選擇加工工件的種類及加工的次序，使得整個選擇加工的工件價值最大。問題分析問題最后的要求是要計算生產(chǎn)產(chǎn)品的價值總和的最大化，是一個優(yōu)化的 問題。問題的關(guān)鍵就在于每一個工件的加工都有一個完成時間的限制，如何在 限制的時間內(nèi)完成最大的產(chǎn)品價值。經(jīng)過最初的分析，由于對于每個工件只 有加工或不加工兩種選擇，我們可以確定這是一個 0-1規(guī)劃問題，但是同時 我們又發(fā)現(xiàn)以上的要求使用我們模型的約束建立的過程非常的困難。顯然如 果按照工件價值從大到小的順序進(jìn)行加工就很有可能使完成時間較早的工件 不能加工而又

4、有許多的剩的時間，從而得不到最大的價值。所以我們不但要考慮工件的價值，而且要考慮工件的加工順序。正是因 為這一點(diǎn)使我們無法通過數(shù)學(xué)的形式將這種加工順序在總價值最大化要求下 體現(xiàn)出來。于是我們考慮了人為的先給出這樣的加工順序，既完成限制時間 較早的工件較早加工（即如下表的加工順序），而正是這種順序解決了我們的 問題。這樣就可以對每個工件都有考慮。如果我們再加以適當(dāng)?shù)募s束就使問 題簡單的解決了Importa nt & Selected Docume nts工件加工時間（h）完工時間（h）工件價值91.77723.27.5412.89852.7107124.7111831.2151672.51717

5、102.5181260.9222044233113.625583.33311假設(shè)及符號設(shè)定假設(shè)一個工件加工完成后到另一個工件加工的開始之間的時間不計:加工工件的總價值:第n個工件是不是要加工（要加工取“ 1”，不加工取“ 0 ”）模型建立模型求解經(jīng)過編程求解得：（程序見附表）Thebestchoiceis:101011111111Important & Selected DocumentsThelargestvalueis117.000000.即選擇加工的工件既加工順序?yàn)?9，1，12，3，7，10，6，4，11，8 號工件。按照這樣的選擇和加工順序就可以得到最大的生產(chǎn)價值117 。結(jié)果分析與發(fā)展1滿足模型約束的像 :101011111111 的序列有多種，每一種可能的方案，都對應(yīng)一總價值：Y,和總的加工時間：T。我們可以人為的按照自己的要求給 總價值 Y 和總時間 T 分別賦于不同的權(quán)值： p1,p2 。通過計算： P1GY+p2GT （p1+p2=1 ）可以得到滿足自己需求的方案,比如加工的時間短,但是價值也 不 怎 么 少 。 我 們 如 果 使 ：p1=2/3,p2=1/3。 此 時 的 目 標(biāo) 。maGp1GY+p2GT=94.32 。2我們只考慮了每個工件只