本文關(guān)鍵詞：一些現(xiàn)代排序問題的算法設(shè)計(jì)與分析

  更多相關(guān)文章： 排序 近似算法 可拒絕 不可用時(shí)間約束 自動(dòng)倉儲(chǔ)系統(tǒng)

【摘要】：本論文主要研究了一些現(xiàn)代排序問題,包括帶有拒絕的排序問題、帶有不可用時(shí)間約束的排序問題以及煙草制造行業(yè)中產(chǎn)生的自動(dòng)倉儲(chǔ)系統(tǒng)一軌雙車排序調(diào)度問題。我們研究了這些問題的性質(zhì),對(duì)這些問題分別設(shè)計(jì)了算法,分析了算法的性能比或競(jìng)爭(zhēng)比,并對(duì)一些問題使用數(shù)值模擬驗(yàn)證了算法的有效性,全文共分六章。第一章介紹了組合優(yōu)化問題和排序問題的研究背景,引入了本文涉及的基本概念和定義。對(duì)經(jīng)典排序問題、在線排序問題、帶有拒絕的排序問題和帶有不可用時(shí)間約束的排序問題,分別介紹了目前的研究現(xiàn)狀和研究結(jié)果。第二章研究了帶有拒絕的單機(jī)和同型機(jī)排序問題。對(duì)于帶有拒絕的單機(jī)排序問題,我們研究了懲罰費(fèi)用是對(duì)應(yīng)工件加工時(shí)間α倍的情形。當(dāng)工件有不同的到達(dá)時(shí)間時(shí),目標(biāo)函數(shù)為時(shí)間表長(zhǎng)與懲罰費(fèi)用之和的問題是可解的；當(dāng)所有工件在零時(shí)刻到達(dá)時(shí),目標(biāo)函數(shù)為總完工時(shí)間與懲罰費(fèi)用之和的問題也是可解的。對(duì)于帶有拒絕的同型機(jī)排序問題,我們研究了至多有兩個(gè)到達(dá)時(shí)間的在線情形,對(duì)機(jī)器臺(tái)數(shù)是2和m的情形,分別給出了競(jìng)爭(zhēng)比為2和4—2/m的在線算法。第三章研究了帶有拒絕的兩機(jī)流水作業(yè)排序問題。每個(gè)工件有兩個(gè)操作,每個(gè)操作可以被接受并安排到機(jī)器上加工,或者被拒絕并支付一定的懲罰費(fèi)用。兩臺(tái)機(jī)器上操作的懲罰費(fèi)用分別為對(duì)應(yīng)加工時(shí)間的α1倍和α2倍。目標(biāo)函數(shù)是最小化時(shí)間表長(zhǎng)和懲罰費(fèi)用之和。對(duì)于此問題min{α1,α2}1且max{α1,α2}≥1的情形,我們給出了性能比為4/3的近似算法。對(duì)于α1和α2的一般情形,我們給出了兩個(gè)時(shí)間復(fù)雜度不同的動(dòng)態(tài)規(guī)劃算法,并設(shè)計(jì)了完全多項(xiàng)式時(shí)間近似方案(FPTAS)。第四章研究了帶有不可用時(shí)間約束的單機(jī)半在線排序問題。在此問題中,機(jī)器由于維修或故障等原因,有一個(gè)不可用時(shí)間段,工件無法在此時(shí)間段內(nèi)進(jìn)行加工。工件是在線實(shí)時(shí)到達(dá)的,目標(biāo)函數(shù)是最小化時(shí)間表長(zhǎng)。我們研究了這個(gè)問題的半在線形式,即工件的某些信息在初始時(shí)刻是已知的。對(duì)于已知最大工件的加工時(shí)間、所有工件的加工時(shí)間和、最后工件的到達(dá)時(shí)間、最優(yōu)時(shí)間表長(zhǎng)這四個(gè)半在線問題,我們分別研究了問題的下界,給出了半在線算法,并證明了這些算法的競(jìng)爭(zhēng)比。第五章研究了由煙草制造行業(yè)提出的自動(dòng)倉儲(chǔ)系統(tǒng)一軌雙車排序調(diào)度問題。在這個(gè)系統(tǒng)中有兩臺(tái)堆垛機(jī)運(yùn)行于同一軌道上,兩臺(tái)堆垛機(jī)之間需要保持一定的安全距離。軌道兩側(cè)分別有高層貨架,多個(gè)出／入貨口位于高層貨架的底部。運(yùn)送貨箱的請(qǐng)求由成型機(jī)與發(fā)射機(jī)在線實(shí)時(shí)產(chǎn)生,堆垛機(jī)在機(jī)器與高層貨架之間運(yùn)送貨箱。問題的目標(biāo)是保證系統(tǒng)安全運(yùn)行,滿足生產(chǎn)要求,最小化完成所有請(qǐng)求時(shí)所需要的時(shí)間。這個(gè)問題可以看成是一個(gè)在線排序與路線問題。在給定系統(tǒng)的物理布局下,我們證明了問題的復(fù)雜性。對(duì)于一軌單車模型與一軌雙車模型兩種情形,我們給出了四個(gè)在線控制策略,形成在線算法,并用實(shí)例與數(shù)值模擬驗(yàn)證了在線算法的有效性。算法已經(jīng)投入實(shí)際使用并取得了良好的效果。第六章對(duì)本論文進(jìn)行了總結(jié),介紹了未來可以研究的方向及問題。
【關(guān)鍵詞】：排序 近似算法 可拒絕 不可用時(shí)間約束 自動(dòng)倉儲(chǔ)系統(tǒng)
【學(xué)位授予單位】：華東理工大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2015
【分類號(hào)】：O223
【目錄】：

