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

1、Important & Selected Documents 工件加工的排序問題 問題提出 現(xiàn)在社會(huì)是建立在龐大的工業(yè)體系之上的。 每天我們的社會(huì)都需要消耗大量的工 業(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，Processingtime ）和工件的價(jià)值 （VAL， Valueifjobisselected ） .車間作業(yè)計(jì)劃研究一個(gè)工廠生產(chǎn)工序的計(jì)劃和安排，需

2、要計(jì)劃與合理安排各個(gè)工件在機(jī)器上加工的先后次序， 即擬訂加工工序， 通過(guò)各 個(gè)工件在機(jī)器上加工次序的合理安排，或要求整個(gè)選擇加工的工件價(jià)值最大。 有一個(gè)工廠現(xiàn)在有 12 種工件（編號(hào)為工件 1，工件 2，工件 12 ）需要 在車床加工?？紤]下面的工件加工的排序問題： 這 12 種工件都要求在車床上加工，車床一次只能加工一種工件，這 12 種工件 加工所需時(shí)間，每個(gè)工件的完工時(shí)間和每個(gè)工件的價(jià)值如表所示： 工件 加工時(shí)間（ h ） 完工時(shí)間 （h） 工件價(jià)值 1 2.8 9 8 2 3.2 7.5 4 3 1.2 15 16 4 4 23 3 5 2.7 10 7 6 0.9 22 20 7 2

3、.5 17 17 Important & Selected Documents Important & Selected Documents 8 3.3 33 11 9 1.7 7 7 10 2.5 18 12 11 3.6 25 5 12 4.7 11 18 由于工件必須在它們要求的時(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)過(guò)最初的分析，由于對(duì)于每個(gè)工

4、件只 有加工或不加工兩種選擇，我們可以確定這是一個(gè) 0-1 規(guī)劃問題，但是同時(shí) 我們又發(fā)現(xiàn)以上的要求使用我們模型的約束建立的過(guò)程非常的困難。顯然如 果按照工件價(jià)值從大到小的順序進(jìn)行加工就很有可能使完成時(shí)間較早的工件 不能加工而又有許多的剩的時(shí)間，從而得不到最大的價(jià)值。 所以我們不但要考慮工件的價(jià)值，而且要考慮工件的加工順序。正是因 為這一點(diǎn)使我們無(wú)法通過(guò)數(shù)學(xué)的形式將這種加工順序在總價(jià)值最大化要求下 體現(xiàn)出來(lái)。于是我們考慮了人為的先給出這樣的加工順序，既完成限制時(shí)間 較早的工件較早加工 （即如下表的加工順序） ，而正是這種順序解決了我們的 問題。這樣就可以對(duì)每個(gè)工件都有考慮。如果我們?cè)偌右赃m當(dāng)?shù)?/p>

5、約束就使問 題簡(jiǎn)單的解決了 Important & Selected Documents Important & Selected Documents 工件 加工時(shí)間（ h ） 完工時(shí)間 （h） 工件價(jià)值 9 1.7 7 7 2 3.2 7.5 4 1 2.8 9 8 5 2.7 10 7 12 4.7 11 18 3 1.2 15 16 7 2.5 17 17 10 2.5 18 12 6 0.9 22 20 4 4 23 3 11 3.6 25 5 8 3.3 33 11 假設(shè)及符號(hào)設(shè)定 假設(shè)一個(gè)工件加工完成后到另一個(gè)工件加工的開始之間的時(shí)間不計(jì) ：加工工件的總價(jià)值 ：第 n 個(gè)工件是不是

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