帶零等待的混合流水車間問(wèn)題優(yōu)化研究

帶零等待的混合流水車間問(wèn)題優(yōu)化研究

1待hfs問(wèn)題的研究生產(chǎn)規(guī)劃是生產(chǎn)決策的過(guò)程，在大多數(shù)制造業(yè)和生產(chǎn)系統(tǒng)中起著重要作用。有效的調(diào)度能夠提高生產(chǎn)能力、提高客戶滿意度、減少庫(kù)存成本以及促進(jìn)瓶頸資源的利用等。在玻璃、鋼鐵等現(xiàn)實(shí)工業(yè)中?？商釤挸龌旌狭魉囬g(HybridFlowShop,HFS)結(jié)構(gòu)。Gupta迄今為止,已有一些文獻(xiàn)為解決零等待HFS問(wèn)題提出了不同的方法。就兩階段的零等待HFS研究而言,Wang等就多階段的零等待HFS而言,Khalili從上述研究可以看出,帶零等待約束的HFS調(diào)度受到了較多的關(guān)注,但考慮的生產(chǎn)特征各不同,且多數(shù)研究的目標(biāo)函數(shù)為最小化makespan,求解方法多為基于智能優(yōu)化的近似算法,基于最優(yōu)化的近似算法—LR算法的應(yīng)用較少,而該算法具有較好的分解特性,這使得一些復(fù)雜問(wèn)題的求解較為簡(jiǎn)便,而且它也為衡量解的質(zhì)量提供了一個(gè)評(píng)價(jià)標(biāo)準(zhǔn),即對(duì)偶間隙,因此,它克服了基于智能優(yōu)化的近似算法無(wú)法保證得到全局最優(yōu)解的問(wèn)題。LR算法將造成問(wèn)題NP-hard的約束松弛到目標(biāo)函數(shù)中,形成原問(wèn)題的松弛問(wèn)題,基于分解策略把松弛問(wèn)題分解成容易求解的子問(wèn)題,然后求解拉格朗日對(duì)偶問(wèn)題,最后將松弛問(wèn)題得到的解轉(zhuǎn)換為可行解,從而逐步求得近優(yōu)解。由于LR所需計(jì)算時(shí)間與其迭代次數(shù)有關(guān),因此縮短每次迭代耗費(fèi)的時(shí)間將有利于加速算法的執(zhí)行,故而設(shè)計(jì)了代理次梯度法(SSG)更新乘子,該方法在HFS問(wèn)題的應(yīng)用2問(wèn)題描述2.1機(jī)器的工作特點(diǎn)本文所研究的帶釋放時(shí)間的零等待HFS問(wèn)題特征如下。(1)工件數(shù)、階段數(shù)以及每個(gè)階段的機(jī)器數(shù)已知;(2)每個(gè)階段至少有一臺(tái)機(jī)器,且至少有一個(gè)階段的機(jī)器數(shù)多于一臺(tái);(3)工件動(dòng)態(tài)到達(dá)生產(chǎn)系統(tǒng)的始端;(4)工件在機(jī)器上的調(diào)整時(shí)間可忽略不計(jì);(5)每個(gè)工件有一個(gè)權(quán)重,每個(gè)工件在各個(gè)階段的加工時(shí)間是已知的;(6)所有的工件需經(jīng)過(guò)所有的加工階段且必須遵循相同的工藝路線;(7)在每個(gè)階段,一個(gè)工件只能在該階段的一臺(tái)機(jī)器上加工,且每臺(tái)機(jī)器一次只能加工一個(gè)工件;(8)任意兩個(gè)連續(xù)階段之間的操作不允許等待。2.2符號(hào)定義所建模型用到的符號(hào)及其含義如表1所示。2.3工件開(kāi)始時(shí)間(1)目標(biāo)函數(shù)該目標(biāo)旨在最小化總加權(quán)完成時(shí)間。該約束表示在時(shí)刻h正在階段s加工的工件數(shù)不能超過(guò)相應(yīng)時(shí)刻可使用的機(jī)器數(shù)。(3)工序加工時(shí)間要求該約束表明了開(kāi)始的操作不允許中斷。(4)零等待約束該約束說(shuō)明了工件在任意兩個(gè)相鄰階段間的操作不允許等待。(5)工件開(kāi)始時(shí)間要求該約束表示工件開(kāi)始加工的時(shí)間不能早于其到達(dá)第一階段始端的時(shí)間。(6)變量X(7)變量F本文的模型與文獻(xiàn)[9]不同之處在于考慮了工件動(dòng)態(tài)到達(dá)的特征和忽略了截止時(shí)間要求。3拉格朗日松弛算法3.1基于工件的分解策略通過(guò)引入一組拉格朗日乘子{v滿足約束(3)-(7)和上述式(8)也可表示為由于每個(gè)工件的約束(3)-(7),(9)都是相互獨(dú)立的,且目標(biāo)是加和的形式,因此,基于工件分解策略,將松弛問(wèn)題分解為多個(gè)工件級(jí)子問(wèn)題:滿足約束(3)-(7)和(9)。3.2解決工作級(jí)子問(wèn)題本文考慮了工件動(dòng)態(tài)到達(dá)的情況,因此,工件j在第一個(gè)階段開(kāi)始加工的可能最早時(shí)間和最晚時(shí)間分別為a3.3更新乘子的確定拉格朗日對(duì)偶問(wèn)題可表示為滿足約束(3)-(7)和(9)。代理對(duì)偶函數(shù)定義如下:相應(yīng)的代理次梯度為當(dāng)更新乘子時(shí),所用公式如下:式中,n是迭代次數(shù),β式中,LSSG每次迭代近似求解松弛問(wèn)題以獲得合理的代理次梯度方向,從而避免了復(fù)雜的求解過(guò)程和時(shí)間浪費(fèi)。由于該方法求的是松弛問(wèn)題的近似解,因此得到的代理對(duì)偶目標(biāo)值不能用作原問(wèn)題最優(yōu)值的下界3.4可執(zhí)行構(gòu)建由于上述得到的松弛問(wèn)題的解可能違反機(jī)器能力約束(2),因此,本文結(jié)合列表調(diào)度與兩兩交換4算法性能比較為了驗(yàn)證所設(shè)計(jì)算法的有效性,用C語(yǔ)言分別對(duì)基于SG法和基于SSG法的LR進(jìn)行編程,并在IntelCore2主頻為2.9GHz的微機(jī)上運(yùn)行,當(dāng)CPU時(shí)間達(dá)到180s或者(代理)對(duì)偶間隙小于0.05%時(shí)算法停止。算法的性能通過(guò)代理對(duì)偶間隙(對(duì)偶間隙)及CPU時(shí)間衡量。代理對(duì)偶間隙定義為對(duì)偶間隙為式中,GAP表示代理對(duì)偶間隙,L使用計(jì)算機(jī)隨機(jī)產(chǎn)生測(cè)試數(shù)據(jù),工件數(shù)取{20,50,80,100},階段數(shù)取{2,3,4},并行機(jī)數(shù)取{3,4}。工件j的權(quán)重、在各階段的加工時(shí)間和動(dòng)態(tài)到達(dá)時(shí)間是在[1,10]滿足均勻分布的整數(shù),計(jì)劃時(shí)間范圍設(shè)為所有工件的總加工時(shí)間之和。以上參數(shù)組合共產(chǎn)生24種問(wèn)題規(guī)模,每種規(guī)模隨機(jī)產(chǎn)生10組實(shí)例。因此,用于實(shí)驗(yàn)的實(shí)例共有240組。令LR-1表示基于SG法的LR算法,LR-2表示基于SSG法的LR算法。表2列出了由兩種算法所得到的(代理)對(duì)偶間隙和CPU時(shí)間,其中LR-2從表2和圖2~圖4中,可得到以下結(jié)論。(1)對(duì)于中小規(guī)模問(wèn)題,由LR-1和LR-2所得到的平均對(duì)偶間隙分別為2.74%和2.32%,平均CPU時(shí)間分別為153.11s和145.08s。后者的對(duì)偶間隙比前者減少了0.42%,CPU時(shí)間減少了8.03s。(2)對(duì)于大規(guī)模問(wèn)題,由LR-1和LR-2得到的平均對(duì)偶間隙分別為7.31%和6.51%,平均CPU時(shí)間均為180s。后者的對(duì)偶間隙比前者減少了0.80%。由此可知,LR-2性能優(yōu)于LR-1,尤其對(duì)于大規(guī)模問(wèn)題,后者優(yōu)勢(shì)更明顯。(3)對(duì)于所有實(shí)例,LR-1和LR-2的平均對(duì)偶間隙分別為5.03%和4.41%。從平均性能來(lái)看,兩種LR算法都能在較短的時(shí)間內(nèi)得到令人滿意的近優(yōu)解,但LR-2比LR-1改進(jìn)了0.62%。由于對(duì)偶間隙衡量的是啟發(fā)式解和下界之間的相對(duì)差,所以對(duì)偶間隙小于5%的解離最優(yōu)解的距離實(shí)際上更近。(4)對(duì)于中小規(guī)模和大規(guī)模的問(wèn)題,真正對(duì)偶間隙與代理對(duì)偶間隙之差分別為0.02%和0.14%。因此,隨著問(wèn)題規(guī)模的增大,真正對(duì)偶間隙與代理對(duì)偶間隙之差略有增大。(5)從圖2-圖4可看出:程序運(yùn)行的前期,兩種算法的收斂速度都較快,之后收斂速度較平穩(wěn);總體上來(lái)看,LR-2比LR-1的收斂速度更快。5靜態(tài)離散時(shí)間數(shù)學(xué)模型的設(shè)計(jì)本文研究了帶釋放時(shí)間