流水線調(diào)度優(yōu)化模型--武大數(shù)模選拔

1、精選優(yōu)質(zhì)文檔-傾情為你奉上題目：流水線車間調(diào)度優(yōu)化模型【摘 要】通過對問題的分析，流水線車間調(diào)度問題可以歸結(jié)為一個整數(shù)規(guī)劃問題，本論文中根據(jù)題目所給的條件以及實際情況依次建立起兩個模型。在滿足加工時間最短的前提下，基于對問題約束條件不同的翻譯得到兩個模型從而得到不同的生產(chǎn)順序，為決策者提供了更多的生產(chǎn)方案。聯(lián)系生產(chǎn)生活實際情況，放松加工工件必須遵循相對順序不變這一約束條件，提出模型的改進方向。模型一，根據(jù)題目要求即每個工件的加工順序為彎折焊接裝配且每臺機器每次只能處理一個加工件。構(gòu)造一個每行每列只含一個1其余元素為0的矩陣，通過矩陣乘積實現(xiàn)對原來工件工序耗時的行變換，整個過程相當于遍歷。建立線

2、性規(guī)劃模型，利用LINGO軟件求解。結(jié)果為當加工順序為413652時，用時最短為35min，利用Excel作出甘特圖使整個生產(chǎn)安排流程更加清晰，引入時間利用率的概念即加工工件的時間占開啟時間的百分比，得到在加工順序為413652時機器一（彎折）機器二（焊接）機器三（裝配）的時間利用率依次為，從而可從機器負載評價加工過程。模型二，將每臺機器每次只能處理一個加工件這一約束條件翻譯為一旦開始順序確定，則后續(xù)工序仍按原順序進行。引入01變量表示兩工件生產(chǎn)順序，建立01規(guī)劃模型，利用LINGO軟件求解。結(jié)果為當加工順序為136452時，用時最短為35min。利用甘特圖對結(jié)果進行分析與檢驗，得到3臺機器的

3、時間利用效率分別為，為決策者選擇方案提供了更多的參考指標。討論本文所建模型的優(yōu)點和缺點，橫向的對比兩個模型。在工件數(shù)目相對較多（在十這一數(shù)量級上）的情況下選擇模型一求解，LINGO可以在短時間內(nèi)給出答案；在數(shù)據(jù)量較少的情況下運用模型二求解，因為它模型建立過程簡單易懂，編程容易。但是對于工件數(shù)目處于百個數(shù)量級時，兩種模型均無法在短時間內(nèi)得到答案，需要建立新的模型，設(shè)計新的算法求解此類大規(guī)模排序問題。針對模型的部分缺點提出優(yōu)化改進方案，改變初始工件加工各工序耗時矩陣，即動態(tài)設(shè)立初始點以彌補LINGO軟件只能輸出一組最優(yōu)解的局限，得出當加工順序為316542，416532，341652，146532

4、時也能使加工時間最短為35min，提供了更多的可選擇方案。聯(lián)系實際生產(chǎn)，根據(jù)各機器單位時間的工作成本不同，可以建立多目標規(guī)劃模型，既要使總的時間最短又要使整個加工過程機器的總成本最低，同時實現(xiàn)時間和成本的最優(yōu)化?？梢詾闆Q策者提供更實用的生產(chǎn)工件加工順序規(guī)劃。文末簡述了模型的推廣與應(yīng)用。將此線性整數(shù)規(guī)劃模型稍作修改就可以運用到安排面試人員的面試順序、單機調(diào)度最優(yōu)化、公交車的調(diào)度等問題。枚舉的思想可以用到一些小規(guī)模的排序問題中，利用優(yōu)化軟件也可以快速求得其最優(yōu)解?？梢詾閷嶋H生產(chǎn)生活解決問題帶來極大地便利?！娟P(guān)鍵詞】流水線調(diào)度 線性整數(shù)規(guī)劃模型 甘特圖 LINGO 1問題重述21世紀是一個注重效率和

