基于數(shù)學(xué)規(guī)劃模型的工件加工問題的求解

1、基于工件加工問題的求解摘要對于一個加工企業(yè)而言，如何在最短時間內(nèi)完成加工任務(wù),是一個企業(yè)提高競爭力和利潤的關(guān)鍵。本文就是一篇關(guān)于工件加工的排序優(yōu)化問題，在給定的數(shù)據(jù)和符合實(shí)際生產(chǎn)的條件下,合理的安排工件的加工順序,使總加工時間達(dá)到最少。對于工件加工次序模型的求解,我們可以運(yùn)用許多方法來進(jìn)行求解,但是考慮到3臺機(jī)床加工10個零件的給定一加工順序，所有零件通過機(jī)床的順序是一致的； 每個零件在各機(jī)床的加工時間已知，且每臺機(jī)床在同一時間只能加工一個零件。M2及M3工序上會出現(xiàn)等待.如果采用不同序加工，那么在M1上已加工好的零件，在M2上加工的時間會落到在M1上比其后加工的零件的后面，則其在M2上等待的

2、時間更長，同樣在M2與M3工序上也是這樣，要求加工時間最短的加工順序，就必須盡量減少零件在M2及M3工序上的等待時間，由于零件必須在它們要求的時間內(nèi)完工，即某零件在任務(wù)開始起到該零件加工完畢之間所用的總時間應(yīng)少于該零件的規(guī)定完工時間。所以要使各個零件在車間待的總時間最短,其加工零件順序固然只有一種。那么就要合理選擇加工零件的種類及其加工的次序。本題根據(jù)已知數(shù)據(jù),結(jié)合問題中的具體要求，我們引入0/1變量建立零件排序的數(shù)學(xué)規(guī)劃模型。通過lingo得出其中的最優(yōu)排序方案.使得完成這批工件加工任務(wù)所需要的總時間最省。然后我們對各個排序后的零件完成特定工序所需花費(fèi)時間進(jìn)行求和得到整個加工程序所需總時間.

3、總時間包括了各個零件在機(jī)床的加工時間以及加工其它零件的等待時間.最后，根據(jù)建立的模型求出某車間加工十個零件所需最短的時間為413分鐘,總加工時間最短的加工順序?yàn)镈-H-GIJEA-F-CB,具體結(jié)果如表1-1，12。若件加工還要滿足下面條件,零件D必須在零件E之前加工；零件H與零件J的加工必須相連；機(jī)床M3加工每個零件等待時間不能超過5分鐘,總等待時間不能超過30分鐘.那么繼續(xù)利用lingo軟件求解可以得出在此條件下最優(yōu)的順序?yàn)镚IDHJEAFCB，所需最短的時間為425分鐘，具體結(jié)果如表3-1，32.關(guān)鍵詞: 線性規(guī)劃 0/1變量 數(shù)學(xué)規(guī)劃模型 lingo軟件 一、 問題重述車間上午8：00

4、開始加工十個零件，這些零件必須依次通過機(jī)床M1，M2，M3，其加工時間如下表（單位:分鐘).M1M2M3A131520B102018C201615D8106E91413F192014G111612H16918I15127J13791。 試建立模型求出使總加工時間最短的加工順序。2。 寫出各零件加工起止時間表，求出各機(jī)床的等待時間.3。 若零件加工還要滿足下面條件，零件D必須在零件E之前加工；零件H與零件J的加工必須相連；機(jī)床M3加工每個零件等待時間不能超過5分鐘，總等待時間不能超過30分鐘.試建立模型,重新回答前面兩個問題。二、 問題分析零件在M1工序上的總加工時間是固定的,無關(guān)乎零件加工順序

5、.問題關(guān)鍵在于零件在M2以及M3工序上回出現(xiàn)等待。若采取不同加工順序，那么在M1上已加工好的零件會在M2工序上出現(xiàn)等待。同樣在M2上加工好的零件在M3工序上也會出現(xiàn)這種現(xiàn)象.要求加工時間最短的加工順序,就必須盡量減少零件在M2及M3工序上的等待時間,由于零件必須在它們要求的時間內(nèi)完工，即某零件在任務(wù)開始起到該零件加工完畢之間所用的總時間應(yīng)少于該零件的規(guī)定完工時間。若要使整個加工任務(wù)的零件總價值最大，應(yīng)選擇最優(yōu)加工零件的種類及其加工的次序。若零件D必須在零件E之前加工且零件H與零件J的加工必須相連；機(jī)床M3加工每個零件等待時間不能超過5分鐘，總等待時間不能超過30分鐘。那么就需在第一個建立好的模

