數(shù)學(xué)建模C題論文(工件加工排序)

1、命題人： 鄒祥福 審批人： 試卷分類（A卷或B卷） A 數(shù)學(xué)建模競賽試題：C題：工件加工排序計(jì)劃排序問題中的車間作業(yè)問題，研究n個(gè)工件在m臺(tái)機(jī)器上有序的加工問題，每個(gè)工件都有完工的日期（DD，Due date）, 加工的時(shí)間（PT，Processing time）和工件的價(jià)值（VAL，Value if job is selected）. 現(xiàn)研究一個(gè)工廠生產(chǎn)工序的計(jì)劃和安排，需要計(jì)劃與合理安排各個(gè)工件在這些機(jī)器上加工的先后次序，即擬訂加工工序，通過各個(gè)工件在各種機(jī)器上加工次序的合理安排，使得完成這批工件加工任務(wù)所需的總時(shí)間最省（注：總時(shí)間即為各個(gè)零件的加工時(shí)間和加工其他零件時(shí)它們等待時(shí)間之和）或

2、要求整個(gè)選擇加工的工件價(jià)值最大。有一個(gè)工廠現(xiàn)在有12種工件（編號為工件1，工件2，工件12）需要在車床，鉆床，銑床幾種不同的設(shè)備上加工?？紤]下面的工件加工的排序問題：(一) 這12種工件都要求在車床上加工，車床一次只能加工一種工件，這12種工件加工所需時(shí)間，每個(gè)工件的完工時(shí)間和每個(gè)工件的價(jià)值如表（1）所示：工件加工時(shí)間（h）完工時(shí)間(h)工件價(jià)值12.89823.27.5431.215164423352.710760.9222072.5171783.3331191.777102.51812113.6255124.71118表（1）1) 不考慮工件的完工時(shí)間和工件的價(jià)值，為該工廠安排工件加工的次

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

4、3.63.8124.71.9 表（2）為該工廠安排工件加工的次序，使得完成這批工件加工任務(wù)所需的總時(shí)間最省。建立數(shù)學(xué)模型并給出相應(yīng)的算法。 (三) 如果這12種工件都要求先在車床上加工，然后再在鉆床上加工，最后再在銑床上加工，每種機(jī)器一次只能加工一種工件，這12種工件加工所需時(shí)間如表（三）所示：工件車床加工時(shí)間（h）鉆床加工時(shí)間(h)銑床加工時(shí)間(h)12.84323.21.3131.21.82.5442.21.352.731.860.94.5272.51.73.683.32.50.891.74.51102.52.51.1113.60.91.3124.71.90.7表（3）為該工廠安排工件加工

5、的次序，使得完成這批工件加工任務(wù)所需的總時(shí)間最省。建立數(shù)學(xué)模型并給出相應(yīng)的算法。(四) 對于上述問題你做出的數(shù)學(xué)模型和相應(yīng)的算法給出評價(jià)。并將模型推廣到n個(gè)工件在m臺(tái)機(jī)器上加工的一般的工件排序問題，給出你的想法和解決問題的思路。解題正文：C題：工件加工排序（建模小組成員： AP0308306 陳運(yùn)標(biāo) AP0308307鄧風(fēng)儀 AP0206311 黃深泉） 摘要本題根據(jù)已知數(shù)據(jù)，結(jié)合問題中的具體要求，我們引入0/1變量建立工件排序的數(shù)學(xué)規(guī)劃模型。借助Lingo軟件進(jìn)行求解運(yùn)算，得出其中的最優(yōu)排序方案。使得完成這批工件加工任務(wù)所需要的總時(shí)間最省。在這里，我們通過對各個(gè)工件（排序后）完成某項(xiàng)特定工序

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

7、考慮工件的完工時(shí)間和工件的價(jià)值，安排工件加工的次序，使得完成這批工件加工任務(wù)所需的總時(shí)間最省。分析：引入0/1變量，利用目標(biāo)函數(shù)最優(yōu)化工件排序。 設(shè)為i工件實(shí)際完工時(shí)間，所以完成這批工件的總時(shí)間為T=,而 =A+A=A+A+A=A+A+=因此: 建立問題（1）的目標(biāo)函數(shù)即數(shù)學(xué)模型為Min= 定義x，xx為0/1變量，為原始工件序列下i工件的車床加工時(shí)間；所以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=1x+x+x+x+x=1.x+x+x+x+x=1Lingo程序：（附wenti(1).

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

