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

1、題目：流水線車間調(diào)度優(yōu)化模型【摘要】通過對(duì)問題的分析，流水線車間調(diào)度問題可以歸結(jié)為一個(gè)整數(shù)規(guī)劃問題，本 論文中根據(jù)題目所給的條件以及實(shí)際情況依次建立起兩個(gè)模型。在滿足加工時(shí)間最 短的前提下，基于對(duì)問題約束條件不同的翻譯得到兩個(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的矩 陣，通過矩陣乘積實(shí)現(xiàn)對(duì)原來工件工序耗時(shí)的行變換，整個(gè)過程相當(dāng)于遍歷。建立 線性規(guī)劃

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

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

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

5、詞】流水線調(diào)度線性整數(shù)規(guī)劃模型甘特圖 LINGO1問題重述21世紀(jì)是一個(gè)注重效率和時(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ī)床上加工，所有零件的加工順序相 同。在本問題中，共有3個(gè)機(jī)床，6種待加工零件，每種零件需要經(jīng)過3道工 序，每臺(tái)機(jī)床同一時(shí)間只能加工一種工件，確定了開始時(shí)的加工順序隨后的

6、加工順 序不會(huì)改變。建立適當(dāng)?shù)臄?shù)學(xué)模型，確定加工件的先后順序，使得加工所有用件用時(shí)最 短。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 62問題分析與假設(shè)2.1問題分析此問題屬于規(guī)劃問題，目的是給出使加工時(shí)間最短的工件加工順序。已知每個(gè)加工件在各個(gè)加工工序所需要的時(shí)間，并且規(guī)定每臺(tái)機(jī)器每次只能 處理一個(gè)加工件，每個(gè)加工件按照給定處理步驟即彎折焊接裝配依次進(jìn)行，要求出加工所有工件所用的最短時(shí)間。要讓總的加工時(shí)間最短，每種機(jī)器工作 時(shí)間是連續(xù)的，即中途不允許在有

7、生產(chǎn)任務(wù)有做相應(yīng)任務(wù)的機(jī)器空閑時(shí)，機(jī)器不加 工?？偟臅r(shí)間就是第一臺(tái)機(jī)器開始工作到第三臺(tái)機(jī)器停止工作的時(shí)間。通過分析知道此問題是一個(gè)整數(shù)規(guī)劃問題，準(zhǔn)確的說是一個(gè)線性規(guī)劃中的二 次分配問題。根據(jù)題目要求忽略次要影響因素，將主要因素翻譯成數(shù)學(xué)語(yǔ)言，利用 已有的數(shù)學(xué)知識(shí)，建立相應(yīng)的模型。忽略了機(jī)器加工的準(zhǔn)備時(shí)間以及機(jī)器可能出現(xiàn) 故障等突發(fā)條件，以工件加工順序隨初始順序而確定，各工件按一定順序加工為主 要約束條件，建立使得加工總用時(shí)最少的整數(shù)規(guī)劃模型。2.2模型假設(shè)機(jī)器正常工作，不出現(xiàn)故障，中途也不需要進(jìn)行維護(hù)；機(jī)器加工效率不隨時(shí)間改變，即加工件的先后順序不影響各個(gè)工序的用 時(shí)；每種金屬管件都要經(jīng)過三個(gè)

8、階段即彎折、焊接、裝配，先后順序不允 許打亂，兩工序之間可以等一段時(shí)間也可以不隔時(shí)間；每種機(jī)器每次只能處理一個(gè)加工件，等待下一臺(tái)機(jī)器處理時(shí)，按原順序進(jìn) 行不允許排在后面的加工件“插隊(duì)”；所有機(jī)器準(zhǔn)備時(shí)間(忽略)為零，即所有生產(chǎn)件立即進(jìn)入加工；無緊急件及其他突發(fā)情況。3符號(hào)說明符號(hào)含義W：工件總數(shù)P加工工序數(shù)第I個(gè)加工的工件第J道工序所需要的時(shí)間第I個(gè)加工的工件開始第J道工序的時(shí)刻%*I號(hào)加工件在第j個(gè)工序需要的時(shí)間*號(hào)加工件開始第j道工序的時(shí)刻引入的01變量，0, i號(hào)工件在k號(hào)工件前加工1, j號(hào)工件在左號(hào)工件后加工T總用時(shí)%加工第./道工序的機(jī)器的時(shí)間利用效率4模型一的建立與求解4.1模型

