[精彩]數(shù)學(xué)建模c題論文(工件加工排序)

1、數(shù)學(xué)建模競賽試題：C題：工件加工排序方案排序問題中的車間作業(yè)問題，研究n個工件在m臺機器上有序的加工問題，每個工件都有完工的日期DD，Due date, 加工的時間PT，Processing time和工件的價值VAL，Value if job is selected. 現(xiàn)研究一個工廠生產(chǎn)工序的方案和安排，需要方案與合理安排各個工件在這些機器上加工的先后次序，即擬訂加工工序，通過各個工件在各種機器上加工次序的合理安排，使得完成這批工件加工任務(wù)所需的總時間最省注：總時間即為各個零件的加工時間和加工其他零件時它們等待時間之和或要求整個選擇加工的工件價值最大。有一個工廠現(xiàn)在有12種工件編號為工件1，

2、工件2，工件12需要在車床，鉆床，銑床幾種不同的設(shè)備上加工?？紤]下面的工件加工的排序問題：(一) 這12種工件都要求在車床上加工，車床一次只能加工一種工件，這12種工件加工所需時間，每個工件的完工時間和每個工件的價值如表1所示：工件加工時間h完工時間(h)工件價值198243151644233510762220717178331197710181211255121118表11) 不考慮工件的完工時間和工件的價值，為該工廠安排工件加工的次序，使得完成這批工件加工任務(wù)所需的總時間最省。建立數(shù)學(xué)模型并給出相應(yīng)的算法。2) 由于工件必須在它們要求的時間內(nèi)完工，按照表1的數(shù)據(jù)，為該工廠安排選擇加工工件的

3、種類及加工的次序，使得整個選擇加工的工件價值最大。建立數(shù)學(xué)模型并給出相應(yīng)的算法。(二) 如果這12種工件都要求先在車床上加工，然后再在鉆床上加工即工件在鉆床加工之前必須先在車床上加工過，每種機器一次只能加工一種工件，這12種工件加工所需時間如表2所示： 工件車床加工時間h鉆床加工時間(h)142344536789101112 表2為該工廠安排工件加工的次序，使得完成這批工件加工任務(wù)所需的總時間最省。建立數(shù)學(xué)模型并給出相應(yīng)的算法。 (三) 如果這12種工件都要求先在車床上加工，然后再在鉆床上加工，最后再在銑床上加工，每種機器一次只能加工一種工件，這12種工件加工所需時間如表三所示：工件車床加工時

4、間h鉆床加工時間(h)銑床加工時間(h)1432134453627891101112表3為該工廠安排工件加工的次序，使得完成這批工件加工任務(wù)所需的總時間最省。建立數(shù)學(xué)模型并給出相應(yīng)的算法。(四) 對于上述問題你做出的數(shù)學(xué)模型和相應(yīng)的算法給出評價。并將模型推廣到n個工件在m臺機器上加工的一般的工件排序問題，給出你的想法和解決問題的思路。解題正文：C題：工件加工排序建模小組成員： AP0308306 陳運標(biāo) AP0308307鄧風(fēng)儀 AP0206311 黃深泉 摘要此題根據(jù)數(shù)據(jù)，結(jié)合問題中的具體要求，我們引入0/1變量建立工件排序的數(shù)學(xué)規(guī)劃模型。借助Lingo軟件進(jìn)行求解運算，得出其中的最優(yōu)排序方

5、案。使得完成這批工件加工任務(wù)所需要的總時間最省。在這里，我們通過對各個工件排序后完成某項特定工序所需總時間進(jìn)行求和得到整個加工任務(wù)所需要的總時間。而各工件的總時間包括其機床加工時間和加工其他零件時的等待時間。模型的假設(shè)：在后面的模型中，我們都假定了忽略工件在轉(zhuǎn)換工序時的運輸時間。即將整個工件加工過程簡化為一個連續(xù)的過程，只考慮機床在加工工件時其他工件的等待時間。模型的建立：我們的思路是引入0/1變量對工件進(jìn)行動態(tài)排序，根據(jù)問題要求得出排序后的目標(biāo)函數(shù)即數(shù)學(xué)模型。根據(jù)題目的約束條件，利用Lingo軟件算出模型的最優(yōu)解，從而獲得工件的最優(yōu)排序。問題一題目要求：12種工件都要求在車床上加工，車床一次