9、(I)*note(I,J); ); !排序后各個(gè)工件的加工總時(shí)間; for(shunxu(I): fin_time(I)=sum(shunxu(J)|J#le#I:time(J); ); !每個(gè)順序位只能有一個(gè)工件; for(shunxu(I): sum(gongjian(J): note(I,J)=1; ); !每個(gè)工件只能排在一個(gè)順序位上; for(gongjian(J): sum(shunxu(I): note(I,J)=1; ); !定義0/1變量; for(links:bin(note);data:!輸出數(shù)據(jù)到Excel文檔;OLE('D:liebiao.XLS')=

10、time,fin_time; !原始排序下各個(gè)工件的機(jī)床加工時(shí)間; 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ù)：工件加工時(shí)間完成時(shí)間T60.90.931.22.191.73.8102.56.372.58.852.711.512.814.323.217.583.320.8113.624.44428.4124.733.1總計(jì)：171.9 表1-1 所以最優(yōu)排序是639107512811412完成這批工件加工任務(wù)所需的最省總時(shí)間為171.92) 分析：由于工件必須在它們要求的時(shí)間內(nèi)完工，即某工件在任務(wù)開始

11、起到該工件加工完畢之間所用的總時(shí)間應(yīng)少于該工件的規(guī)定完工時(shí)間。所以要使整個(gè)加工任務(wù)的工件總價(jià)值最大，必須合理選擇加工工件的種類及其加工的次序。 引入0-1變量,若選擇i工件加工,則記Y=1.否則記Y=0;工件的排序算法同問題1），但約束條件有所不同。在本題中，12種工件不一定都可以入選到最優(yōu)加工序列中（即目標(biāo)排序中可能出現(xiàn)工件空缺），所以 (=1, 2, .12)，且 (=1, 2, .12)，為0-1變量。用Lingo進(jìn)行編程，工件集加入原始排序下車床加工時(shí)間，完工時(shí)間和工件價(jià)值屬性；順序集加入重新排序后車床加工時(shí)間，完工時(shí)間和工件價(jià)值屬性；因此該模型為：目標(biāo)函數(shù): Max= （在排序算法及

12、程序中已隱含有）工件選擇： (=1, 2, .12)， (=1, 2, .12)完工時(shí)間約束： (=1, 2, .12)Lingo程序：（wenti(2).lg4文件）model: !考慮完工時(shí)間和工件價(jià)值的排序問題;sets: gongjian/g1.g12/:shijian,endtime,gj_value; ! 屬性為原始排序下各個(gè)工件的機(jī)床加工時(shí)間，完工時(shí)間，工件價(jià)值; shunxu/s1.s12/:time,overtime,fin_value; ! 屬性為重新排序后各個(gè)工件的機(jī)床加工時(shí)間，完工時(shí)間，工件價(jià)值; links(shunxu,gongjian): note;endsets

