【摘要】：調(diào)度問(wèn)題是一類具有廣泛應(yīng)用背景的組合優(yōu)化問(wèn)題,調(diào)度的主要目的是對(duì)有限資源的合理分配,以獲得最大的經(jīng)濟(jì)效益。隨著調(diào)度問(wèn)題的復(fù)雜化,已經(jīng)無(wú)法僅僅依靠經(jīng)驗(yàn)來(lái)解決調(diào)度問(wèn)題,這時(shí)候,一個(gè)高效的調(diào)度算法顯得尤為重要。由于調(diào)度流程和環(huán)境的復(fù)雜化,調(diào)度問(wèn)題不斷多樣化,且演化出多種具有不同特征的調(diào)度問(wèn)題。其中,批調(diào)度問(wèn)題就是對(duì)經(jīng)典調(diào)度問(wèn)題的擴(kuò)展和延伸。批調(diào)度問(wèn)題是將一定數(shù)量的工件同時(shí)使用批處理機(jī)進(jìn)行加工的問(wèn)題,廣泛應(yīng)用于多種場(chǎng)景,如物流運(yùn)輸、石油化工等。不同于經(jīng)典調(diào)度問(wèn)題,在批調(diào)度問(wèn)題中一臺(tái)機(jī)器可以同時(shí)對(duì)多個(gè)工件進(jìn)行無(wú)中斷加工。在批調(diào)度問(wèn)題中,首先對(duì)工件進(jìn)行分批,然后將工件以批的形式放入批處理機(jī)種進(jìn)行加工。工件分批后,批的屬性受該批中工件屬性和加工該批的機(jī)器屬性共同決定。批調(diào)度問(wèn)題已經(jīng)不滿足于對(duì)單一目標(biāo)的優(yōu)化,逐步考慮到對(duì)多種互斥目標(biāo)的優(yōu)化,形成了多目標(biāo)批調(diào)度問(wèn)題。蟻群算法是一種根據(jù)螞蟻覓食行為而提出的進(jìn)化算法。不同于其他的進(jìn)化算法,蟻群算法中的螞蟻能夠逐步構(gòu)造問(wèn)題的可行解。由于蟻群算法的構(gòu)造性,近年來(lái)蟻群算法被廣泛應(yīng)用于批調(diào)度這一類組合優(yōu)化問(wèn)題中。蟻群算法通過(guò)信息素、啟發(fā)式信息來(lái)指導(dǎo)螞蟻構(gòu)造新的可行解。在批調(diào)度問(wèn)題中,信息素記錄了工件與工件在同一個(gè)批中的歷史權(quán)重關(guān)系,指導(dǎo)螞蟻向歷史優(yōu)勢(shì)解空間搜索。啟發(fā)式信息通常是根據(jù)批調(diào)度經(jīng)驗(yàn)所設(shè)計(jì),指導(dǎo)螞蟻向人們所期望的解空間進(jìn)行搜索。通過(guò)信息素和啟發(fā)式信息,有效降低了批調(diào)度問(wèn)題的搜索空間,提高了解的搜索質(zhì)量。本文首先研究了平行批處理機(jī)環(huán)境下,調(diào)度不同到達(dá)時(shí)間的差異工件,以獲得極小化制造跨度的批調(diào)度問(wèn)題。根據(jù)問(wèn)題的特點(diǎn),提出了一種新的下界算法以評(píng)價(jià)算法性能,并證明了本文所提出的下界算法是有效的。根據(jù)批構(gòu)建過(guò)程中,第一個(gè)工件對(duì)于批構(gòu)建過(guò)程的影響,對(duì)批構(gòu)建過(guò)程中第一個(gè)工件的選擇提出了弱約束標(biāo)準(zhǔn)和兩個(gè)基于弱約束標(biāo)準(zhǔn)下的首工件選擇策略,并將兩個(gè)選擇策略引入到蟻群算法中。仿真實(shí)驗(yàn)的結(jié)果表明,批構(gòu)建過(guò)程中使用首工件弱約束策略是有效的且工件尺寸大的高概率選擇策略優(yōu)于平均概率選擇策略。其次,研究了平行批處理機(jī)環(huán)境下,調(diào)度具有不同到達(dá)時(shí)間的差異工件,以獲得極小化制造跨度和極小化最大延誤的多目標(biāo)問(wèn)題。為了降低蟻群算法的搜索空間,針對(duì)批構(gòu)建過(guò)程中的第一個(gè)工件提出了一種新的約束和選擇策略,并設(shè)計(jì)了一種新的啟發(fā)式信息。為了加強(qiáng)蟻群算法的局部搜索能力,引入了一種新的局部搜索螞蟻P-ANT以加強(qiáng)算法在非支配解的鄰域搜索能力。仿真實(shí)驗(yàn)的結(jié)果表明,本文所提降低蟻群搜索空間策略和新局部搜索螞蟻是有效的。最后,對(duì)所研究的批調(diào)度問(wèn)題與調(diào)度算法進(jìn)行了總結(jié),并對(duì)相關(guān)領(lǐng)域的研究方向進(jìn)行了展望。
【圖文】：

