工件加工的排序優(yōu)化問答

湖南工學(xué)院數(shù)學(xué)建模競賽承 諾 書我們仔細(xì)閱讀了第7屆湖南工學(xué)院數(shù)學(xué)建模競賽的競賽規(guī)則。精品文檔放心下載我們完全明白，在競賽開始后參賽隊(duì)員不能以任何方式（包括電話、電子郵件、網(wǎng)上咨詢等）與本隊(duì)以外的任何人（包括指導(dǎo)教師）研究、討論與賽題有關(guān)的問題。感謝閱讀我們知道，抄襲別人的成果是違反競賽規(guī)則的,如果引用別人的成果或其他公開的資料（包括網(wǎng)上查到的資料），必須按照規(guī)定的參考文獻(xiàn)的表述方式在正文引用處和參考文獻(xiàn)中明確列出。精品文檔放心下載我們鄭重承諾，嚴(yán)格遵守競賽規(guī)則，以保證競賽的公正、公平性。如有違反競賽規(guī)則的行為，我們愿意承擔(dān)由此引起的一切后果。精品文檔放心下載我們的參賽報(bào)名號為：參賽隊(duì)員 (簽名)：隊(duì)員1：***隊(duì)員2：***隊(duì)員3：***湖南工學(xué)院數(shù)學(xué)建模競賽編號專用頁參賽隊(duì)伍的參賽號碼：（請各個(gè)參賽隊(duì)提前填寫好）：競賽統(tǒng)一編號（由競賽組委會送至評委團(tuán)前編號）：競賽評閱編號（由競賽評委團(tuán)評閱前進(jìn)行編號）：湖南工學(xué)院數(shù)學(xué)建模競賽工件加工的排序優(yōu)化問題摘要眾所周知，對于一個(gè)加工企業(yè)而言，如何在最短時(shí)間內(nèi)完成加工任務(wù)，是一個(gè)企業(yè)提高競爭力和利潤的關(guān)鍵。本文就是一篇關(guān)于工件加工的排序優(yōu)化問題，即在給定的數(shù)據(jù)和做出符合實(shí)際生產(chǎn)的條件下，合理的安排工件的加工順序，使加工的效率或所獲得的利潤等指標(biāo)達(dá)到最大值。如：問題一第一問問在所有工件必須且只需加工一次，如何合理安排加工順序，使得完成這批工件加工任務(wù)所需的總時(shí)間最??；第二問問如何安排加工順序能使加工零件的總價(jià)值最大。因?yàn)楣ぜ庸ぶ挥许樞蚝图庸づc否，所以我們引入了一個(gè)0-1變量表示加工工件的順序和工件的種類，運(yùn)用lingo編程求出該變量，即可得到在不同情況下加工順序。然后對結(jié)果進(jìn)行分析，因?yàn)橛?jì)算出的結(jié)果唯一的（實(shí)際可能不唯一，如，第一題第二問）。這是因?yàn)楫?dāng)前一個(gè)工件的完工時(shí)間大于排序后后一個(gè)工件的累計(jì)加工時(shí)間時(shí)，兩者互換加工順序均可行。問題二三四是在問題一上的推廣,因此我們運(yùn)用前面方法將模型符號化，再歸納出i種工件，每種工件需要j部機(jī)床的情況，在解決方法上只需要在lingo程序中的工件順序集里加入相應(yīng)的屬性，便解出0-1變量，然后轉(zhuǎn)換成順序，問題就解決了。精品文檔放心下載關(guān)鍵詞：0-1變量、lingo、排序問題-1-問題重述計(jì)劃排序問題中的車間作業(yè)問題，研究n個(gè)工件在m臺機(jī)器上有序的加工問題，每個(gè)工件都有完工的日期（DD，Duedate）,加工的時(shí)間（PT，Processingtime）和工件的價(jià)值（VAL，Valueifjobisselected）.車間作業(yè)計(jì)劃研究一個(gè)工廠生產(chǎn)工序的計(jì)劃和安排，需要計(jì)劃與合理安排各個(gè)工件在這些機(jī)器上加工的先后次序，即擬訂加工工序，通過各個(gè)工件在各種機(jī)器上加工次序的合理安排，使得完成這批工件加工任務(wù)所需的總時(shí)間最省（注：總時(shí)間即為各個(gè)零件的加工時(shí)間和加工其他零件時(shí)它們等待時(shí)間之和）或要求整個(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表11、不考慮工件的完工時(shí)間和工件的價(jià)值，為該工廠安排工件加工的次序，使得完成這批工件加工任務(wù)所需的總時(shí)間最省。建立數(shù)學(xué)模型并給出相應(yīng)的算法。精品文檔放心下載2、由于工件必須在它們要求的時(shí)間內(nèi)完工，按照表1的數(shù)據(jù)，為該工廠安排選擇加工工件的種類及加工的次序，使得整個(gè)選擇加工的工件價(jià)值最大。建立數(shù)學(xué)模型并給出相應(yīng)的算法。精品文檔放心下載（二）如果這12種工件都要求先在車床上加工，然后再在鉆床上加工（即工件在鉆床加工之前必須先在車床上加工過），每種機(jī)器一次只能加工一種工件，這12種工件加工所需時(shí)間如表2所示：精品文檔放心下載-2-工件車床加工時(shí)間（h）鉆床加工時(shí)間(h)12.8423.21.331.21.8442.252.7360.94.572.51.783.32.591.74.5102.52.5113.63.8124.71.9表2為該工廠安排工件加工的次序，使得完成這批工件加工任務(wù)所需的總時(shí)間最省。建立數(shù)學(xué)模型并給出相應(yīng)的算法。謝謝閱讀（三）如果這12種工件都要求先在車床上加工，然后再在鉆床上加工，最后再在銑床上加工，每種機(jī)器一次只能加工一種工件，這12種工件加工所需時(shí)間如表3所示：精品文檔放心下載工件車床加工時(shí)間（h）鉆床加工時(shí)間(h)銑床加工時(shí)間(h)12.84323.21.3442.21.352.731.860.94.5291.74.51表3為該工廠安排工件加工的次序，使得完成這批工件加工任務(wù)所需的總時(shí)間最省。建立數(shù)學(xué)模型并給出相應(yīng)的算法。謝謝閱讀（四）對于上述問題你做出的數(shù)學(xué)模型和相應(yīng)的算法給出評價(jià)。并將模型推廣到n個(gè)工件在m臺機(jī)器上加工的一般的工件排序問題，給出你的想法和解決問題的思路。精品文檔放心下載-3-問題分析問題一：第一問，題目只要求完成這批工件加工任務(wù)所需的總時(shí)間最省，不考慮完工時(shí)間和工件價(jià)值，為此引入一個(gè)12×12的0-1變量，下標(biāo)分別表示工件序號和加工順序序號。如：y(1,7)=1表示工件1加工順序?yàn)?。利用約束條件和目標(biāo)函數(shù)求出此變量，就能得到題目要求的工件加工次序。第二問，題目要求考慮完工時(shí)間并使利潤最大，在第一問的基礎(chǔ)上將目標(biāo)函數(shù)中的總時(shí)間改為總利潤，并加上完工時(shí)間的約束，將0-1變量解出，就能得到需要加工的工件序號和順序。謝謝閱讀問題二：在問題一第一問的基礎(chǔ)上，將加工次數(shù)增為兩次，因?yàn)楣ぜ仨毾冉?jīng)過車床加工，才能進(jìn)行鉆床的加工，所以只要求出工件車床的加工順序就是整個(gè)加工順序。因此仍然可以用一個(gè)12×12的0-1變量來解決此問題，然后用lingo編程解出此變量。感謝閱讀問題三四：在問題一二基礎(chǔ)上進(jìn)一步推廣，因此我們運(yùn)用前面方法將模型符號化，然后歸納出一般的式子得到第三四問的解。感謝閱讀符號說明yijaijminjirjdifjjujtiWP