• 摘要5-7
• Abstract7-11
• 第1章 緒論11-27
• 內(nèi)容提要11
• 1.1 組合優(yōu)化問題11
• 1.2 算法和復(fù)雜性11-15
• 1.3 離線問題與在線問題15-16
• 1.4 排序問題16-18
• 1.5 文獻(xiàn)綜述18-24
• 1.5.1 經(jīng)典排序問題和在線排序問題19-20
• 1.5.2 帶有拒絕的排序問題20-22
• 1.5.3 帶有不可用時(shí)間約束的排序問題22-24
• 1.6 論文概述24-27
• 第2章 帶有拒絕的單機(jī)和同型機(jī)排序問題27-37
• 內(nèi)容提要27
• 2.1 引言27-28
• 2.2 兩個(gè)單機(jī)可解的情形28-30
• 2.3 m臺(tái)同型機(jī)的情形30-37
• 第3章 帶有拒絕的兩機(jī)流水作業(yè)排序問題37-53
• 內(nèi)容提要37
• 3.1 引言37-38
• 3.2 問題性質(zhì)38-39
• 3.3 4/3-近似算法39-43
• 3.4 動(dòng)態(tài)規(guī)劃算法43-50
• 3.5 FPTAS50-53
• 第4章 帶有不可用時(shí)間約束的單機(jī)半在線排序問題53-73
• 內(nèi)容提要53
• 4.1 引言53-55
• 4.2 問題1,h_1|nr-a,r_j,online,p_(max)|C_(max)55-62
• 4.3 問題1,h_1|nr-a,r_j,online,sum|C_(max)62-65
• 4.4 問題1,h_1|nr-a,r_j,online,r_(max)|C_(max)65-68
• 4.5 問題1,h_1|nr-a,r_j,online,opt|C_(max)68-73
• 第5章 一軌雙車自動(dòng)倉儲(chǔ)系統(tǒng)的在線算法設(shè)計(jì)與分析73-91
• 內(nèi)容提要73
• 5.1 引言73-75
• 5.2 問題描述75-77
• 5.3 一軌單車模型77-84
• 5.3.1 指派策略77-78
• 5.3.2 排序策略78-84
• 5.4 一軌雙車模型84-86
• 5.4.1 分配策略84
• 5.4.2 安全策略84-86
• 5.5 實(shí)例與數(shù)值模擬86-91
• 5.5.1 應(yīng)用實(shí)例86-87
• 5.5.2 數(shù)值模擬87-91
• 第6章 結(jié)論與展望91-93
• 參考文獻(xiàn)93-101
• 致謝101-103
• 附錄：博士在讀期間完成的論文103

【共引文獻(xiàn)】

中國(guó)期刊全文數(shù)據(jù)庫 前10條

1 陶玉敏;;無向反轉(zhuǎn)排序問題的遺傳模擬退火求解[J];遼寧科技大學(xué)學(xué)報(bào);2009年04期

2 李琳;白運(yùn);;大地電磁模擬退火反演研究[J];安陽工學(xué)院學(xué)報(bào);2011年02期

3 賈煜亮;繆立新;;自動(dòng)化立體倉庫中貨位實(shí)時(shí)分配優(yōu)化問題研究[J];北京交通大學(xué)學(xué)報(bào)(社會(huì)科學(xué)版);2007年04期

4 曹守華;袁振洲;韓寶明;李得偉;;基于SOFM神經(jīng)網(wǎng)絡(luò)的客運(yùn)一體化樞紐分類[J];北京交通大學(xué)學(xué)報(bào);2008年06期