5、時間利用率的時代，在工業(yè)生產(chǎn)和經(jīng)濟發(fā)展中，我們竭盡全力去節(jié)省時間，在有限的時間內(nèi)盡可能多的創(chuàng)造財富。所以，根據(jù)實際的生產(chǎn)需要及生產(chǎn)要求合理的安排生產(chǎn)的順序尤為重要。生產(chǎn)調(diào)度即將分好批的生產(chǎn)任務(wù)落實到加工設(shè)備上，以使某代價最小，所謂的某代價最小也即優(yōu)化目標。所謂的流水線車間調(diào)度即有一組功能不同的機床，待加工的零件包含多道工序，每道工序在一臺機床上加工，所有零件的加工順序相同。在本問題中，共有3個機床，6種待加工零件，每種零件需要經(jīng)過3道工序，每臺機床同一時間只能加工一種工件，確定了開始時的加工順序隨后的加工順序不會改變。建立適當?shù)臄?shù)學模型，確定加工件的先后順序，使得加工所有用件用時最短。6種工件

6、加工工序需時（分鐘）見下表1：表1：6種加工工件各工序耗時表（min）加工件 1 2 3 4 5 6 彎折 3 6 3 5 5 7焊接 5 4 2 4 4 5裝配 5 2 4 6 3 6 2問題分析與假設(shè)2.1問題分析此問題屬于規(guī)劃問題，目的是給出使加工時間最短的工件加工順序。已知每個加工件在各個加工工序所需要的時間，并且規(guī)定每臺機器每次只能處理一個加工件，每個加工件按照給定處理步驟即彎折焊接裝配依次進行，要求出加工所有工件所用的最短時間。要讓總的加工時間最短，每種機器工作時間是連續(xù)的，即中途不允許在有生產(chǎn)任務(wù)有做相應(yīng)任務(wù)的機器空閑時，機器不加工?？偟臅r間就是第一臺機器開始工作到第三臺機器停止

7、工作的時間。通過分析知道此問題是一個整數(shù)規(guī)劃問題，準確的說是一個線性規(guī)劃中的二次分配問題。根據(jù)題目要求忽略次要影響因素，將主要因素翻譯成數(shù)學語言，利用已有的數(shù)學知識，建立相應(yīng)的模型。忽略了機器加工的準備時間以及機器可能出現(xiàn)故障等突發(fā)條件，以工件加工順序隨初始順序而確定，各工件按一定順序加工為主要約束條件，建立使得加工總用時最少的整數(shù)規(guī)劃模型。2.2模型假設(shè)(1) 機器正常工作，不出現(xiàn)故障,中途也不需要進行維護；(2)機器加工效率不隨時間改變，即加工件的先后順序不影響各個工序的用時； (3) 每種金屬管件都要經(jīng)過三個階段即彎折、焊接、裝配，先后順序不允許打亂，兩工序之間可以等一段時間也可以不隔時

8、間；(4)每種機器每次只能處理一個加工件，等待下一臺機器處理時，按原順序進行不允許排在后面的加工件“插隊”；（5） 所有機器準備時間（忽略）為零，即所有生產(chǎn)件立即進入加工；（6） 無緊急件及其他突發(fā)情況。3符號說明符號含義：工件總數(shù)加工工序數(shù)第I個加工的工件第J道工序所需要的時間第I個加工的工件開始第J道工序的時刻號加工件在第j個工序需要的時間號加工件開始第j道工序的時刻引入的01變量，總用時加工第道工序的機器的時間利用效率 4模型一的建立與求解4.1模型一的建立此問題明顯是根據(jù)生產(chǎn)順序的排列組合，求最小的生產(chǎn)時間的問題。一共有六個工件共有720種可能的排列順序。構(gòu)建一個的0-1矩陣，每行每列

9、僅有一個元素為1，其余元素為0，共有720種矩陣。我們假設(shè)最優(yōu)的方案已經(jīng)找到，即第個生產(chǎn)的工件工件號為i。要求最小的加工時間，即第一臺機器開始工作到最后一臺機器停止工作的時間最短。轉(zhuǎn)化為最后一個加工的工件開始第三道工序的時刻與第三道工序耗時之和即（4.1）又由假設(shè)可知每個工件依次經(jīng)過彎折焊接裝配，所以對于第I個加工的工件前一個工序的結(jié)束時間必須在不晚于下一道工序的開始時間即（4.2）又每個機器每次只能加工一個工件故第I+1個工件必須在第I個工件的J工序完成后才能進行J工序，（4.3）因為已經(jīng)假設(shè)最優(yōu)的方案已經(jīng)找到，是對應(yīng)最優(yōu)方案的工序加工耗時，必須對原來的按工件序號組成的耗時矩陣變換為按加工順