13、 !目標(biāo)函數(shù); max=sum(shunxu(I):fin_value(I);!從新排序后各工件的機(jī)床加工時(shí)間（可能為零，即表示未選中工件）; for(shunxu(I): time(I)=sum(gongjian(J):shijian(J)*note(I,J);!從新排序后各工件的完工時(shí)間（可能為零，即表示未選中工件）;for(shunxu(I): overtime(I)=sum(gongjian(J):endtime(J)*note(I,J); );!從新排序后各工件的工件價(jià)值（可能為零，即表示未選中工件）;for(shunxu(I): fin_value(I)=sum(gongjian(

14、J):gj_value(J)*note(I,J); ); !每個(gè)順序位只能有一個(gè)工件或者沒有工件; for(shunxu(I): sum(gongjian(J): note(I,J)<=1); !每個(gè)工件只能排在一個(gè)順序位上; for(gongjian(J):sum(shunxu(I): note(I,J)<=1); !各工件的完工時(shí)間約束; for(shunxu(I): sum(shunxu(J)|J#le#I:time(J)<=overtime(I); ); !定義0/1變量; for(links:bin(note);data: !原始排序下各個(gè)工件的機(jī)床加工時(shí)間; sh

15、ijian= 2.8,3.2,1.2,4,2.7,0.9,2.5,3.3,1.7,2.5,3.6,4.7; !原始排序下各個(gè)工件的完工時(shí)間; endtime=9,7.5,15,23,10,22,17,33,7,18,25,11; !原始排序下各個(gè)工件的工件價(jià)值; gj_value=8,4,16,3,7,20,17,11,7,12,5,18;enddataend模型結(jié)果：導(dǎo)出列表：工件順序車床加工時(shí)間規(guī)定的完工時(shí)間各工件價(jià)值000000 12.898 51.777 124.71118 102.51812 31.21516 60.92220 72.51717 24233 113.6255 83.3

16、3311總價(jià)值：117 表1-2 由上表可知，最優(yōu)方案是選擇工件1512103672118，并按此順序進(jìn)行加工。從而獲得最大的工件總價(jià)值為117.關(guān)于問題（二），（三），（四）分析：問題（二）要求：如果這12種工件都要求先在車床上加工，然后再在鉆床上加工（即工件在鉆床加工之前必須先在車床上加工過），每種機(jī)器一次只能加工一種工件，求工件加工的最優(yōu)排序，使得完成這批工件加工任務(wù)所需的總時(shí)間最省。根據(jù)總時(shí)間的定義，某工件從任務(wù)開始時(shí)刻起到完成鉆床工序止所需要的總時(shí)間包括該工件完成車工序的時(shí)間，等待上一個(gè)工件加工完的時(shí)間（即從該工件在車床加工完畢時(shí)刻起到其上一個(gè)工件在鉆床上加工完畢這一段時(shí)間），該工件

17、在鉆床上加工的時(shí)間。我們假設(shè)工件在車床加工所需時(shí)間為，在鉆床上加工所需時(shí)間為；工件完成在車床加工的總時(shí)間為；（）工件完成在鉆床加工的總時(shí)間為，（）。這里要分兩種情況進(jìn)行分析： 1).當(dāng)時(shí)，即工件完成車工序的總時(shí)間大于或等于（）工件完成鉆工序的總時(shí)間，此時(shí)工件不需要等待（）工件而立即就進(jìn)入鉆工序，因此工件完成鉆床工序的總時(shí)間表達(dá)式為+; 2).當(dāng)時(shí)，即工件完成車工序的總時(shí)間小于或等于（）工件完成鉆工序的總時(shí)間，此時(shí)工件需要等待（）工件完成鉆床工序才能進(jìn)入鉆床加工。因此工件完成鉆床工序的總時(shí)間表達(dá)式為+。 綜合以上兩種情況，得到工件完成鉆床工序的總時(shí)間計(jì)算公式為 Max（，）+ （） 同理，對于問

18、題（三），我們也可以得到類似的計(jì)算公式.，下面是以列表的形式將這一推導(dǎo)公式推廣到工件個(gè)工序的情況：假設(shè)i工件在車床加工所需時(shí)間為；在鉆床上加工所需時(shí)間為；在銑床上加工所需要的時(shí)間為；在后續(xù)的各工序（）中加工所需要的時(shí)間設(shè)為；下表中內(nèi)容表示i工件從任務(wù)開始時(shí)刻起到完成道工序止所需要的總時(shí)間 工序 順序 工件順序車床鉆床銑床 加工1+ +2+Max（，）+Max（，）+ Max（，）+3Max（，）+Max（，）+ Max（，）+ iMax（，）+Max（，）+ Max（，）+表2-1模型的建立： 根據(jù)表2-1，問題（二）中要求的完成加工任務(wù)的最省總時(shí)間即為在最優(yōu)排序下各工件完成鉆床加工工序的總時(shí)

19、間之和。即建立問題（二）的數(shù)學(xué)模型為Max=+ （，）+；這里 +；Lingo編程：附錄1（wenti(3).lg4）文件同理，問題（三）中要求的完成加工任務(wù)的最省總時(shí)間即為在最優(yōu)排序下各工件完成銑床加工工序的總時(shí)間之和。 建立問題（三）的數(shù)學(xué)模型為Max=+ （，）+；這里 +；Lingo編程：附錄2（wenti(4).lg4）文件歸納以上算式，推廣到i個(gè)工件j部機(jī)床的工件排序問題， 建立問題（四）的數(shù)學(xué)模型為Max=+ （，）+；這里 +；Lingo編程：（略） 模型結(jié)果：問題（二）運(yùn)算后導(dǎo)出列表：順序號工件號車床加工時(shí)間 鉆床加工時(shí)間完成車床工序總時(shí)間完成鉆床工序總時(shí)間 1 31.21.

20、81.23 2 60.94.52.17.5 3 72.51.74.69.2 4 23.21.37.810.5 5 102.52.510.313 6 52.731316 7 91.74.514.720.5 8 442.218.722.7 9 83.32.52225.2 10 12.8424.829.2 11 113.63.828.433 12 124.71.933.135總時(shí)間：224.8表2-2 由上表可知，最優(yōu)的工件排序?yàn)?67210594811112，完成這批工件加工任務(wù)所需的最省總時(shí)間為224.8。問題（三）運(yùn)算后導(dǎo)出列表：順序號 工件號車床加工時(shí)間 鉆床加工時(shí)間銑床加工時(shí)間 1 31.

21、21.82.5 2 90.94.52 3 113.60.91.3 4 102.52.51.1 5 72.51.73.6 6 91.74.51 7 23.21.31 8 52.731.8 9 83.32.50.8 10 12.843 11 442.21.3 12 124.71.90.7 表2-3順序號工件號完成車床工序總時(shí)間完成鉆床工序總時(shí)間完成銑床工序總時(shí)間 1 31.235.5 2 92.17.59.5 3 115.78.410.8 4 108.210.912 5 710.712.616.2 6 912.417.118.1 7 215.618.419.4 8 518.321.423.2 9

22、821.624.124.9 10 124.428.431.4 11 428.430.632.7 12 1233.13535.7總時(shí)間：239.4 表2-4 從軟件的運(yùn)行情況可知，最優(yōu)的工件排序?yàn)?91110792581412；完成這批工件加工任務(wù)所需的最省總時(shí)間為239.4模型評價(jià)，改進(jìn)方法，推廣1 在本題的解答過程中所建立的數(shù)學(xué)規(guī)劃模型中，我們始終圍繞一種化整為零的數(shù)學(xué)思想，將整批工件的加工任務(wù)拆分為在最優(yōu)的排序下每個(gè)工件的實(shí)際加工情況來分析，根據(jù)各工件在加工過程中加工時(shí)間和總時(shí)間之間的聯(lián)系，尋求各工件加工總時(shí)間的具體算法。再利用Lingo軟件進(jìn)行求解模型，得出工件的最優(yōu)排序。其中邏輯嚴(yán)謹(jǐn)，

23、論證充分，算法簡潔準(zhǔn)確。有效地提高了軟件求解效率。2 由于在模型求解中利用了Lingo軟件，大大簡化了編程工作，且模型本身結(jié)合軟件的使用就具有很強(qiáng)的可移植性，便于模型的推廣。列如在推廣到m工件n部機(jī)床的情況，只需在程序中的工件，順序集里加入相應(yīng)的屬性；在程序段中加入對應(yīng)的算法和約束條件就可以完全替換從而解決問題了。參考資料：1 姜啟源 等，數(shù)學(xué)模型（第三版），高等教育出版社，2003。2 洪文 吳本忠，Lingo4.0 for windows 最優(yōu)化軟件及應(yīng)用，北京大學(xué)出版社，2001。34 附錄一：model: !工件先車后鉆的排序問題;sets: gongjian/g1.g12/:che_

24、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);!從新排序后各工件的車床加工時(shí)間; for(shunxu(I): che_time(I)=sum(gongjian(J):che_shijian(J)*note(I,J); );!從新排序后各工件的鉆床加工時(shí)間;for(shunxu(I): zuan_time(I)=sum(go

25、ngjian(J):zuan_shijian(J)*note(I,J); ); !每個(gè)順序位只能有一個(gè)工件; for(shunxu(I): sum(gongjian(J): note(I,J)=1; ); !每個(gè)工件只能排在一個(gè)順序位上; for(gongjian(J): sum(shunxu(I): note(I,J)=1; );!從新排序后各工件在完成車工序的總時(shí)間;for(shunxu(I): che_fintime(I)=sum(shunxu(J)|J#le#I:che_time(J); );!從新排序后各工件在完成鉆工序的總時(shí)間;for(shunxu(I)| I#gt#1:zuan_

26、fintime(I)=if(che_fintime(I)#ge#zuan_fintime(I-1),che_fintime(I),zuan_fintime(I-1)+zuan_time(I); ); !順序1中的工件在完成鉆工序的總時(shí)間; zuan_fintime(1)=che_fintime(1)+zuan_time(1); !定義0/1變量; for(links:bin(note); data: !原始排序下各個(gè)工件的車床加工時(shí)間; 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; !原始排序下各個(gè)工件的鉆床加工時(shí)間;

27、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,che_fintime,zuan_fintime,xi_fintime; links(shunxu,gongjian): note;endsets !目標(biāo)函數(shù); min=sum(shunxu(I):xi_f

28、intime(I);!從新排序后各工件的車床加工時(shí)間; for(shunxu(I): che_time(I)=sum(gongjian(J):che_shijian(J)*note(I,J); );!從新排序后各工件的鉆床加工時(shí)間;for(shunxu(I): zuan_time(I)=sum(gongjian(J):zuan_shijian(J)*note(I,J); );!從新排序后各工件的銑床加工時(shí)間;for(shunxu(I): xi_time(I)=sum(gongjian(J):xi_shijian(J)*note(I,J); ); !每個(gè)順序位只能有一個(gè)工件; for(shunxu(I): sum(gongjian(J): note(I,J)=1;