5 黎浩東;何世偉;宋瑞;紀(jì)麗君;申永生;;列車編組計(jì)劃和技術(shù)站布局的綜合優(yōu)化[J];北京交通大學(xué)學(xué)報(bào);2010年06期

6 趙博文;余永剛;潘玉竹;;隨行裝藥退火算法的優(yōu)化設(shè)計(jì)及數(shù)值模擬[J];火炸藥學(xué)報(bào);2010年05期

7 夏志安;趙英俊;;基于遺傳算法的裝備器件更換周期優(yōu)化模型[J];兵工自動(dòng)化;2008年08期

8 王文峰;劉亞杰;郭波;;戰(zhàn)役裝備維修保障網(wǎng)絡(luò)設(shè)計(jì)問題研究[J];兵工學(xué)報(bào);2008年12期

9 陳云霞;高潔萍;夏華鳳;曾聲奎;;基于遺傳算法的多學(xué)科設(shè)計(jì)優(yōu)化分解方法[J];北京航空航天大學(xué)學(xué)報(bào);2009年06期

10 李少保;趙春曉;;基于多Agent遺傳算法求解迷宮游戲[J];北京建筑工程學(xué)院學(xué)報(bào);2011年03期

中國(guó)博士學(xué)位論文全文數(shù)據(jù)庫 前10條

1 李佳;載人潛器阻力性能的數(shù)值和試驗(yàn)預(yù)報(bào)及外形優(yōu)化研究[D];哈爾濱工程大學(xué);2010年

2 宋越明;基于粒子濾波的跟蹤方法研究[D];解放軍信息工程大學(xué);2010年

3 王曉娟;多目標(biāo)柔性作業(yè)車間調(diào)度方法研究[D];華中科技大學(xué);2011年

4 程文濤;關(guān)節(jié)式坐標(biāo)測(cè)量機(jī)標(biāo)定技術(shù)研究[D];合肥工業(yè)大學(xué);2011年

5 王聯(lián)國(guó);人工魚群算法及其應(yīng)用研究[D];蘭州理工大學(xué);2009年

6 陳雪;太陽能熱光伏系統(tǒng)機(jī)理與實(shí)驗(yàn)研究[D];南京理工大學(xué);2010年

7 王筱蓉;沖壓增程炮彈進(jìn)氣道型面氣動(dòng)優(yōu)化方法研究[D];南京理工大學(xué);2010年

8 繆濵;公（鐵）工程三維選線的群智能算法研究[D];中南大學(xué);2011年

9 張恒;無線接入網(wǎng)中無線下行覆蓋自優(yōu)化和自主負(fù)載均衡方法[D];北京郵電大學(xué);2011年

10 查靚;精益生產(chǎn)方式下U型流水線平衡的優(yōu)化模型與算法研究[D];華南理工大學(xué);2011年

中國(guó)碩士學(xué)位論文全文數(shù)據(jù)庫 前10條

1 吳家瑞;服裝產(chǎn)品加工成本快速估算方法研究[D];浙江理工大學(xué);2010年

2 周宇龍;基于遺傳算法的堤防材料動(dòng)力特性反演分析[D];鄭州大學(xué);2010年

3 王斌;淺層地表缺陷動(dòng)力探測(cè)技術(shù)研究[D];鄭州大學(xué);2010年

4 石麗麗;智能優(yōu)化算法對(duì)比研究及其在船體雙底結(jié)構(gòu)優(yōu)化中的應(yīng)用[D];哈爾濱工程大學(xué);2010年

5 王宏云;基于數(shù)據(jù)挖掘的煤礦安全監(jiān)測(cè)系統(tǒng)研究[D];遼寧工程技術(shù)大學(xué);2009年

6 高婷;智能天線系統(tǒng)中的動(dòng)態(tài)信道分配算法研究[D];遼寧工程技術(shù)大學(xué);2010年

7 李天贊;神經(jīng)網(wǎng)絡(luò)在電力系統(tǒng)諧波分析中的應(yīng)用研究[D];長(zhǎng)沙理工大學(xué);2009年

8 劉子文;改進(jìn)的粒子群算法在停車場(chǎng)中的應(yīng)用[D];湘潭大學(xué);2010年

9 余勇;我國(guó)建設(shè)工程招投標(biāo)管理機(jī)制研究[D];湘潭大學(xué);2010年

10 盛大寧;IMRT逆向計(jì)劃中的混合多目標(biāo)梯度算法研究[D];合肥工業(yè)大學(xué);2010年

，

本文編號(hào)：680207