粒子通過(guò)當(dāng)前位置和其速度矢量來(lái)移動(dòng)每個(gè)粒子，以獲得新的解。逡逑在粒子群算法中，主要的組成部分包括：目標(biāo)函數(shù)、速度更新公式、位置更逡逑新公式和算法結(jié)束條件等。粒子群算法的算法流程如圖２．２所示。逡逑初跳聽(tīng)＿子逡逑的位ｓ和速度逡逑邐ｙ邐逡逑計(jì)？所栜Ｌ邐逡逑子ｉｉ鵬值逡逑ｖ逡逑子的歷灥尤枿邐男}逡逑否逡逑星否滿足終止條件＾＞邐逡逑蝻出優(yōu)彳七結(jié)逡逑ｍ逡逑（壀）逡逑圖２．２粒子群算法流程圖逡逑Ｆｉｇｕｒｅ邋２．２邋Ｔｈｅ邋ａｌｇｏｒｉｔｈｍ邋ｆｌｏｗ邋ｃｈａｒｔ邋ｏｆ邋ＰＳＯ逡逑２．３．３蟻群算法逡逑蟻群算法思想最早由Ｄｏｒｉｇｏ｜Ｍ１根據(jù)�。欤椋保∠佉捠常妫�?yàn)樗岢�，并很快得到逡逑者們的關(guān)注和研究。在尋找貪物T，螞蟻eA初以隨機(jī)的方式搜索巢穴周圍的區(qū)域，逡逑１３逡逑

最初蟻群算法主要應(yīng)用于旅行商問(wèn)題｜５１］，并隨著研宄的深入，蟻群算法己逡逑經(jīng)用于多種組合優(yōu)化問(wèn)題，如作業(yè)調(diào)度１５２］、車輛路徑問(wèn)題［５３）等。蟻群算法的算逡逑法流程如圖２．３所示。逡逑Ｃ＾Ｄ逡逑Ｉ逡逑初始化算法參數(shù)．逡逑送代次數(shù)設(shè)ｓ為0逡逑Ｉ逡逑邐？逆數(shù)增加逡逑Ｉ為每個(gè)幽構(gòu)逡逑ｍｍ逡逑”逡逑計(jì)ｇ解適應(yīng)度逡逑值逡逑更新信皂索逡逑—否達(dá)到薛大挪欠逡逑鏑出優(yōu)化結(jié)逡逑」［＿逡逑圖２．３蟻群算法流程圖逡逑Ｆｉｇｕｒｅ邋２．３邋Ｔｈｅ邋ａｌｇｏｒｉｔｈｍ邋ｆｌｏｗ邋ｃｈａｒｔ邋ｏｆ邋ＡＣＯ逡逑蟻群算法的核心是建立一個(gè)信息素系統(tǒng)，通常蟻群算法通過(guò)使用信息素矩陣逡逑來(lái)存儲(chǔ)信息素。在路徑問(wèn)題中，，信息素通常代表一條路徑到另一條路徑的信息素逡逑濃度。蟻群算法的一些關(guān)鍵細(xì)節(jié)如下：逡逑（１）初始化信息素濃度：在蟻群算法工作的開(kāi)始，首先將信息的濃度設(shè)置逡逑１４逡逑
【學(xué)位授予單位】：安徽大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2019
【分類號(hào)】：TP18;O221

【相似文獻(xiàn)】

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

1 苗成標(biāo);;萊蕪煤機(jī)公司師傅劉義(右)與徒弟張龍哲探討交流工件加工工藝改進(jìn)技術(shù)[J];中國(guó)工會(huì)財(cái)會(huì);2019年06期

2 白穆民;;圓柱體上階梯橫孔的加工[J];機(jī)械工藝師;1987年08期

3 文藝;;用簡(jiǎn)易夾具加工對(duì)稱旋轉(zhuǎn)的工件[J];電加工;1987年03期