0/1變量i工件的車床加工時(shí)間在最優(yōu)排列下第j次在車床加工的時(shí)間i工件的鉆床加工時(shí)間在最優(yōu)排列下第j次在鉆床加工的時(shí)間i工件的銑床加工時(shí)間在最優(yōu)排列下第j次在銑床加工的時(shí)間第i種工件在車床的完工時(shí)間感謝閱讀在最優(yōu)排列下第j種工件在車床工件的完工時(shí)間在最優(yōu)排列下第j種工件在完成鉆床序的總時(shí)間感謝閱讀在最優(yōu)排列下第j種工件在完成銑床序的總時(shí)間i工件在從最優(yōu)排列下車床加工所用的總時(shí)間完成這批工件加工任務(wù)所需的總時(shí)間感謝閱讀工件總價(jià)值-4-模型假設(shè)4.1.不考慮的完工時(shí)間和工件的價(jià)值，安排工件加工的次序，使得完成這批工件加工感謝閱讀任務(wù)所需的總時(shí)間最省。4.2.工件在轉(zhuǎn)換工序時(shí)所需的運(yùn)輸時(shí)間為零。4.3.機(jī)器加工完一種工件后，能及時(shí)另外一種零件。感謝閱讀4.4.工件和機(jī)器在加工過程中不發(fā)生意外。模型的建立與求解5.1.對于問題一1）設(shè)t為i工件實(shí)際完工時(shí)間，所以完成這批工件的總時(shí)間為Z=∑12t精品文檔放心下載i ii=1而加工i工件在最優(yōu)排列下所用的總時(shí)間t=b +b=b +b +b=b+b+…+b精品文檔放心下載i i?1 i i?2 i?1 i 1 2 i謝謝閱讀ti=∑ibjj=112工件，第i工件加工順序在1到12之間，即∑12yij=1。感謝閱讀=1加工順序?yàn)閖是，一定有一個(gè)工件i，即∑12yij=1。精品文檔放心下載=1最優(yōu)排列下第j次加工的時(shí)間bj=∑12yijai感謝閱讀=1因此:問題1）的數(shù)學(xué)模型為目標(biāo)函數(shù):12minZ=∑tii=1約束條件:ti=∑bijj=112=112=1∑y，∑yijiji=1j=1bj=∑12yijai=1對此數(shù)學(xué)模型用lingo編程，運(yùn)行程序即得完成這批工件的總時(shí)間和加工順序，程序見附件-程序一謝謝閱讀-5-2）設(shè)P為工件的總價(jià)值，ej在最優(yōu)排列下第j種工件的價(jià)值，那么有：maxP=∑12e精品文檔放心下載jj=1因?yàn)椴灰竺恳环N工件都加工，所以∑12yij≤1，∑12yij≤1感謝閱讀i=1 j=1因?yàn)榈诙柺窃诘谝粏柕幕A(chǔ)上，因此需要滿足第一問的約束bj=∑12yijai，ej=∑12yijci謝謝閱讀i=1 i=1完工時(shí)間約束fj=∑12yijdi=1i工件在從最優(yōu)排列下加工所用的總時(shí)間需要小于完工時(shí)間，故t≤f（i=j）。感謝閱讀j綜上所述可得問題2）的數(shù)學(xué)模型為目標(biāo)函數(shù)：maxP=∑12ejj=1約束條件：1212≤1∑y≤1，∑yijiji=1j=1b1212=∑ya，e=∑ycjijijijii=1i=1f12，t≤f(i=j)=∑ydjijiij=1對此數(shù)學(xué)模型用lingo編程，運(yùn)行程序即得完成這批工件的總價(jià)值以及相應(yīng)的總時(shí)間和加工順序，程序見附錄-程序二謝謝閱讀5.2.對于問題二問題二要求完成任務(wù)使總時(shí)間最少，根據(jù)題意總時(shí)間為加工時(shí)間加上等待時(shí)間，所以有如下式子感謝閱讀完成這批工件加工任務(wù)所需的總時(shí)間最少minW=∑12sj感謝閱讀j=1其中sj最優(yōu)排列下第j種工件在完成鉆工序的總時(shí)間精品文檔放心下載{t+nt≥ssj=si+jnit≤js?1s1=t1+n1j?1jij?1ti為i工件在從最優(yōu)排列下車床加工所用的總時(shí)間ti=∑ibj精品文檔放心下載j=1-6-ni為i工件在從最優(yōu)排列下車床加工所用的總時(shí)間nj=∑1yijmi謝謝閱讀n=1mi為i工件的鉆床加工時(shí)間，根據(jù)前面第一問可知還有如下約束感謝閱讀bj=∑12yijai，∑12yij=1，∑12yij=1感謝閱讀i=1 i=1 j=1因此問題二的數(shù)學(xué)模型可以表述為目標(biāo)函數(shù)：12minW=∑sjj=1約束條件：{t+nt≥ssj=si+jnit≤js?1s1=t1+n1j?1jij?1ti=∑ibjnj=∑12yijmi感謝閱讀j=1 i=1bj=∑12yijai，∑12yij=1，∑12yij=1謝謝閱讀i=1 i=1 j=1對此數(shù)學(xué)模型用lingo編程，運(yùn)行程序即得完成這批工件的最少總時(shí)間和加工順序，程序見附件-程序三。感謝閱讀5.3.對于問題三這是在問題一二上的推廣，我們?nèi)匀话凑盏谝粏柾茝V到第二問的方法，將第二問推廣到第三問，設(shè)uj最優(yōu)排列下第j種工件在完成銑床序的總時(shí)間感謝閱讀那么最少的總時(shí)間minW=∑12uj ··························································(1)感謝閱讀=1在最優(yōu)排列下第j次在車床加工的時(shí)間b12··································(2)=∑yajijii=1在最優(yōu)排列下第j次在鉆床加工的時(shí)間nj12····································(3)=∑yijmii=1在最優(yōu)排列下第j次在銑床加工的時(shí)間r12···································(4)=∑yqjijii=112工件，第i工件加工順序在1到12之間，即∑12yij=1·······················(5)謝謝閱讀=1加工順序?yàn)閖是，一定有一個(gè)工件i，即∑12yij=1···································(6)感謝閱讀=1-7-最優(yōu)排列下第j次加工的時(shí)間bj=∑12yijai···············································(7)精品文檔放心下載=1i··························(8)為i工件在從最優(yōu)排列下車床加工所用的總時(shí)間t=∑bjij=1{t+nt≥ssj最優(yōu)排列下第j種工件在完成鉆工序的總時(shí)間sj=si+jnit≤js?1··(9)j?1jij?1s1=t1+n1·······················································································(10){si+rjsi≥uj?1·········································································uju+rs≤u(11)j?1jij?1u=s+r1·······················································································(12)11綜上所述問題三的模型如下：目標(biāo)函數(shù)：minW=∑12ujj=1約束條件：上述（2）（3）（4）（5）（6）（7）（8（9）（10）（11）（12）謝謝閱讀對上述模型用lingo編程，程序見附錄—程序四，運(yùn)行程序就能得到總時(shí)間最少的工件精品文檔放心下載加工順序，以及總時(shí)間5.4.對于問題四為了方便模型的符號化，我們假設(shè)i工件在車床M加工所需時(shí)間為X；在鉆床上M加感謝閱讀1 i1 2工所需時(shí)間為X；在銑床M上加工所需要的時(shí)間為X；在后續(xù)的各工序M中加工所i23i3j需要的時(shí)間設(shè)為X；下表中內(nèi)容表示i工件從任務(wù)開始時(shí)刻起到完成M道工序止所需i,jj要的總時(shí)間M，根據(jù)題意可以得到下表ij車床M1鉆床M2銑床M3…Mj10+XM+XM+X…M+x1111121213i,j-11j2M+XMax(M，M)+XMax(M,M)+X…Max(M,M)+X11212112222213232,j-11j2j3M+XMax(M,M)+XMax(M,M)+X…Max(M,M)+X21313122323223333,j-12j3j…………iM+XMax(M,M)+XMax(M,M)+X…Max(M,M)+Xi-1,1i1i1i-1,2i2i2i-1,3i3i,j-1i-1,ji,j4-1-8-由表4-1可知問題（二）的數(shù)學(xué)模型也可以表述為Min=M12)+X}；+∑{Max(M,M12i1i-1,2i2i=2=M+X121112問題（三）的數(shù)學(xué)模型也可以表述為Min=M12,M)+X}；+∑{Max(M13i2i-1,3i3i=2M=M+X；131213歸納以上算式，推廣到i個(gè)工件j部機(jī)床的工件排序問題，得出問題（四）的數(shù)學(xué)模型為精品文檔放心下載Min=Mi,M)+X}；+∑{Max(M1ji,j-1i-1,jiji=2M=M+X1j1,j-11,j-1-9-結(jié)果分析6.1.對問題一的結(jié)果分析1）運(yùn)行程序一可得工件的加工順序如下:加工序號工件加工時(shí)間b完成時(shí)間tii160.90.9231.22.1391.73.84102.56.3572.58.8652.711.5712.814.3823.217.5983.320.810113.624.4114428.412124.733.1總計(jì)：171.9由上表可知加工順序?yàn)?-3-9-10-7-5-1-2-8-11-4-12，此時(shí)加工總時(shí)間最少,為171.9謝謝閱讀2）運(yùn)行程序二分析可得下表工件序號加工順序加工時(shí)間累計(jì)加工時(shí)間完工時(shí)間工件價(jià)值911.71.777122.84.5981234.79.21118341.210.41516752.512.917171062.515.41812670.916.3222048420.32331193.623.92558103.327.23311總價(jià)值：117由上表可看出加工順序?yàn)?-1-12-3-7-10-6-4-11-8,分析該表，我們發(fā)現(xiàn)只要前一個(gè)工謝謝閱讀件的完工時(shí)間大于后一個(gè)工件的總加工時(shí)間，兩者可以互換加工順序，不影響最大利潤精品文檔放心下載（總時(shí)間可能不同），具體可互換的結(jié)果如下圖9 1 12 3 78 11 4 6 10最大的總價(jià)值為117-10-6.2.對問題二的結(jié)果分析運(yùn)行程序三分析可得到下表完成車床工完成鉆床工序總順序工件車床加工時(shí)間鉆床加工時(shí)間序總時(shí)間號號xi1Xi2M時(shí)間Mi2i15.46.738.4410.2552.7310.513.56102.52.51316783.32.516.318.8891.74.51823.39124.71.922.725.21012.8425.529.511442.229.531.712113.63.833.136.9總時(shí)間：225.6表2-1由上表可知，最優(yōu)的工件排序?yàn)?－2－7－3－5－10－8－9－12－1－4－11，完成這批工件加工任務(wù)所需的最省總時(shí)間為225.6。精品文檔放心下載6.3.對問題三的結(jié)果分析運(yùn)行程序四，分析結(jié)果，便可以得到下表：車床加鉆床加銑床加完成車完成鉆完成銑順序號工件號工時(shí)間工時(shí)間工時(shí)間床工序床工序床工序總時(shí)間總時(shí)間總時(shí)間X(1)X(1)X(1)iiiM(1)M(2)M(3)iii1.235.5291.74.5323.21.348.610.514.1560.94.529.51517614.216.917.7716.719.420.5852.731.819.422.424.2922.725.2261012.84325.529.532.511442.21.329.531.733.81233.136.938.2總時(shí)間：247.83-1-11-從表3-1可以看出，最優(yōu)的工件排序?yàn)?－9－2－7－6－12－10－5－8－1－4－11；完成這批工件加工任務(wù)所需的最省總時(shí)間為247.8感謝閱讀模型評價(jià)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)，論證充分，算法簡潔準(zhǔn)確。有效地提高了軟件求解效率。感謝閱讀2）由于在模型求解中利用了Lingo軟件，大大簡化了編程工作，且模型本身結(jié)合軟件的使用就具有很強(qiáng)的可移植性，便于模型的推廣。列如在推廣到m工件n部機(jī)床的情況，只需在程序中的工件，順序集里加入相應(yīng)的屬性；在程序段中加入對應(yīng)的算法和約束條件就可以完全替換從而解決問題了。精品文檔放心下載參考文獻(xiàn)姜啟源等，數(shù)學(xué)模型（第三版），高等教育出版社，2003。謝謝閱讀洪文吳本忠，Lingo4.0forwindows最優(yōu)化軟件及應(yīng)用，北京大學(xué)出版社，2001。謝謝閱讀/Forums/1/268/ShowPost.aspx#268謝謝閱讀-12-附錄1程序一：model:sets:gongjian/1..12/:a;shunxu/1..12/:b,t;links(shunxu,gongjian):y;endsetsdata:a=2.83.21.242.70.92.53.31.72.53.64.7;精品文檔放心下載enddatamin=@sum(shunxu:t);@for(shunxu(j):b(j)=@sum(gongjian(i):a(i)*y(i,j)));謝謝閱讀@for(shunxu(i):t(i)=@sum(shunxu(j)|j#le#i:b(j)));精品文檔放心下載@for(shunxu(i):@sum(gongjian(j):y(i,j))=1);謝謝閱讀@for(shunxu(j):@sum(gongjian(i):y(i,j))=1);精品文檔放心下載@for(links:@bin(y));end程序二：model:sets:gongjian/1..12/:a,d,c;shunxu/1..12/:b,f,e;links(shunxu,gongjian):y;endsetsdata:a=2.83.21.242.70.92.53.31.72.53.64.7;d=97.51523102217337182511;c=841637201711712518;感謝閱讀enddatamax=@sum(shunxu:e);@for(shunxu(i):b(i)=@sum(gongjian(j):a(j)*y(i,j)));謝謝閱讀@for(shunxu(i):f(i)=@sum(gongjian(j):d(j)*y(i,j)));謝謝閱讀@for(shunxu(i):e(i)=@sum(gongjian(j):c(j)*y(i,j)));精品文檔放心下載@for(shunxu(i):@sum(gongjian(j):y(i,j))<=1);感謝閱讀@for(shunxu(j):@sum(gongjian(i):y(i,j))<=1);感謝閱讀@for(shunxu(i):@sum(shunxu(j)|j#le#i:b(j))<=f(i));精品文檔放心下載@for(links:@bin(y));end-13-程序三model:sets:gongjian/1..12/:a,m;shunxu/1..12/:b,n,t,s;links(shunxu,gongjian):y;endsetsdata:a=2.83.21.242.70.92.53.31.72.53.64.7;m=41.31.82.234.51.72.54.52.53.81.9;enddata精品文檔放心下載min=@sum(shunxu(i):s(i));@for(shunxu(i):b(i)=@sum(gongjian(j):a(j)*y(i,j)));精品文檔放心下載@for(shunxu(i):n(i)=@sum(gongjian(j):m(j)*y(i,j)))