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

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

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

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

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

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