4 黃衛(wèi)國(guó);幾種特殊工件的磨削加工(一)[J];磨料磨具與磨削;1988年01期

5 吳盛福;加工超長(zhǎng)軸的一種高效方法[J];機(jī)床;1989年02期

6 袁福麟;;圓感應(yīng)同步器用于車床加工錐度工件[J];機(jī)械工人.冷加工;1989年09期

7 康宇紅;張新功;;具有錯(cuò)位限制且工件可退化的單機(jī)重新排序問(wèn)題[J];系統(tǒng)科學(xué)與數(shù)學(xué);2018年04期

8 余鳳燕;;工件加工工序的自由度分析[J];企業(yè)科技與發(fā)展;2008年10期

9 張秀艷;張秀梅;;薄環(huán)工件加工過(guò)程易產(chǎn)生變形問(wèn)題的探討[J];硅谷;2008年23期

10 徐延輝;;機(jī)械加工中振動(dòng)對(duì)工件的影響[J];遼寧省交通高等�？茖W(xué)校學(xué)報(bào);2018年05期

相關(guān)會(huì)議論文 前4條

1 陳太湖;胡小建;李曉征;紀(jì)中麗;;基于K-Mediods聚類方法的液壓元件加工車間工件分批方法研究[A];第十九屆中國(guó)管理科學(xué)學(xué)術(shù)年會(huì)論文集[C];2017年

2 黃垣鋒;陳小莎;;典型零件加工方案——不銹鋼薄壁工件卡箍接頭加工方案[A];中國(guó)職協(xié)2017年度優(yōu)秀科研成果獲獎(jiǎng)?wù)撐募ㄒ欢泉?jiǎng)）[C];2018年

3 李曉舟;孫拂曉;;細(xì)長(zhǎng)件加工動(dòng)態(tài)特性的研究[A];科技創(chuàng)新與節(jié)能減排——吉林省第五屆科學(xué)技術(shù)學(xué)術(shù)年會(huì)論文集（上冊(cè)）[C];2008年

4 關(guān)鑫;;先進(jìn)刀具在特大型工件加工中的應(yīng)用[A];2009海峽兩岸機(jī)械科技論壇論文集[C];2009年

相關(guān)重要報(bào)紙文章 前1條

1 MEB記者 余悅;聚焦電動(dòng)汽車典型工件加工工藝[N];機(jī)電商報(bào);2018年

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

1 柴幸;帶有工件約束的平行機(jī)排序問(wèn)題的近似算法研究[D];鄭州大學(xué);2019年

2 郭艷東;初始調(diào)度調(diào)整受限的新到工件重調(diào)度優(yōu)化方法研究[D];東北大學(xué);2015年

3 路來(lái)驍;航空梁類鋁合金結(jié)構(gòu)件滾壓變形校正理論及方法研究[D];山東大學(xué);2018年

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

1 楊洋;帶有首工件選擇策略的批調(diào)度算法研究[D];安徽大學(xué);2019年

2 王利博;線性退化工件的分批在線排序問(wèn)題[D];鄭州大學(xué);2019年

3 吳吉榮;變厚度工件電火花線切割溫度場(chǎng)仿真研究[D];哈爾濱理工大學(xué);2019年

4 楊艷;混合磨具對(duì)磁力拋光的影響及實(shí)驗(yàn)研究[D];太原理工大學(xué);2019年

5 張建;差異工件并行批處理機(jī)調(diào)度問(wèn)題求解算法研究[D];中國(guó)科學(xué)技術(shù)大學(xué);2019年

6 黃廣煒;往復(fù)走絲電火花線切割加工控制系統(tǒng)及工件厚度識(shí)別研究[D];上海交通大學(xué);2017年

7 肖奕霖;帶有相容工件族的批處理機(jī)在線調(diào)度問(wèn)題研究[D];合肥工業(yè)大學(xué);2018年

8 孫恒;基于不相容工件簇的并行機(jī)分批調(diào)度問(wèn)題分析及算法研究[D];吉林大學(xué);2018年

9 馬春風(fēng);基于工件動(dòng)態(tài)到達(dá)的平行批生產(chǎn)調(diào)度優(yōu)化問(wèn)題研究[D];合肥工業(yè)大學(xué);2018年

10 王永青;帶有不相容工件簇的單機(jī)隨機(jī)調(diào)度問(wèn)題研究[D];合肥工業(yè)大學(xué);2017年

本文編號(hào)：2595006