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

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

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

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

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

6、型上附上條件，得出該條件下的最優次序。三、 模型假設假設一:在后面的模型中,我們都假定了忽略零件在轉換工序時的運輸時間。即將整個零件加工過程簡化為一個連續的過程,只考慮機床在加工零件時其他零件的等待時間。假設二:零件之間是相互獨立的，從生產的角度看,先加工一個零件并不響對后面零件的加工.不象有些流水線生產那樣，存在固定的加工順序。假設三：工人都是熟練工人，零件在工序上的加工時間是固定不變的,與工人的操作水平無關.假設四：零件在三個工序上采有同順序加工,即在工序M1上的加工順序與在M2及M3工序上的加工順序相同。在工序M1上的加工是連續不斷的。四、 符號說明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）當Ti1Ti-12時，即i工件完成M1工序

8、的總時間大于或等于（i-1）工件完成M2工序的總時間，此時i工件不需要等待（i-1)工件而立即就進入下一工序，因此i工件完成 M2工序的總時間表達式為: Ti2=Ti1+Xi2 （2）當Ti1Ti-12時,即i工件完成M1工序的總時間小于或等于（i1）工件完成M2工序的總時間，此時i工件需要等待（i1)工件完成M2工序才能進入M2加工。因此i工件 完成M2工序的總時間表達式為: 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求解，我們得出以下結論：順序號零件號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七、 模型評價 在本題中,對于第一題中構建了數學規劃模型,將整批工件的加工任務拆分為在

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

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

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 ！目標函數； 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