6、型上附上條件，得出該條件下的最優(yōu)次序。三、 模型假設(shè)假設(shè)一:在后面的模型中,我們都假定了忽略零件在轉(zhuǎn)換工序時的運(yùn)輸時間。即將整個零件加工過程簡化為一個連續(xù)的過程,只考慮機(jī)床在加工零件時其他零件的等待時間。假設(shè)二:零件之間是相互獨(dú)立的，從生產(chǎn)的角度看,先加工一個零件并不響對后面零件的加工.不象有些流水線生產(chǎn)那樣，存在固定的加工順序。假設(shè)三：工人都是熟練工人，零件在工序上的加工時間是固定不變的,與工人的操作水平無關(guān).假設(shè)四：零件在三個工序上采有同順序加工,即在工序M1上的加工順序與在M2及M3工序上的加工順序相同。在工序M1上的加工是連續(xù)不斷的。四、 符號說明Xi （1）：i零件在車床M1加工所需

7、時間Xi (2） ：i零件在車床M2加工所需時間Xi (3) ：i零件在車床M3加工所需時間Ti （1）：i零件完成在M1加工的總時間Ti （2)：i零件完成在M2加工的總時間Ti (3):i零件完成在M3加工的總時間Ti1(2）：（i1）零件完成在M2加工的總時間（i1)Ti-1（3)（i1)零件完成在M3加工的總時間（i1）T:加工十個零件模型的總時間五、 模型的建立由問題分析可知工件i在M1工序完成的時間： Ti1=Ti-11+Ti1 （1)對于工件i在M1工序完成的時間Ti1與(i1）工件完成在M2加工的總時間Ti-12要分兩種情況分析:(1）當(dāng)Ti1Ti-12時，即i工件完成M1工序

8、的總時間大于或等于（i-1）工件完成M2工序的總時間，此時i工件不需要等待（i-1)工件而立即就進(jìn)入下一工序，因此i工件完成 M2工序的總時間表達(dá)式為: Ti2=Ti1+Xi2 （2）當(dāng)Ti1Ti-12時,即i工件完成M1工序的總時間小于或等于（i1）工件完成M2工序的總時間，此時i工件需要等待（i1)工件完成M2工序才能進(jìn)入M2加工。因此i工件 完成M2工序的總時間表達(dá)式為: Ti2=Ti-12+Xi2 綜合以上兩種情況，得到i工件完成M2工序的總時間計算公式為：-=+>Ti2=maxTi1，Ti-12+Xi2 (i1) （2）同理：對于工件i在M2工序完成的時間Ti2與（i1)工件完