9、一的建立此問題明顯是根據(jù)生產(chǎn)順序的排列組合，求最小的生產(chǎn)時(shí)間的問題。一共有 六個(gè)工件共有720種可能的排列順序。構(gòu)建一個(gè)6x6的0-1矩陣，每行每列僅有一個(gè)元素為1，其余元素為0，共有720種矩陣。我們 假設(shè)最優(yōu)的方案已經(jīng)找到，即第T個(gè)生產(chǎn)的工件工件號(hào)為i。要求最小的加工時(shí)間，即第一臺(tái)機(jī)器開始工作到最后一臺(tái)機(jī)器停止工作的時(shí) 間最短。轉(zhuǎn)化為最后一個(gè)加工的工件開始第三道工序的時(shí)刻與第三道工序耗時(shí)之和 即7 =曜加十呼&（4.1）又由假設(shè)可知每個(gè)工件依次經(jīng)過彎折一焊接一裝配，所以對(duì)于第I個(gè)加工的 工件前一個(gè)工序的結(jié)束時(shí)間必須在不晚于下一道工序的開始時(shí)間即（4.2）又每個(gè)機(jī)器每次只能加工一個(gè)工件故第I

10、+1個(gè)工件必須在第I個(gè)工件的J工序完成后才能進(jìn)行J工序，（4.3）因?yàn)橐呀?jīng)假設(shè)最優(yōu)的方案已經(jīng)找到，訥v是對(duì)應(yīng)最優(yōu)方案的工序加工耗時(shí)，必須對(duì)原來的按工件序號(hào)組成的耗時(shí)矩陣變換為 按加工順序組成的耗時(shí)矩陣。引入6x6的0-1矩陣，每行每列僅有一個(gè)元素為1，其余元素為0。41s23w,w 上，W4.G ，知*上3w%,上1，如,加WhW的,W知41，如，43WE矽W如A 1 ,農(nóng)-A%w知w上J、y j卻 _W，w為少隊(duì)無，兒I，人，死一玲 I，鳧 坤為、a* y? I，也，瑁，外、為， 丹I J-in 30少桐，貝3我46孔I，為我印盼為，珞）64，罵犬咿二1,茬二，2,3,4,，6獻(xiàn)二I龍” 二

11、L鋼=1，2,3,4,5,6 n-i兩矩陣相乘得到的新矩陣，例如吧1 5+為叫1 +入孩4】+九叫】+% 購(gòu)+尸任叫1若最優(yōu)解對(duì)應(yīng)的Jim = 1，說明工件3排在第一個(gè)加工。第一行即第一個(gè)加工工件各加工工序的耗時(shí)，以此 類推第6行是第6個(gè)加工工件各工序的耗時(shí)。綜上，得到整數(shù)規(guī)劃模型如下：min十 卵方皿,凹4l，七占3力1*光*外a y：4，j%兩右Cii 頃，上叫I，w上w知的1，肉半為，M.4 *，地上1盤殄如叫3知Xll, Xl； ? A41 J 尸45，JsGj f J , 匕 4W或W如叫3.烏 1 1 y. * r JV r Pis，Mfiy,l，y&2，63，- Jtri，比S

