【摘要】：在制造領(lǐng)域,調(diào)度是生產(chǎn)管理的核心和關(guān)鍵技術(shù),合理的調(diào)度可以縮短制造期、減少資源浪費(fèi),提高經(jīng)濟(jì)效益。隨著生產(chǎn)過(guò)程的日益復(fù)雜和競(jìng)爭(zhēng)的加劇,調(diào)度的作用越來(lái)越重要。 柔性開(kāi)放車間調(diào)度問(wèn)題(FOSSP)是生產(chǎn)中常見(jiàn)的調(diào)度問(wèn)題,也是亟待解決的高難度組合優(yōu)化問(wèn)題。本文主要研究加工可中斷、不可中斷和具有機(jī)器使用限制三種情況下的柔性開(kāi)放車間調(diào)度問(wèn)題(Om(P)|pmtn,ri|Cmax、Om(P)||Cmax和Om(P)|r,aN,I|Cmax)的數(shù)建模和近似調(diào)度算法設(shè)計(jì)。針對(duì)問(wèn)題特點(diǎn),分別采用網(wǎng)絡(luò)流和半匹配理論設(shè)計(jì)了相應(yīng)的近似調(diào)度算法,并給出了算法的最壞情況界等性能參數(shù)。 本文主要研究?jī)?nèi)容包括以下五個(gè)方面： 1.研究了柔性開(kāi)放車間調(diào)度問(wèn)題的數(shù)學(xué)建模方法。分析了可中斷、不可中斷和具有機(jī)器使用限制三種情況下柔性開(kāi)放車間生產(chǎn)過(guò)程的約束條件,將它們形式化的表示為一組約束函數(shù),以制造期最短為優(yōu)化目標(biāo),建立了上述三種柔性開(kāi)放車間調(diào)度問(wèn)題的混合整數(shù)規(guī)劃模型,為算法驗(yàn)證奠定了基礎(chǔ)。 2.以制造期最短為優(yōu)化目標(biāo),給出了基于網(wǎng)絡(luò)流的Om(P)|pmtn,ri|Cmax(?)司題調(diào)度算法。算法將Om(P)|pmtn,ri|Cmax問(wèn)題分解為資源分配和工件排序兩個(gè)子問(wèn)題,首先將調(diào)度問(wèn)題轉(zhuǎn)化為網(wǎng)絡(luò)流模型,通過(guò)最大流算法確定使機(jī)器滿負(fù)荷工作的資源分配方案。為了提高最大流算法的效率,研究了融入加工領(lǐng)域知識(shí)的活躍頂點(diǎn)選擇策略,采用最小負(fù)載優(yōu)先和最大工作量?jī)?yōu)先啟發(fā)式規(guī)則設(shè)計(jì)了高效率的最大流算法。針對(duì)最大流存在陷入局部?jī)?yōu)化的情況,給出了優(yōu)化方法。在最大流的基礎(chǔ)上,通過(guò)加工時(shí)間矩陣的減量集合確定工件的加工順序 3.針對(duì)Om(P)||Gmax問(wèn)題求解難度大的特點(diǎn),給出了以稠密調(diào)度為目標(biāo)的近似調(diào)度算法求解方案,該方案將調(diào)度問(wèn)題分解為資源匹配和調(diào)度優(yōu)化兩個(gè)子問(wèn)題,每次資源匹配所有工件都僅完成一個(gè)操作,那么具有m個(gè)操作的工件集合需要進(jìn)行m次資源匹配,通過(guò)連接各資源匹配結(jié)果得到初步調(diào)度解,最后對(duì)初步調(diào)度解進(jìn)行優(yōu)化,消除不必要的機(jī)器空閑時(shí)間,得到稠密調(diào)度解。在兩個(gè)子問(wèn)題中,資源匹配是核心問(wèn)題,文中采用賦權(quán)二分圖進(jìn)行建模,通過(guò)半匹配求得負(fù)載差異最小的資源匹配結(jié)果,并且針對(duì)小規(guī)模和大規(guī)模問(wèn)題分別設(shè)計(jì)了基于最優(yōu)增廣路徑和基于遺傳算法的最優(yōu)半匹配算法。在資源匹配的基礎(chǔ)上,本文給出了初步調(diào)度解的構(gòu)造方法及其優(yōu)化方法。 4.研究了Om(P)|r,aN.I|Cmax問(wèn)題制造期下界的計(jì)算方法。由于存在機(jī)器使用限制,無(wú)法通過(guò)簡(jiǎn)單的方法獲得制造期的下界。因此,本文通過(guò)約束松弛將原問(wèn)題轉(zhuǎn)化為機(jī)器使用限制下可中斷柔性開(kāi)放車間調(diào)度問(wèn)題(Om(P)|r,aN.I,pmtn|Cmax),Om(P)|r,aN.I,pmtn|Cmax易于解決,將它的最短制造期作為Om(P)|r,aN.I|Cmax問(wèn)題制造期的下界。具體的解決方法是首先建立Om(P)|r,aN.I,pmtn|Cmax|司題的混合整數(shù)規(guī)劃模型,在此基礎(chǔ)上將模型中的約束條件轉(zhuǎn)化為弧的容量約束,得到問(wèn)題的網(wǎng)絡(luò)流模型。然后,通過(guò)最大流算法求得它的制造期,以此作為Om(P)|r,aN.I|Cmax問(wèn)題的制造期下界。 5.針對(duì)Om(P)|r,aN.1|Cmax問(wèn)題,給出了最壞情況界為2的稠密調(diào)度算法。Om(P)|r,aN1|Cmax問(wèn)題允許機(jī)器在制造期內(nèi)含有一個(gè)不可用時(shí)間窗,并且被中斷工件在機(jī)器恢復(fù)可用后可以繼續(xù)加工。文中將機(jī)器的不可用時(shí)間窗定義為虛擬工件,它的加工起止時(shí)間等于不可用時(shí)間窗的開(kāi)始時(shí)間和結(jié)束時(shí)間。為了降低問(wèn)題的難度,首先在不考慮虛擬工件的情況下進(jìn)行資源匹配,進(jìn)而通過(guò)分析虛擬工件與資源匹配制造期間的關(guān)系,得到三種模式關(guān)系。針對(duì)每種模式的特點(diǎn),給出了考慮虛擬工件后的資源匹配調(diào)整方法。在此基礎(chǔ)上,設(shè)計(jì)了Om(P)|r,aN.1|Cmax問(wèn)題的稠密調(diào)度算法。 在算法性能研究方面,本文從理論和算例試驗(yàn)兩個(gè)方面分析了上述三種柔性開(kāi)放車間調(diào)度算法的性能。在理論上,分析了調(diào)度算法的時(shí)間復(fù)雜度和最壞情況界,并通過(guò)隨機(jī)產(chǎn)生的算例驗(yàn)證了算法的正確性,結(jié)果表明算法能夠求得調(diào)度問(wèn)題的有效解,并且制造期滿足最壞情況界指標(biāo)。
【學(xué)位授予單位】：哈爾濱工程大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2011
【分類號(hào)】：TH186
【圖文】：

