數(shù)學建模 工件的加工次序問題（課堂PPT）

1、.1工件的加工次序問題孫瑜 張成偉 徐兆國.2摘要 本文探討的問題是如何安排工件的加工順序以使得各工件的完工時間之和最短、機床花費的總時間最小、加工工件的總補償費用最少。求解這一問題主要用到了圖論和線性規(guī)劃的數(shù)學方法。在第一問與第三問中，本文先將題中所給出的數(shù)據(jù)、條件轉(zhuǎn)換為圖，在此基礎上表示出目標函數(shù)及約束條件，利用非線性規(guī)劃求得最優(yōu)解。第二問中，文本利用了圖論中哈密頓鏈原理，將完成工件加工的問題轉(zhuǎn)化為有向圖中點的遍歷，所建立的模型可遍歷哈密頓鏈中的全部點且得到最短路徑。.3 最終求解模型，結(jié)果如下： (1) 加工順序為4109711538612141213時，各工件的完工時間和最小，為258

2、8。 (2) 加工順序為4711109538621141213時，機床花費的總時間最小，為114。 (3) 加工順序為4711105938612141213時，總補償費最小，為142.42。 (4) 對u進行討論，可分為以下幾種情況:u92、92=u108、108=u174、174=u199、199=u209、209=u219、219=u269、269=u309、309=u=345,并進而用lingo可求出答案 (5)把一般情況下上述各問題的解法進行的一些討論。.4問題重述與分析 現(xiàn)有14件工件等待在一臺機床上加工，某些工件的加工必須安排在另一些工件加工完工以后才能開始，第j號工件的加工時間t

3、j及先期必須完工的工件號i由下表給出。工件號j1234567891011121314tj2028251642123210242040243616前期 工件號i3,45,7,85,9-10,113,8,943,5,74-4,76,7,145,121,2,6.51）若給出一個加工工序，則確定了每個工件的完工時間（包括等待與加工兩個階段）。試設計一個滿足條件的加工順序，使各工件的完工時間之和最小。2）若第j號工件緊接著第i號工件完工后開工，機床需要花費的準備時間是：3）假定工件的完工時間（包括等待與加工兩個階段）超過一確定時限u時，則需支付一定的補償費用，其數(shù)值等于超過時間與費用率之積，各工件的補償

4、費用率i如下：u=100，tij=0，安排一個加工順序，使總補償最小。(4)試對(3)中的u進行討論。(5)能否對一般情況下上述各問題的解法進行一些討論。j1234567891011121314i121015161011108541010812.6問題分析這五個問題都是要求一種最優(yōu)加工次序，使得工件完工時間和、機床花費時間、總補償費分別達到最小。由于題中安排了各工件的前期工件，所以解題時可以先利用圖論的知識將加工工件之間的先后關系表示出來。由于第j號工件完工時間和補償費與其前置加工工件完工時間的累加密切相關，所以單純用圖論解決完工時間和補償費的最優(yōu)化是很復雜的，但是可以在有向圖的基礎上將目標函

5、數(shù)、約束條件巧妙表示出來，再結(jié)合非線性規(guī)劃解出最優(yōu)解。在第二問中，求得的是機床花費總時間的最小值問題，實質(zhì)就是要解決機床的總準備時間最短的問題。該問題可轉(zhuǎn)化為最短路徑問題，但是同時要考慮到各加工工件的前期工件。這就需要構造一個好的有向圖，再遍歷點并求得最短路徑。.7模型假設 (1) 假設相鄰工件之間的加工是緊挨著進行的，即除了準備時間外，不浪費任何時間。 (2) 假設機床在加工工件的過程中運轉(zhuǎn)正常。 (3) 假設不會發(fā)生意外情況（機器壞掉、加工的工件不能正常使用等。）.8符號說明 第i號工件在加工流程中的加工序號 各工件完工時間之和 機床花費的總時間 加工時的總補償費 表示從節(jié)點i(表示加工工

6、件i)到節(jié)點j(表示加工工件j)的準備時間。 是0-1變量，表示是否選取直接從加工第i號工件接替到加工第j號工件這一順序 ，表示選取了從加工i號工件到加工j號工件的順序 ，表示不選取從加工i號工件到加工j號工件的順序 表示第 個工件的完工時間超過了確定時限u j=1,2.14 表示第 個工件的完工時間沒有超過了確定時限u j=1,2.14 iy1Z2Z3Zijwijx10ijx1im0jm.9模型建立與求解 1、總完工時間最優(yōu)模型 問題1中要求根據(jù)各個工件的加工時間，以及其前期工件的要求，建立以總的完工時間最少為目標的目標函數(shù)。在加工時間一定的情況下，對其進行合理的排序，使目標函數(shù)達到最小值。