12、七1 棚妃七wi，wb，wL6k/，W4,5,6JM-I力 j,二 1,珀= 1,2,3,4,5,6 心洲打+岫與皿川）1=1,2,345,6J I.,%3注：為了表達(dá)簡(jiǎn)便，在約束條件中，將I取到6，J取到3,但也內(nèi)）在為3時(shí)越界，討川為6時(shí)越界，此時(shí)只需在編程的過程中對(duì)分IJ分別約束即可。4.2模型的求解將目標(biāo)函數(shù)及約束條件輸入到Lingo中運(yùn)行求解，可以得到結(jié)果（程序語(yǔ)句 以及輸出結(jié)果參見附錄），可得加工順序?yàn)闉?41256。為了更清晰的說明生產(chǎn)流程，由求解結(jié)果作出各工件開始、完成各工序的時(shí) 間表41表41工件i開始及完成工序J的時(shí)間生產(chǎn)工序J工件號(hào)F開始1（彎折）完成彎折開始2（焊接）完

13、成焊接開始3 （裝配）裝配完成4055991515891415203811171920246111819242430518232529303322329293333354.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é)裝配的機(jī)器935min 一直工作。利用率二F品皿婦。%機(jī)器1（負(fù)責(zé)彎折）機(jī)器2 （負(fù)責(zé)焊接）機(jī)器3（負(fù)責(zé)裝配）在一個(gè)生產(chǎn)周期時(shí)間利用

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

15、之間的加工順序不改變，引入01變量，F(xiàn) = JO, i號(hào)工件在&號(hào)T件前加工“一 h珂工件在比號(hào)工件后加:：，若按一種工件3道工序全部加工完成，另一工件才開始加工，完成6種工件 需要94,故+在k之前加工時(shí)，（與+匕_如京94 叫=0（5.2）k之后加工時(shí)，0 W)件(i)=()(5.3)由(5.2)(5.3)得4+4-施亡94季匕%+虹_ 屈M9S(1一孔)(5.4)表示i號(hào)工件有可能在號(hào)廠件后加.，也有可能在它之前加工。對(duì)于任何一個(gè)工件，其加工結(jié)束的時(shí)間應(yīng)不超過總時(shí)間，即婦+可3 - T(5.5)綜上所述，得到一個(gè)以加工時(shí)間最短為目標(biāo)的整數(shù)規(guī)劃模型min Ts.t.婦4電可I與 + r F

16、 94* 孔站+%-島 94* (1-V 加 *4 4 T 1,2,345,6& =1,2,3心6 j = 口35.2模型的求解將目標(biāo)函數(shù)及約束條件輸入到Lingol 1中運(yùn)行求解，可以得到結(jié)果（程序語(yǔ) 句以及輸出結(jié)果參見附錄），即加工順序?yàn)?36452時(shí)加工時(shí)間最短為 35min。根據(jù)結(jié)果做出號(hào)工件開始第j道工序和完成第j道工序的時(shí)刻表51表51號(hào)工件開始第j道工序和完成第j道工序的時(shí)刻生產(chǎn)工序工件號(hào)1（彎折）完成彎折2（焊接）完成焊接3 （裝配）裝配完成103388132232929333335336810131741318182224305182323273033661313181824

17、5.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 工作，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í)間利用率邛，X100% = 90% 33-3n. = 士 .lx 100% = 963%35-K

18、在此情況下，三個(gè)機(jī)器的利用率相差不大即機(jī)器負(fù)荷相對(duì)平衡。得到了比較 滿意的生產(chǎn)順序安排。6模型的評(píng)價(jià)本文建立了兩個(gè)模型。模型一建立了線性整數(shù)規(guī)劃模型，模擬遍歷的過程， 解決了各生產(chǎn)工件任務(wù)量相等時(shí)完成任務(wù)的最短時(shí)間以及對(duì)應(yīng)的加工順序。模型二 引入01變量表示兩工件相對(duì)加工順序，建立了 01規(guī)劃模型，求得使加工過程 最短的加工順序。6.1模型的優(yōu)點(diǎn)（1）采用較為成熟的數(shù)學(xué)理論建立模型，所建模型簡(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）甘特圖的使用使

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