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

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

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

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

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

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

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

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

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

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

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

11、1 工件i開始及完成工序J的時(shí)間生產(chǎn)工序J工件號(hào)開始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模型檢驗(yàn)與分析根據(jù)表41利用Excel作出甘特圖如圖4一1圖4一1 工件生產(chǎn)順序甘特圖即加工順序?yàn)?13652時(shí)，最短加工時(shí)間為35min。負(fù)責(zé)彎折的機(jī)器029min一直工作，未出現(xiàn)空載情況；負(fù)責(zé)焊接的機(jī)器59min、 1724min、2533min工作，從開始到停止共9min空載；負(fù)責(zé)裝

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

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

14、完成第j道工序的時(shí)刻表51表51號(hào)工件開始第j道工序和完成第j道工序的時(shí)刻生產(chǎn)工序工件號(hào)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模型的檢驗(yàn)與分析為了更加直觀的表示整個(gè)生產(chǎn)流程，畫出甘特圖。如圖5-2從甘特圖中可以清晰的看出加工順序?yàn)?36452，總時(shí)間為35min。工序1即彎折的條形圖，負(fù)責(zé)彎折的機(jī)器從0-29min一直工作，沒有出現(xiàn)空載情況；工序2的條形圖，負(fù)責(zé)焊接的機(jī)器3-10min

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

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

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

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