7、.10 (1)模型建立 總的完工時間包括各工件的等待時間之和與各工件的加工時間之和。由于各工件的加工時間之和是一定的，所以完工時間最優(yōu)問題等價于各工件等待時間總和的最優(yōu)化問題。 設第 個工件的加工次序為 ，總的完工時間為 。 每個工件都被其后置加工工件所等待，因此，總的工件等待時間即每個工件被等待的時間總和。 第 個工件被等待的時間為 ，則所有工件被等待的時間為 所有工件的加工時間為 因此總的完工時間之和為： iy1Ziity )14(141)14(iiity345141iit1411411411)15()14(iiiiiiiityttyZ.11 (2) 約束條件分析 設 是 的前期工件，則第

8、 個工件的加工次序應早于第 個工件的加工次序，所以 由題目當中的表可得約束條件為： 均為正整數(shù)， i=1,2,314。 ; 1;14; 1)( ; 1)(; 1)( ; 1)( ; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 141326226122121110614214114121314127114938478611510593538231yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyiy.12 (3) 相關圖形 由題目中的表可作圖如下： 11 9 4 7 5 3 10圖1.13 (4) 模型求解 這是一個

9、最優(yōu)化問題，由于變量和約束條件都很多，人工求解有一定困難，因此可以借助lingo軟件，求解得到最佳加工順序和最少總完工時間。 在lingo軟件中求解的部分代碼： MIN=5175-20*y1-28*y2-25*y3-16*y4-42*y5-12*y6-32*y7-10*y8-24*y9-20*y10-40*y11-24*y12-36*y13-16*y14=0;（目標函數(shù)的表示）。 由lingo計算得使得總完工時間最短的最佳加工次序為： ， 此時總完工時間為2588。 1 8 3 14 13 2 6 12圖21312142168351179101.14 2、機床花費總時間最優(yōu)模型 (1)模型建立

10、機床花費總時間包括機床的總準備時間和總的工件加工時間?？偟墓ぜ庸r間是一定的，因此解決機床花費總時間最短問題等價于機床準備總時間的最優(yōu)化問題。本模型將此問題轉(zhuǎn)化為圖論中的遍歷哈密頓鏈問題。構造圖如下 11 9 4 7 5 3 10圖3.15 圖中的頂點表示加工工件號，實線表示規(guī)定的加工先后順序，如有向?qū)嵕€ 表示加工順序應該是先加工了4號工件才能加工9號工件。有向虛線表示可以相鄰加工的兩個工件號，如虛線 表示可以先加工5號工件，再緊接著加工9號工件； 表示可以先加工9號工件，再緊接著加工5號工件。有向弧的權用 表示從節(jié)點i(表示加工工件i)到節(jié)點j(表示加工工件j)的準備時間。 是0-1變量，

11、表示是否選取加工第i號工件后緊接著加工第j號工件這一路徑。 ，表示選取了從加工i號工件到加工j號工件的順序 ，表示不選取從加工i號工件到加工j號工件的順449x59x95xijw10ijxijx.16 現(xiàn)要求求得一種加工順序，使得機床的總等待時間最短。轉(zhuǎn)換為圖論問題即是尋找一條最短路徑，并滿足如下要求： 該路徑經(jīng)過所有節(jié)點一次且僅一次，且無環(huán)，因此路徑數(shù)目要比節(jié)點數(shù)目少1； 該路徑經(jīng)過工件i所代表的節(jié)點時，必須已經(jīng)經(jīng)過工件i的所有前置節(jié)點。 根據(jù)圖1，與圖2，3號工件必定是排在第7個序號上，13號工件必定排在最后一個加工序號上，同理，12號工件必定是倒數(shù)第二個被加工，