9、成在M3加工的總時Ti-13,有i工件完成M3工序的總時間計算公式為: Ti3=maxTi2,Ti-13+Xi3 （i>1） （3）綜合(1）（2)（3)可得加工十件零件需要的總時間為： T=Ti3+i=210maxTi2,Ti3+Xi3 約束條件：s。t。 =1,（i=1,2,3，,10） =1，(j=1,2，3，10)六、 模型求解算法流程圖通過lingo求解，我們得出以下結(jié)論：順序號零件號M1加工時間XI(1）(分鐘）M2加工時間分XI（2）鐘)M3加工時間Xi（3 (分鐘）1D81062H169183G1116124I151275J13796E914137A1315208F192

10、0149C20161510B102018 順序號零件號完成M1工序總時間MI（1)(分鐘)完成M2工序總時間MI（2（分鐘）完成M3工序總時間MI（3）（分鐘）1D818242H2433513G3551634I5063705J6370796E7286997A851011218F1041241389C12414015510B134160178 表1-1序順間時止起號序工M1M2M3D8：008：088:088：188：18-8：24H8:088：248：24-8:338:338：51G8:24-8:358:35-8：518：519:03I8：35-8：508：519：039：03-9；10J8：

11、509：039:039:109：109:19E9:039：129：129:269:26-9：39A9：129：259:269：419：4110：01F9：25-9：449：4410:0410：0110：18C9：4410:0410:04-10：2410：24-10:35B10：0410：2610：26-10：4010：4010：58 表12工序號等待時間順序號M1M2M3D000H067G020I000J000E000A000F040C005B006 順序號零件號M1加工時間XI（1）(分鐘）M2加工時間分XI(2)鐘)M3加工時間Xi（3 （分鐘）1G1116122I151273D81064

12、H16918 5J13796E914137A1315208F1920149C20161510B102018順序號零件號完成M1工序總時間MI（1）(分鐘）完成M2工序總時間MI（2（分鐘）完成M3工序總時間MI（3）（分鐘）1G1127392I2639463D3249554H4858765J6168856E7084987A83991198F1021221369C12213815310B132158176表31序順間時止起號序工M1M2M3D8：008：118:118：278：27-8：39H8：118:268:27-8：398：398:46G8：26-8：328:398：498：49-8:55

13、I8：328:488:498:588:58-9:16J8：489:019：01-9：099：16-9：25E9:019：109：109：249：259：38A9：10-9:239：249：399：399：59F9：239:429：42-10：0210：0210：26C9:4210:0210:02-10:1810：26-10：33B10：0210:3210：3210：3810：3810：56表3-2工序號等待時間順序號M1M2M3G000I000D003H003J030E010A001F033C000B0145七、 模型評價 在本題中,對于第一題中構(gòu)建了數(shù)學(xué)規(guī)劃模型,將整批工件的加工任務(wù)拆分為在

14、最優(yōu)的排序下每個工件的實(shí)際加工情況來分析，根據(jù)各工件在加工過程中加工時間和總時間之間的聯(lián)系，尋求各工件加工總時間的具體算法。再利用Lingo軟件進(jìn)行求解模型，得出工件的最優(yōu)排序。其中邏輯嚴(yán)謹(jǐn),論證充分，算法簡潔準(zhǔn)確。有效地提高了軟件求解效率.考慮到它其實(shí)是一個有限源的“單隊(duì)-多服務(wù)臺"模型由于運(yùn)用了lingo軟件進(jìn)行求解，使模型本身就具有很大的可移植性，方便了其到m件零件n臺機(jī)床的延伸與應(yīng)用.但是我們的模型還是存在一些不足之處。模型對于無限源的情況并不適用，與現(xiàn)實(shí)生活并不相符合，只是用于理論的研究.但是總的來說,該模型對于日常生活中的工作安排問題還是具有很大的實(shí)際運(yùn)用價值,值得推廣.

15、八、 參考文獻(xiàn)1清華大學(xué)運(yùn)籌學(xué)教材編寫組。運(yùn)籌學(xué)(第三版)M清華大學(xué)出版社,20052洪文，吳本忠，Lingo4.0 for windows 優(yōu)化軟件及應(yīng)用，北京大學(xué)出版社，2001.3顏文勇，數(shù)學(xué)建模,高等教育出版社,北京，2011.64姜啟源 謝金星 葉俊等,數(shù)學(xué)模型(第四版），高等教育出版社,2010。5盧開澄。單目標(biāo)、多目標(biāo)與整數(shù)規(guī)劃M.北京：清華大學(xué)出版社，1999.6張建中.線性規(guī)劃,M。北京：科學(xué)出版社,19997 http：//view/63bfcf3410661ed9ad51f391.html九、附錄model: ！工件先M1后M2再M(fèi)3的的排序

16、問題；sets： gongjian/g1。.g10/：M1_shijian,M2_shijian,M3_shijian; shunxu/s1。.s10/：M1_time,M2_time,M3_time,M1_fintime,M2_fintime，M3_fintime; links（shunxu，gongjian)： note;endsets ！目標(biāo)函數(shù)； min=sum（shunxu(I)：M3_fintime（I）；！重新排序后各工件的M1床加工時間； for（shunxu（I）： che_time(I）=sum(gongjian（J）：M1_shijian(J)*note(I,J）； ）;

17、！ 重新排序后各工件的M2床加工時間;for（shunxu(I): zuan_time（I)=sum（gongjian（J):M2_shijian（J）note(I，J）; ）;！ 重新排序后各工件的M3床加工時間；for（shunxu(I）: xi_time（I)=sum（gongjian（J）:M3_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

18、； );!從新排序后各工件的M1完工時間；for（shunxu（I): che_fintime(I）=sum（shunxu(J）JleI:M1_time（J）); );!從新排序后各工件在M2工序的完工時間；for（shunxu（I） Igt1: M2_fintime（I)=if（M1_fintime(I)geM2_fintime（I1），M1_fintime（I），M2_fintime（I-1）)+M1_time(I）; ）； ！順序1中的M1床工序的完工時間； M2_fintime（1)=M1_fintime（1)+M2_time(1）;! 重新排序后各工件在完成M3工序的時間；for（shunxu(I)| Igt1: M3_fintime(I）=if（M2_fintime（I)ge#M3_fintime(I1)，M2_fintime(I），M3_fintime(I-1）)+M3_time（I）; );！順序1中的M3工序的完工時間;M3_fintime（1）=M2_fintime（1)+M3_time(1）； ！定義0/1變量； for（links：bin(not