10、序組成的耗時矩陣。引入的0-1矩陣，每行每列僅有一個元素為1，其余元素為0。兩矩陣相乘得到的新矩陣，例如，若最優(yōu)解對應(yīng)的，說明工件3排在第一個加工。第一行即第一個加工工件各加工工序的耗時，以此類推第6行是第6個加工工件各工序的耗時。綜上，得到整數(shù)規(guī)劃模型如下：；注：為了表達簡便，在約束條件中，將取到6，取到3，但在為3時越界，在為6時越界，此時只需在編程的過程中對分分別約束即可。4.2模型的求解將目標函數(shù)及約束條件輸入到Lingo中運行求解，可以得到結(jié)果（程序語句以及輸出結(jié)果參見附錄），可得加工順序為為341256。為了更清晰的說明生產(chǎn)流程，由求解結(jié)果作出各工件開始、完成各工序的時間表41表4

11、1 工件i開始及完成工序J的時間生產(chǎn)工序J工件號開始1（彎折）完成彎折開始2(焊接)完成焊接開始3（裝配）裝配完成40 55 991515 89 14 15 203 8 1117 19 20 246 11 1819 24 24 305 18 2325 29 30 332 23 2929 33 33 354.3模型檢驗與分析根據(jù)表41利用Excel作出甘特圖如圖4一1圖4一1 工件生產(chǎn)順序甘特圖即加工順序為413652時，最短加工時間為35min。負責彎折的機器029min一直工作，未出現(xiàn)空載情況；負責焊接的機器59min、 1724min、2533min工作，從開始到停止共9min空載；負責裝

12、配的機器935min一直工作。利用率=機器1（負責彎折）機器2（負責焊接）機器3（負責裝配）在一個生產(chǎn)周期時間利用率可以看出此加工順序使三個機器的空載時間不均衡，機器二空載時間過長。此模型模擬遍歷的過程，沒有對工件不允許插隊進行限制，而且各機器的時間利用效率不均衡，為了求解出更加合理的生產(chǎn)順序，建立模型二。5模型二的建立與求解5.1模型的建立模型一采取遍歷的思想方法來表示工件之間的絕對加工順序，還有一種方法就是對兩個工件的加工順序依次進行比較，引入01變量來表示任意兩個工件的相對加工順序，根據(jù)他們相對的加工順序求得總的加工順序。首先每個工件都要滿足按照彎折焊接裝配的工序生產(chǎn)。即前一個工序結(jié)束后

13、才能進行后一個工序。故（5.1）其次工件之間的加工順序不改變，引入01變量，若按一種工件3道工序全部加工完成，另一工件才開始加工，完成6種工件需要94，故在之前加工時，（5.2）在之后加工時， （5.3）由(5.2)(5.3)得（5.4） （5.4）表示，也有可能在它之前加工。對于任何一個工件，其加工結(jié)束的時間應(yīng)不超過總時間，即（5.5）綜上所述，得到一個以加工時間最短為目標的整數(shù)規(guī)劃模型s.t.5.2模型的求解將目標函數(shù)及約束條件輸入到Lingo11中運行求解，可以得到結(jié)果（程序語句以及輸出結(jié)果參見附錄），即加工順序為136452時加工時間最短為35min。根據(jù)結(jié)果做出號工件開始第j道工序和

14、完成第j道工序的時刻表51表51號工件開始第j道工序和完成第j道工序的時刻生產(chǎn)工序工件號1（彎折）完成彎折2(焊接)完成焊接3（裝配）裝配完成10 33 8813223 2929 33 33 353 3 68 10 13 174 13 1818 22 24 305 18 2323 27 30 336 6 1313 18 18 245.3模型的檢驗與分析為了更加直觀的表示整個生產(chǎn)流程，畫出甘特圖。如圖5-2從甘特圖中可以清晰的看出加工順序為136452，總時間為35min。工序1即彎折的條形圖，負責彎折的機器從0-29min一直工作，沒有出現(xiàn)空載情況；工序2的條形圖，負責焊接的機器3-10min