6、只能加工一種工件。設(shè) i 工件車床加工時間為A ,規(guī)定完工時間為B,工件價值為C1） 不考慮工件的完工時間和工件的價值，安排工件加工的次序，使得完成這批工件加工任務(wù)所需的總時間最省。分析：引入0/1變量，利用目標(biāo)函數(shù)最優(yōu)化工件排序。 設(shè)為i工件實際完工時間，所以完成這批工件的總時間為T=,而 =A+A=A+A+A=A+A+=因此: 建立問題1的目標(biāo)函數(shù)即數(shù)學(xué)模型為Min= 定義x，xx為0/1變量，為原始工件序列下i工件的車床加工時間；所以A=xa+xa+.+xaA=xa+xa+.+xa . A=xa+xa+.+xax+x+.+x=1x+x+.+x=1.x+x+.+x=1x+x+x+x+x=1

7、x+x+x+x+x=1.x+x+x+x+x=1Lingo程序：附wenti(1).lg4文件model: !不考慮完工時間和工件價值的排序問題;sets: gongjian/g1.g12/:shijian; !屬性為原始排序下各個工件的機床加工時間; shunxu/s1.s12/:time,fin_time; !屬性為重新排序后各工件的機床加工時間和完成車工序的時間; links(shunxu,gongjian): note;endsets !目標(biāo)函數(shù)：求各個工件的加工總時間和最小; min=sum(shunxu(I):fin_time(I); !重新排序后各工件的機床加工時間; for(sh

8、unxu(J): time(J)=sum(gongjian(I):shijian(I)*note(I,J); ); !排序后各個工件的加工總時間; for(shunxu(I): fin_time(I)=sum(shunxu(J)|J#le#I:time(J); ); !每個順序位只能有一個工件; for(shunxu(I): sum(gongjian(J): note(I,J)=1; ); !每個工件只能排在一個順序位上; for(gongjian(J): sum(shunxu(I): note(I,J)=1; ); !定義0/1變量; for(links:bin(note);data:!輸出

9、數(shù)據(jù)到Excel文檔;OLE(D:liebiao.XLS)=time,fin_time; !原始排序下各個工件的機床加工時間; shijian= 2.8,3.2,1.2,4,2.7,0.9,2.5,3.3,1.7,2.5,3.6,4.7;enddataend結(jié)果數(shù)據(jù)：工件加工時間完成時間T6391075128114412總計： 表1-1 所以最優(yōu)排序是639107512811412完成這批工件加工任務(wù)所需的最省總時間2) 分析：由于工件必須在它們要求的時間內(nèi)完工，即某工件在任務(wù)開始起到該工件加工完畢之間所用的總時間應(yīng)少于該工件的規(guī)定完工時間。所以要使整個加工任務(wù)的工件總價值最大，必須合理選擇加

10、工工件的種類及其加工的次序。 引入0-1變量,假設(shè)選擇i工件加工,那么記Y=0;工件的排序算法同問題1，但約束條件有所不同。在此題中，12種工件不一定都可以入選到最優(yōu)加工序列中即目標(biāo)排序中可能出現(xiàn)工件空缺，所以 (=1, 2, .12)，且 (=1, 2, .12)，為0-1變量。用Lingo進(jìn)行編程，工件集參加原始排序下車床加工時間，完工時間和工件價值屬性；順序集參加重新排序后車床加工時間，完工時間和工件價值屬性；因此該模型為：目標(biāo)函數(shù): Max= 在排序算法及程序中已隱含有工件選擇： (=1, 2, .12)， (=1, 2, .12)完工時間約束： (=1, 2, .12)Lingo程序

11、：wenti(2).lg4文件model: !考慮完工時間和工件價值的排序問題;sets: gongjian/g1.g12/:shijian,endtime,gj_value; ! 屬性為原始排序下各個工件的機床加工時間，完工時間，工件價值; shunxu/s1.s12/:time,overtime,fin_value; ! 屬性為重新排序后各個工件的機床加工時間，完工時間，工件價值; links(shunxu,gongjian): note;endsets !目標(biāo)函數(shù); max=sum(shunxu(I):fin_value(I);!從新排序后各工件的機床加工時間可能為零，即表示未選中工件;

12、 for(shunxu(I): time(I)=sum(gongjian(J):shijian(J)*note(I,J);!從新排序后各工件的完工時間可能為零，即表示未選中工件;for(shunxu(I): overtime(I)=sum(gongjian(J):endtime(J)*note(I,J); );!從新排序后各工件的工件價值可能為零，即表示未選中工件;for(shunxu(I): fin_value(I)=sum(gongjian(J):gj_value(J)*note(I,J); ); !每個順序位只能有一個工件或者沒有工件; for(shunxu(I): sum(gongji

13、an(J): note(I,J)=1); !每個工件只能排在一個順序位上; for(gongjian(J):sum(shunxu(I): note(I,J)=1); !各工件的完工時間約束; for(shunxu(I): sum(shunxu(J)|J#le#I:time(J)=overtime(I); ); !定義0/1變量; for(links:bin(note);data: !原始排序下各個工件的機床加工時間; shijian= 2.8,3.2,1.2,4,2.7,0.9,2.5,3.3,1.7,2.5,3.6,4.7; !原始排序下各個工件的完工時間; endtime=9,7.5,15

14、,23,10,22,17,33,7,18,25,11; !原始排序下各個工件的工件價值; gj_value=8,4,16,3,7,20,17,11,7,12,5,18;enddataend模型結(jié)果：導(dǎo)出列表：工件順序車床加工時間規(guī)定的完工時間各工件價值000000 198 577 121118 101812 31516 62220 71717 24233 11255 83311總價值：117 表1-2 由上表可知，最優(yōu)方案是選擇工件1512103672118，并按此順序進(jìn)行加工。從而獲得最大的工件總價值為117.關(guān)于問題二，三，四分析：問題二要求：如果這12種工件都要求先在車床上加工，然后再在

15、鉆床上加工即工件在鉆床加工之前必須先在車床上加工過，每種機器一次只能加工一種工件，求工件加工的最優(yōu)排序，使得完成這批工件加工任務(wù)所需的總時間最省。根據(jù)總時間的定義，某工件從任務(wù)開始時刻起到完成鉆床工序止所需要的總時間包括該工件完成車工序的時間，等待上一個工件加工完的時間即從該工件在車床加工完畢時刻起到其上一個工件在鉆床上加工完畢這一段時間，該工件在鉆床上加工的時間。我們假設(shè)工件在車床加工所需時間為，在鉆床上加工所需時間為；工件完成在車床加工的總時間為；工件完成在鉆床加工的總時間為，。這里要分兩種情況進(jìn)行分析： 1).當(dāng)時，即工件完成車工序的總時間大于或等于工件完成鉆工序的總時間，此時工件不需要

16、等待工件而立即就進(jìn)入鉆工序，因此工件完成鉆床工序的總時間表達(dá)式為+; 2).當(dāng)時，即工件完成車工序的總時間小于或等于工件完成鉆工序的總時間，此時工件需要等待工件完成鉆床工序才能進(jìn)入鉆床加工。因此工件完成鉆床工序的總時間表達(dá)式為+。 綜合以上兩種情況，得到工件完成鉆床工序的總時間計算公式為 Max，+ 同理，對于問題三，我們也可以得到類似的計算公式.，下面是以列表的形式將這一推導(dǎo)公式推廣到工件個工序的情況：假設(shè)i工件在車床加工所需時間為；在鉆床上加工所需時間為；在銑床上加工所需要的時間為；在后續(xù)的各工序中加工所需要的時間設(shè)為；下表中內(nèi)容表示i工件從任務(wù)開始時刻起到完成道工序止所需要的總時間 工序

17、 順序 工件順序車床鉆床銑床 加工1+ +2+Max，+Max，+ Max，+3Max，+Max，+ Max，+ iMax，+Max，+ Max，+表2-1模型的建立： 根據(jù)表2-1，問題二中要求的完成加工任務(wù)的最省總時間即為在最優(yōu)排序下各工件完成鉆床加工工序的總時間之和。即建立問題二的數(shù)學(xué)模型為Max=+ ，+；這里 +；Lingo編程：附錄1wenti(3).lg4文件同理，問題三中要求的完成加工任務(wù)的最省總時間即為在最優(yōu)排序下各工件完成銑床加工工序的總時間之和。 建立問題三的數(shù)學(xué)模型為Max=+ ，+；這里 +；Lingo編程：附錄2wenti(4).lg4文件歸納以上算式，推廣到i個工

18、件j部機床的工件排序問題， 建立問題四的數(shù)學(xué)模型為Max=+ ，+；這里 +；Lingo編程：略 模型結(jié)果：問題二運算后導(dǎo)出列表：順序號工件號車床加工時間 鉆床加工時間完成車床工序總時間完成鉆床工序總時間 1 33 2 6 3 7 4 2 5 1013 6 531316 7 9 8 44 9 822 10 14 11 1133 12 1235總時間：表2-2 由上表可知，最優(yōu)的工件排序為367210594811112，完成這批工件加工任務(wù)所需的最省總時間為224.8。問題三運算后導(dǎo)出列表：順序號 工件號車床加工時間 鉆床加工時間銑床加工時間 1 3 2 92 3 11 4 10 5 7 6 9

19、1 7 21 8 53 9 8 10 143 11 44 12 12 表2-3順序號工件號完成車床工序總時間完成鉆床工序總時間完成銑床工序總時間 1 33 2 9 3 11 4 1012 5 7 6 9 7 2 8 5 9 8 10 1 11 4 12 1235總時間： 表2-4 從軟件的運行情況可知，最優(yōu)的工件排序為391110792581412；完成這批工件加工任務(wù)所需的最省總時間模型評價，改良方法，推廣1 在此題的解答過程中所建立的數(shù)學(xué)規(guī)劃模型中，我們始終圍繞一種化整為零的數(shù)學(xué)思想，將整批工件的加工任務(wù)拆分為在最優(yōu)的排序下每個工件的實際加工情況來分析，根據(jù)各工件在加工過程中加工時間和總時

20、間之間的聯(lián)系，尋求各工件加工總時間的具體算法。再利用Lingo軟件進(jìn)行求解模型，得出工件的最優(yōu)排序。其中邏輯嚴(yán)謹(jǐn)，論證充分，算法簡潔準(zhǔn)確。有效地提高了軟件求解效率。2 由于在模型求解中利用了Lingo軟件，大大簡化了編程工作，且模型本身結(jié)合軟件的使用就具有很強的可移植性，便于模型的推廣。列如在推廣到m工件n部機床的情況，只需在程序中的工件，順序集里參加相應(yīng)的屬性；在程序段中參加對應(yīng)的算法和約束條件就可以完全替換從而解決問題了。參考資料：1 姜啟源 等，數(shù)學(xué)模型第三版，高等教育出版社，2003。2 洪文 吳本忠，Lingo4.0 for windows 最優(yōu)化軟件及應(yīng)用，北京大學(xué)出版社，2001

21、。34 :/ /Forums/1/268/ShowPost.aspx#268 附錄一：model: !工件先車后鉆的排序問題;sets: gongjian/g1.g12/:che_shijian,zuan_shijian; shunxu/s1.s12/:che_time,zuan_time,che_fintime,zuan_fintime; links(shunxu,gongjian): note;endsets !目標(biāo)函數(shù); min=sum(shunxu(I):zuan_fintime(I);!從新排序后各工件的車床加工時間; for(shunxu(I): che_ti

22、me(I)=sum(gongjian(J):che_shijian(J)*note(I,J); );!從新排序后各工件的鉆床加工時間;for(shunxu(I): zuan_time(I)=sum(gongjian(J):zuan_shijian(J)*note(I,J); ); !每個順序位只能有一個工件; for(shunxu(I): sum(gongjian(J): note(I,J)=1; ); !每個工件只能排在一個順序位上; for(gongjian(J): sum(shunxu(I): note(I,J)=1; );!從新排序后各工件在完成車工序的總時間;for(shunxu(I

23、): che_fintime(I)=sum(shunxu(J)|J#le#I:che_time(J); );!從新排序后各工件在完成鉆工序的總時間;for(shunxu(I)| I#gt#1:zuan_fintime(I)=if(che_fintime(I)#ge#zuan_fintime(I-1),che_fintime(I),zuan_fintime(I-1)+zuan_time(I); ); !順序1中的工件在完成鉆工序的總時間; zuan_fintime(1)=che_fintime(1)+zuan_time(1); !定義0/1變量; for(links:bin(note); dat

24、a: !原始排序下各個工件的車床加工時間; che_shijian= 2.8,3.2,1.2,4,2.7,0.9,2.5,3.3,1.7,2.5,3.6,4.7; !原始排序下各個工件的鉆床加工時間; zuan_shijian=4,1.3,1.8,2.2,3,4.5,1.7,2.5,4.5,2.5,3.8,1.9; enddataend附錄二：model: !工件先車后鉆再銑的的排序問題;sets: gongjian/g1.g12/:che_shijian,zuan_shijian,xi_shijian; shunxu/s1.s12/:che_time,zuan_time,xi_time,ch

25、e_fintime,zuan_fintime,xi_fintime; links(shunxu,gongjian): note;endsets !目標(biāo)函數(shù); min=sum(shunxu(I):xi_fintime(I);!從新排序后各工件的車床加工時間; for(shunxu(I): che_time(I)=sum(gongjian(J):che_shijian(J)*note(I,J); );!從新排序后各工件的鉆床加工時間;for(shunxu(I): zuan_time(I)=sum(gongjian(J):zuan_shijian(J)*note(I,J); );!從新排序后各工件的銑床加工時間;for(shunxu(I): xi_time(I)=sum(gongjian(J):xi_shijian(J)*note(I,J); ); !每個順序位只能有一個工件; for(shunxu(I): sum(gongjian(J): note(I,J)=1; ); !每個工件只能排在一個順序位上; for(gongjian(J): sum(shunxu(I): note(I,J)=1; );!從新排