圖1.3論文的總體結(jié)構(gòu)圖F19.1.3Tllestr·L一etL一e91丑Plloftlledisse一tatio一1第5一章研究了機(jī)器使用限制卜柔性川飛放車問(wèn)調(diào)度問(wèn)題，給{日了最壞情況界為2的稠密調(diào))夏算法。首先，通過(guò)分析調(diào)度問(wèn)題的約束條件，建花了i亥問(wèn)題的混合整數(shù)規(guī)劃模型，為算法ll{確險(xiǎn)驗(yàn)i讓奠定了基礎(chǔ)。進(jìn)而，為了得到制造)t)]的卜界，本章通過(guò)松弛不.IJ一中斷約束，建_立了可中斷隋況的網(wǎng)絡(luò)流模型，少}通過(guò)最大流算爭(zhēng)去求得它「l{J制造期，以此作為機(jī)器使用限制下柔性開(kāi)放車I’l習(xí)調(diào)度問(wèn)題的劊jl]造期卜界。對(duì)J幾機(jī)器使用限制，文，「，采川了虛擬工件表示法，將機(jī)器的不萬(wàn)!J一用時(shí)間窗轉(zhuǎn)化為廠副以l_件，在此幕礎(chǔ)卜通過(guò)分析虛擬}件與資源匹配制造期間的關(guān)系，得到了二幾干，1，模式關(guān)系及其調(diào)整方法。在此從礎(chǔ)卜，給出了稠密調(diào)度算法。最后分析了稠密調(diào)度算法的}l.]I樸」復(fù)雜度和最壞情況界，井進(jìn)行了算例試驗(yàn)，結(jié)果表}明算法f]’旨?jí)蚯蟮谜{(diào)度問(wèn)題的稠密調(diào)度解，井日.制造均{滿足最壞情況界指標(biāo)。本文最后對(duì)個(gè)文進(jìn)行了總結(jié)，展望了卜步的付「究}_作。

lJ一分別為兩個(gè)11_不相交的r集廠!和價(jià)，又寸J一萬(wàn)，{，子千泣邊。一比.、，，)，均有、，，:廠，和、，/任矛遙，I_l協(xié)條邊。都對(duì)!、布」個(gè)權(quán)亞喲。)。_分1冬1是‘類特殊的無(wú)向圖，圖2.2為一個(gè)賦權(quán)_分圖，邊表小兩個(gè)項(xiàng)點(diǎn)I’l]J存在鄰接關(guān)系。為了進(jìn)一步分析廠}和價(jià)中丁貞點(diǎn)l’[lJl’l勺一元關(guān)系，引出了匹配的概念。、{‘.丫2一、’3一、’」..一比一.一、’b圖2.2一分圖「 19.2.2BipaltilegI’aPI1【定義2.4】匹配:邊集合F里萬(wàn)足1冬IC的個(gè)匹配，若咚】(尸}，的協(xié)個(gè)項(xiàng)點(diǎn)都儀’。產(chǎn)一，}，自勺一條邊關(guān)聯(lián)11}定義 2.4.J知，}冬 12.3(a)足合李去匹配

