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

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

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

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

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

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

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

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

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

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

10、08F1920149C20161510B102018 順序號(hào)零件號(hào)完成M1工序總時(shí)間MI(1)（分鐘）完成M2工序總時(shí)間MI(2（分鐘）完成M3工序總時(shí)間MI(3)（分鐘）1D818242H2433513G3551634I5063705J6370796E7286997A851011218F1041241389C12414015510B134160178 表1-1序順間時(shí)止起號(hào)序工M1M2M3D8:00-8:088:08-8:188：18-8:24H8：08-8:248:24-8:338:33-8:51G8:24-8:358:35-8:518:51-9:03I8:35-8:508:51-9:03

11、9:03-9;10J8:50-9:039:03-9:109:10-9:19E9:03-9:129:12-9:269:26-9:39A9:12-9:259:26-9:419:41-10:01F9:25-9:449:44-10:0410:01-10:18C9:44-10:0410:04-10:2410:24-10:35B10:04-10:2610:26-10:4010:40-10:58 表1-2工序號(hào)等待時(shí)間順序號(hào)M1M2M3D000H067G020I000J000E000A000F040C005B006 順序號(hào)零件號(hào)M1加工時(shí)間XI(1)（分鐘）M2加工時(shí)間分XI(2)鐘）M3加工時(shí)間Xi(3

12、（分鐘）1G1116122I151273D81064H16918 5J13796E914137A1315208F1920149C20161510B102018順序號(hào)零件號(hào)完成M1工序總時(shí)間MI(1)（分鐘）完成M2工序總時(shí)間MI(2（分鐘）完成M3工序總時(shí)間MI(3)（分鐘）1G1127392I2639463D3249554H4858765J6168856E7084987A83991198F1021221369C12213815310B132158176表3-1序順間時(shí)止起號(hào)序工M1M2M3D8:00-8:118:11-8:278：27-8:39H8：11-8:268:27-8:398:39-

13、8:46G8:26-8:328:39-8:498:49-8:55I8:32-8:488:49-8:588:58-9:16J8:48-9:019:01-9:099:16-9:25E9:01-9:109:10-9:249:25-9:38A9:10-9:239:24-9:399:39-9:59F9:23-9:429:42-10:0210:02-10:26C9:42-10:0210:02-10:1810:26-10:33B10:02-10:3210:32-10:3810:38-10:56表3-2工序號(hào)等待時(shí)間順序號(hào)M1M2M3G000I000D003H003J030E010A001F033C000B0

14、145七、 模型評(píng)價(jià) 在本題中，對(duì)于第一題中構(gòu)建了數(shù)學(xué)規(guī)劃模型，將整批工件的加工任務(wù)拆分為在最優(yōu)的排序下每個(gè)工件的實(shí)際加工情況來分析，根據(jù)各工件在加工過程中加工時(shí)間和總時(shí)間之間的聯(lián)系，尋求各工件加工總時(shí)間的具體算法。再利用Lingo軟件進(jìn)行求解模型，得出工件的最優(yōu)排序。其中邏輯嚴(yán)謹(jǐn)，論證充分，算法簡潔準(zhǔn)確。有效地提高了軟件求解效率。考慮到它其實(shí)是一個(gè)有限源的“單隊(duì)多服務(wù)臺(tái)”模型由于運(yùn)用了lingo軟件進(jìn)行求解，使模型本身就具有很大的可移植性，方便了其到m件零件n臺(tái)機(jī)床的延伸與應(yīng)用。但是我們的模型還是存在一些不足之處。模型對(duì)于無限源的情況并不適用，與現(xiàn)實(shí)生活并不相符合，只是用于理論的研究。但是總

15、的來說，該模型對(duì)于日常生活中的工作安排問題還是具有很大的實(shí)際運(yùn)用價(jià)值，值得推廣。八、 參考文獻(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 九、附錄model: !工件先M1后M2再M(fèi)3的的排序問題;sets: gongjia

16、n/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床加工時(shí)間; for(shunxu(I): che_time(I)=sum(gongjian(J):M1_shijian(J)*note(I,J); );! 重新排序后各工件的M2床加工時(shí)間

17、;for(shunxu(I): zuan_time(I)=sum(gongjian(J):M2_shijian(J)*note(I,J); );! 重新排序后各工件的M3床加工時(shí)間;for(shunxu(I): xi_time(I)=sum(gongjian(J):M3_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; );!從新排序后各工件的M1

18、完工時(shí)間;for(shunxu(I): che_fintime(I)=sum(shunxu(J)|J#le#I:M1_time(J); );!從新排序后各工件在M2工序的完工時(shí)間;for(shunxu(I)| I#gt#1: M2_fintime(I)=if(M1_fintime(I)#ge#M2_fintime(I-1),M1_fintime(I),M2_fintime(I-1)+M1_time(I); ); !順序1中的M1床工序的完工時(shí)間; M2_fintime(1)=M1_fintime(1)+M2_time(1);! 重新排序后各工件在完成M3工序的時(shí)間;for(shunxu(I)| I#gt#1: M3_fintime(I)=if(M2_fintime(I)#ge#M3_fintime(I-1),M2_fintime(I),M3_fintime(I-1)+M3_time(I); );!順序1中的M3工序的完工時(shí)間;M3_fintime(1)=M2_fintime(1)+M3_time(1); !定義0/1變量; for(links:bin