15、工作，10-13min空載，13-33min工作；工序3的條形圖，負責裝配的機器從8-17min工作，17-18min空載，18-35min工作。機器1（負責彎折）機器2（負責焊接）機器3（負責裝配）在一個生產(chǎn)周期時間利用率在此情況下，三個機器的利用率相差不大即機器負荷相對平衡。得到了比較滿意的生產(chǎn)順序安排。6模型的評價本文建立了兩個模型。模型一建立了線性整數(shù)規(guī)劃模型，模擬遍歷的過程，解決了各生產(chǎn)工件任務(wù)量相等時完成任務(wù)的最短時間以及對應(yīng)的加工順序。模型二引入01變量表示兩工件相對加工順序，建立了01規(guī)劃模型，求得使加工過程最短的加工順序。6.1模型的優(yōu)點（1） 采用較為成熟的數(shù)學理論建立模型

16、，所建模型簡單，通俗易懂。（2） 為求得更為合理的生產(chǎn)工作調(diào)度表，建立多個模型，對結(jié)果進行比較，有較強的實用性。（3） 模型的計算采用LINGO軟件，算法簡便,編程實現(xiàn)簡單；可信度較高，便于推廣。（4） 甘特圖的使用使生產(chǎn)過程更加清晰，各機器工作時間，各工件加工進度一目了然。（5） 機器時間利用效率概念的引入從整體上評價了不同生產(chǎn)順序的利弊。6.2模型的缺點（1）模型雖然綜合考慮了很多因素，但為了建立模型，理想化了許多影響因素，具有一定的局限性，得到的最優(yōu)方案可能與實際有一定的出入。（2）模型只考慮了時間最短，沒有考慮成本最低，有可能每個機器運轉(zhuǎn)時單位時間花費不同，模型結(jié)果與實際有一定差距。（

17、3）所建立的模型對工件個數(shù)少的流水線調(diào)度比較適用，一旦工件種類增加至100個及以上可能很難得到全局的最優(yōu)解。（4）LINGO軟件求解優(yōu)化問題時，只能輸出一組最優(yōu)解，其他最優(yōu)解不能輸出。即使得到了最短時間是35min，但是不能得到所有使與之對應(yīng)的加工順序。7 模型的優(yōu)化與模型改進針對上述提出的不足之處，可進一步對模型進行優(yōu)化，如：1. 對于模型1針對LINGO不能輸出所有最優(yōu)解得情況，在不了解其具體求解路徑時，可以通過改變初始的工件各工序耗時矩陣，求得其它最優(yōu)解。如316542 ，416532，341652，146532都可以使總的加工時間為35min，提供了更多的可選擇方案。2. 多種加工順序

18、均能達到時間最短的目標，但是不同的加工順序?qū)?yīng)各機器的時間利用效率不同，綜合考慮增加加工成本最低的目標，建立多目標線性規(guī)劃模型，求出更具有實際意義的加工順序。3. 實際問題中，有可能多種安排順序時間相差不大，這時根據(jù)每臺機器運轉(zhuǎn)的成本不同，盡量使運轉(zhuǎn)成本高的機器工作時間短，提高其時間利用效率。根據(jù)時間和成本所占不同權(quán)重，確定最優(yōu)生產(chǎn)計劃。8模型的推廣與應(yīng)用此類流水線生產(chǎn)調(diào)度優(yōu)化問題在實際中經(jīng)常碰到，增強和減弱約束條件后能運用到其他方面。例如安排人員面試順序問題、將多項任務(wù)分配給多人完成、生產(chǎn)過程中存在制品庫存問題、公交車的調(diào)度問題等都可建立類似的線性規(guī)劃模型。將此模型稍作修改，具體問題具體分析便可以很好地解決這一類的優(yōu)化排序，生產(chǎn)規(guī)劃問題。運籌學的題目都可以用這類整數(shù)規(guī)劃模型解決。故該模型具有一定的實用性與推廣性。參考文獻1 姜啟源