【參考文獻(xiàn)】

相關(guān)期刊論文 前10條

1 陳榮軍;唐國(guó)春;;自由作業(yè)加工總長(zhǎng)排序問(wèn)題的稠密時(shí)間表[J];系統(tǒng)工程;2007年09期

2 馬英;楊善林;儲(chǔ)誠(chéng)斌;;機(jī)器在一段時(shí)間不可用條件下的單機(jī)調(diào)度問(wèn)題[J];合肥工業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版);2007年08期

3 馬英;左春榮;;帶不可用時(shí)間段和惡化加工時(shí)間的幾個(gè)多項(xiàng)式可解問(wèn)題[J];合肥工業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版);2009年03期

4 劉朝暉,俞文泦;關(guān)于工件組的兩機(jī)自由作業(yè)時(shí)間表問(wèn)題[J];華東理工大學(xué)學(xué)報(bào);2000年06期

5 陳秀宏,俞文泦;自由作業(yè)稠密時(shí)間表的性能比上界[J];華東理工大學(xué)學(xué)報(bào);2000年06期

6 李紅英,蘇純潔;機(jī)器使用有限制的兩臺(tái)同類機(jī)排序[J];華東理工大學(xué)學(xué)報(bào)(自然科學(xué)版);2005年04期

7 張憲超 ,陳國(guó)良 ,萬(wàn)穎瑜;網(wǎng)絡(luò)最大流問(wèn)題研究進(jìn)展[J];計(jì)算機(jī)研究與發(fā)展;2003年09期

8 喻小光;戰(zhàn)德臣;聶蘭順;初佃輝;徐曉飛;;柔性資源約束的資源水平項(xiàng)目調(diào)度問(wèn)題[J];計(jì)算機(jī)集成制造系統(tǒng);2010年09期

9 高亮;高海兵;周馳;;基于粒子群優(yōu)化的開(kāi)放式車間調(diào)度[J];機(jī)械工程學(xué)報(bào);2006年02期

10 韓兵,席裕庚;多機(jī)器總完成時(shí)間和makespan近似最優(yōu)的開(kāi)放式車間調(diào)度方法[J];控制理論與應(yīng)用;2003年06期

相關(guān)博士學(xué)位論文 前1條

1 蔣義偉;可中斷平行機(jī)排序問(wèn)題研究[D];浙江大學(xué);2007年

本文編號(hào)：2791137