..題目：流水線車間調度優化模型[摘要]通過對問題的分析,流水線車間調度問題可以歸結為一個整數規劃問題,本論文中根據題目所給的條件以及實際情況依次建立起兩個模型。在滿足加工時間最短的前提下,基于對問題約束條件不同的翻譯得到兩個模型從而得到不同的生產順序,為決策者提供了更多的生產方案。聯系生產生活實際情況,放松加工工件必須遵循相對順序不變這一約束條件,提出模型的改進方向。模型一,根據題目要求即每個工件的加工順序為彎折——焊接——裝配且每臺機器每次只能處理一個加工件。構造一個每行每列只含一個1其余元素為0的矩陣,通過矩陣乘積實現對原來工件工序耗時的行變換,整個過程相當于遍歷。建立線性規劃模型,利用LINGO軟件求解。結果為當加工順序為4—1—3—6—5—2時,用時最短為35min,利用Excel作出甘特圖使整個生產安排流程更加清晰,引入時間利用率的概念即加工工件的時間占開啟時間的百分比,得到在加工順序為4—1—3—6—5—2時機器一〔彎折機器二〔焊接機器三〔裝配的時間利用率依次為,,,從而可從機器負載評價加工過程。模型二,將每臺機器每次只能處理一個加工件這一約束條件翻譯為一旦開始順序確定,則后續工序仍按原順序進行。引入0—1變量表示兩工件生產順序,建立0—1規劃模型,利用LINGO軟件求解。結果為當加工順序為1—3—6—4—5—2時,用時最短為35min。利用甘特圖對結果進行分析與檢驗,得到3臺機器的時間利用效率分別為,為決策者選擇方案提供了更多的參考指標。討論本文所建模型的優點和缺點,橫向的對比兩個模型。在工件數目相對較多〔在十這一數量級上的情況下選擇模型一求解,LINGO可以在短時間內給出答案；在數據量較少的情況下運用模型二求解,因為它模型建立過程簡單易懂,編程容易。但是對于工件數目處于百個數量級時,兩種模型均無法在短時間內得到答案,需要建立新的模型,設計新的算法求解此類大規模排序問題。針對模型的部分缺點提出優化改進方案,改變初始工件加工各工序耗時矩陣,即動態設立初始點以彌補LINGO軟件只能輸出一組最優解的局限,得出當加工順序為3—1—6—5—4—2,4—1—6—5—3—2,3—4—1—6—5—2,1—4—6—5—3—2時也能使加工時間最短為35min,提供了更多的可選擇方案。聯系實際生產,根據各機器單位時間的工作成本不同,可以建立多目標規劃模型,既要使總的時間最短又要使整個加工過程機器的總成本最低,同時實現時間和成本的最優化。可以為決策者提供更實用的生產工件加工順序規劃。文末簡述了模型的推廣與應用。將此線性整數規劃模型稍作修改就可以運用到安排面試人員的面試順序、單機調度最優化、公交車的調度等問題。枚舉的思想可以用到一些小規模的排序問題中,利用優化軟件也可以快速求得其最優解。可以為實際生產生活解決問題帶來極大地便利。[關鍵詞]流水線調度線性整數規劃模型甘特圖LINGO1問題重述21世紀是一個注重效率和時間利用率的時代,在工業生產和經濟發展中,我們竭盡全力去節省時間,在有限的時間內盡可能多的創造財富。所以,根據實際的生產需要及生產要求合理的安排生產的順序尤為重要。生產調度即將分好批的生產任務落實到加工設備上,以使某代價最小,所謂的某代價最小也即優化目標。所謂的流水線車間調度即有一組功能不同的機床,待加工的零件包含多道工序,每道工序在一臺機床上加工,所有零件的加工順序相同。在本問題中,共有3個機床,6種待加工零件,每種零件需要經過3道工序,每臺機床同一時間只能加工一種工件,確定了開始時的加工順序隨后的加工順序不會改變。建立適當的數學模型,確定加工件的先后順序,使得加工所有用件用時最短。6種工件加工工序需時〔分鐘見下表1：表1：6種加工工件各工序耗時表〔min加工件123456彎折363557焊接542445裝配5246362問題分析與假設2.1問題分析此問題屬于規劃問題,目的是給出使加工時間最短的工件加工順序。已知每個加工件在各個加工工序所需要的時間,并且規定每臺機器每次只能處理一個加工件,每個加工件按照給定處理步驟即彎折——焊接——裝配依次進行,要求出加工所有工件所用的最短時間。要讓總的加工時間最短,每種機器工作時間是連續的,即中途不允許在有生產任務有做相應任務的機器空閑時,機器不加工。總的時間就是第一臺機器開始工作到第三臺機器停止工作的時間。通過分析知道此問題是一個整數規劃問題,準確的說是一個線性規劃中的二次分配問題。根據題目要求忽略次要影響因素,將主要因素翻譯成數學語言,利用已有的數學知識,建立相應的模型。忽略了機器加工的準備時間以及機器可能出現故障等突發條件,以工件加工順序隨初始順序而確定,各工件按一定順序加工為主要約束條件,建立使得加工總用時最少的整數規劃模型。2.2模型假設<1>機器正常工作,不出現故障,中途也不需要進行維護；<2>機器加工效率不隨時間改變,即加工件的先后順序不影響各個工序的用時；<3>每種金屬管件都要經過三個階段即彎折、焊接、裝配,先后順序不允許打亂,兩工序之間可以等一段時間也可以不隔時間；<4>每種機器每次只能處理一個加工件,等待下一臺機器處理時,按原順序進行不允許排在后面的加工件"插隊"；〔5所有機器準備時間〔忽略為零,即所有生產件立即進入加工；〔6無緊急件及其他突發情況。3符號說明符號含義：工件總數加工工序數第I個加工的工件第J道工序所需要的時間第I個加工的工件開始第J道工序的時刻號加工件在第j個工序需要的時間號加工件開始第j道工序的時刻引入的0—1變量,總用時加工第道工序的機器的時間利用效率4模型一的建立與求解4.1模型一的建立此問題明顯是根據生產順序的排列組合,求最小的生產時間的問題。一共有六個工件共有720種可能的排列順序。構建一個的0-1矩陣,每行每列僅有一個元素為1,其余元素為0,共有720種矩陣。我們假設最優的方案已經找到,即第個生產的工件工件號為i。要求最小的加工時間,即第一臺機器開始工作到最后一臺機器停止工作的時間最短。轉化為最后一個加工的工件開始第三道工序的時刻與第三道工序耗時之和即 〔4.1又由假設可知每個工件依次經過彎折—焊接—裝配,所以對于第I個加工的工件前一個工序的結束時間必須在不晚于下一道工序的開始時間即〔4.2又每個機器每次只能加工一個工件故第I+1個工件必須在第I個工件的J工序完成后才能進行J工序, 〔4.3因為已經假設最優的方案已經找到,是對應最優方案的工序加工耗時,必須對原來的按工件序號組成的耗時矩陣變換為按加工順序組成的耗時矩陣。引入的0-1矩陣,每行每列僅有一個元素為1,其余元素為0。兩矩陣相乘得到的新矩陣,例如,若最優解對應的,說明工件3排在第一個加工。第一行即第一個加工工件各加工工序的耗時,以此類推第6行是第6個加工工件各工序的耗時。綜上,得到整數規劃模型如下：；注：為了表達簡便,在約束條件中,將取到6,取到3,但在為3時越界,在為6時越界,此時只需在編程的過程中對分分別約束即可。4.2模型的求解將目標函數及約束條件輸入到Lingo中運行求解,可以得到結果〔程序語句以及輸出結果參見附錄,可得加工順序為為3—4—1—2—5—6。為了更清晰的說明生產流程,由求解結果作出各工件開始、完成各工序的時間表4—1表4—1工件i開始及完成工序J的時間生產工序J工件號開始1〔彎折完成彎折開始2<焊接>完成焊接開始3〔裝配裝配完成4055991515891415203811171920246111819242430518232529303322329293333354.3模型檢驗與分析根據表4—1利用Excel作出甘特圖如圖4一1圖4一1工件生產順序甘特圖即加工順序為4—1—3—6—5—2時,最短加工時間為35min。負責彎折的機器0—29min一直工作,未出現空載情況；負責焊接的機器5—9min、17—24min、25—33min工作,從開始到停止共9min空載；負責裝配的機器9—35min一直工作。利用率=機器1〔負責彎折機器2〔負責焊接機器3〔負責裝配在一個生產周期時間利用率可以看出此加工順序使三個機器的空載時間不均衡,機器二空載時間過長。此模型模擬遍歷的過程,沒有對工件不允許插隊進行限制,而且各機器的時間利用效率不均衡,為了求解出更加合理的生產順序,建立模型二。5模型二的建立與求解5.1模型的建立模型一采取遍歷的思想方法來表示工件之間的絕對加工順序,還有一種方法就是對兩個工件的加工順序依次進行比較,引入0—1變量來表示任意兩個工件的相對加工順序,根據他們相對的加工順序求得總的加工順序。首先每個工件都要滿足按照彎折—焊接—裝配的工序生產。即前一個工序結束后才能進行后一個工序。故 〔5.1其次工件之間的加工順序不改變,引入0—1變量,,若按一種工件3道工序全部加工完成,另一工件才開始加工,完成6種工件需要94,故在之前加工時,〔5.2在之后加工時,〔5.3由<5.2><5.3>得 〔5.4〔5.4表示,也有可能在它之前加工。對于任何一個工件,其加工結束的時間應不超過總時間,即 〔5.5綜上所述,得到一個以加工時間最短為目標的整數規劃模型s.t.5.2模型的求解將目標函數及約束條件輸入到Lingo11中運行求解,可以得到結果〔程序語句以及輸出結果參見附錄,即加工順序為1—3—6—4—5—2時加工時間最短為35min。根據結果做出號工件開始第j道工序和完成第j道工序的時刻表5—1表5—1號工件開始第j道工序和完成第j道工序的時刻生產工序工件號1〔彎折完成彎折2<焊接>完成焊接3〔裝配裝配完成1033881322329293333353368101317413181822243051823232730336613131818245.3模型的檢驗與分析為了更加直觀的表示整個生產流程,畫出甘特圖。如圖5-2從甘特圖中可以清晰的看出加工順序為1—3—6—4—5—2,總時間為35min。工序1即彎折的條形圖,負責彎折的機器從0-29min一直工作,沒有出現空載情況；工序2的條形圖,負責焊接的機器3-10min工作,10-13min空載,13-33min工作；工序3的條形圖,負責裝配的機器從8-17min工作,17-18min空載,18-35min工作。機器1〔負責彎折機器2〔負責焊接機器3〔負責裝配在一個生產周期時間利用率在此情況下,三個機器的利用率相差不大即機器負荷相對平衡。得到了比較滿意的生產順序安排。6模型的評價本文建立了兩個模型。模型一建立了線性整數規劃模型,模擬遍歷的過程,解決了各生產工件任務量相等時完成任務的最短時間以及對應的加工順序。模型二引入0—1變量表示兩工件相對加工順序,建立了0—1規劃模型,求得使加工過程最短的加工順序。6.1模型的優點采用較為成熟的數學理論建立模型,所建模型簡單,通俗易懂。為求得更為合理的生產工作調度表,建立多個模型,對結果進行比較,有較強的實用性。模型的計算采用LINGO軟件,算法簡便,編程實現簡單；可信度較高,便于推廣。甘特圖的使用使生產過程更加清晰,各機器工作時間,各工件加工進度一目了然。機器時間利用效率概念的引入從整體上評價了不同生產順序的利弊。6.2模型的缺點〔1模型雖然綜合考慮了很多因素,但為了建立模型,理想化了許多影響因素,具有一定的局限性,得到的最優方案可能與實際有一定的出入。〔2模型只考慮了時間最短,沒有考慮成本最低,有可能每個機器運轉時單位時間花費不同,模型結果與實際有一定差距。〔3所建立的模型對工件個數少的流水線調度比較適用,一旦工件種類增加至100個及以上可能很難得到全局的最優解。〔4LINGO軟件求解優化問題時,只能輸出一組最優解,其他最優解不能輸出。即使得到了最短時間是35min,但是不能得到所有使與之對應的加工順序。7模型的優化與模型改進針對上述提出的不足之處,可進一步對模型進行優化,如：對于模型1針對LINGO不能輸出所有最優解得情況,在不了解其具體求解路徑時,可以通過改變初始的工件各工序耗時矩陣,求得其它最優解。如3—1—6—5—4—2,4—1—6—5—3—2,3—4—1—6—5—2,1—4—6—5—3—2都可以使總的加工時間為35min,提供了更多的可選擇方案。多種加工順序均能達到時間最短的目標,但是不同的加工順序對應各機器的時間利用效率不同,