12、14號工件必定是倒數(shù)第三個被加工。因此問題簡化為找到圖3、圖4這兩部分的最優(yōu)加工順序。建立模型為： Min s.t. 14114114114113)4.1 , 0(1 , 0)4.1 , 0( 1)4.1 , 0( 1ijijijjijiijxjxjxjx)4.1 , 0,( ,141141jixwzijijij.17 (2) 模型求解 本模型用求解： 對圖一求解 求解結(jié)果為：471110953 所需機床花費總時間為45。 對圖二求解 求解結(jié)果為：38621141213 所需機床花費總時間為69。.18 3、總補償費最少模型 本問題主要研究如何給出一個加工順序使得總補償費最小。 (1) 目標函

13、數(shù)分析 變量說明: 表示第 個工件的完工時間（包括等待與加工兩個階段） j=1,214 u表示確定時限，題目中給的值為100 表示第 j個工件的完工時間超過了確定時限 u 表示第j 個工件的完工時間沒有超過了確定時限 u j=1,214 表示第 j個工件的補償費率 根據(jù)題目要求，只有超過了確定時限的工件才需要支付補償費用，由此可以得到目標函數(shù)為： Min （ 1.1）ix1jm0jmjw)(1413uxwmzjjjj.19 (2) 約束條件分析 根據(jù)題目給出的表中可以得知各工件之間的關系（1.2），由此也可以得到各工件完工時間之間的關系（1.3）。由分析知道工件3的完工時間為199，工件14的

14、完工時間為285，工件12的完工時間為309，工件13的完工時間為345，因此工件3以后完工的工件的完工時間都會超過確定時限 u，則 （ 為工件3以后完工的工件號，包括工件3）；而不管安排怎樣的加工順序工件4的完工時間都不會超過 u，則 ；對于工件5，它加工之前工件4、7、11、10必須完工，因此工件5的完工時間至少為108，也超過了確定時限 u，則 ；對于工件7，它最多排在工件4、9、10的后面，因此它的完工時間最多為92，不超過 u，則 ；對于工件9、10、11，它們可能超過也可能不超過確定時限，這只能根據(jù)加工的順序來得到 的值。 工件的完工時間 與工件的加工順序 之間的關系為（1.5），

15、由問題一可知。1jm04m05m07m11109,mmmjxiy.20 (3) 總補償費最少模型的建立 基于上面的分析，以（1.1）為目標函數(shù)，以（1.2）、（1.3）、（1.4）、（1.5）為約束條件建立模型1111111111111111614214114121314127114938478611510593538231yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy26926926940242093212424217417428219621711498478610510595821xxxxxxxxxxxxxxxxxxxxx)2 . 1 ()3 . 1 ()4 . 1 (1

16、111011011114131287654321mmmmmmmmmmm)(1413uxwmzjjjjMin141141)15(iiijjtyx.21 (4) 模型的求解 經(jīng)過化簡后，目標函數(shù)中只剩 下 幾個未知變量，根據(jù)lingo軟件可以得出結(jié)果?？傃a償費最小的加工順序為 ，總補償費為142.24。 根據(jù)題目給出的表中可以得知各工件之間的關系（1.2），由此也可以得到各工件完工時間之間的關系（1.3）。由分析知道工件3的完工時間為199，工件14的完工時間為285，工件12的完工時間為309，工件13的完工時間為345，因此工件3以后完工的工件的完工時間都會超過確定時限u ，則 （ 為工件3以

17、后完工的工件號，包括工件3）；而不管安排怎樣的加工順序工件4的完工時間都不會超過 u，則 ；對于工件5，它加工之前工件4、7、11、10必須完工，因此工件5的完工時間至少為108，也超過了確定時限 u，則 ；對于工件7，它最多排在工件4、9、10的后面，因此它的完工時間最多為92，不超過 ，則 ；對于工件9、10、11，它們可能超過也可能不超過確定時限，這只能根據(jù)加工的順序來得到 的值。1110986521xxxxxxxx、1jm05m07m11109mmm、.22 4.對(3)中的u進行討論。 對u進行討論，可以分為以下幾種情況 當u92時，所有工件加工時間都超過了時限，所有 （j=1,2,

18、3,5.）.由式（1.2），（.3）和mj的值。 當92=u108，此情況與u=100相同，答案為總補償費最小的加工順序為 總補償費為142.24。 當108=u174 其他約束條件相同 當174=U199 其他約束條件相同1312142168395101174, 0, 1, 1, 1, 176321mmmmm, 1, 1, 1, 11413128mmmm, 1, 1, 1, 1, 165321mmmmm, 1, 1, 15128mmm.23 當199=U209 當209=u219 其他約束條件同(1.2)(1.3) 當219=u269 其他約束條件同(1.2)(1.3) 當269=u309

19、其他約束條件同(1.2)(1.3) 當309=u345 其他約束條件同(1.2)(1.3) 當345=u,所有工件加工時間皆沒有超過時限u，此時原問題相當于問題二, 1, 0, 0, 1, 165321mmmmm, 1, 1, 01287mmm, 1, 0, 0, 1, 165321mmmmm, 1, 0, 01287mmm, 1, 0, 0, 1, 065321mmmmm, 1, 0, 01287mmm, 0, 0, 0, 0, 065321mmmmm, 1, 0, 01287mmm, 0, 0, 0, 0, 065321mmmmm, 0, 0, 01287mmm.24 5.對一般情況下上述各問題的解法進行的一些討論 對于前兩個問題總的完工時間包括各工件的等待時間之和與各工件的加工時間之和。由于各工件的加工時間之和是一定的，所以完工時間最優(yōu)問題等價于各工件等待時間總和的最優(yōu)化問題。 設第 i個工件的加工次序為 ，總的完工時間為 。 每個工件都被其后置加工工件所等待，