鋼鐵工業(yè)是國(guó)民經(jīng)濟(jì)的重要支柱產(chǎn)業(yè)之一。近年來(lái),隨著建筑業(yè)、汽車(chē)制造業(yè)、造船業(yè)和家電業(yè)的大力發(fā)展,對(duì)鋼材的需求數(shù)量和質(zhì)量提出了更高的要求。由于鋼鐵生產(chǎn)具有多階段、物件帶有高溫連續(xù)運(yùn)作、物流呈交叉網(wǎng)狀結(jié)構(gòu)等特點(diǎn),這就決定了物件在工序上的生產(chǎn)調(diào)度、連接工序之間的運(yùn)輸物流調(diào)度以及生產(chǎn)和物流調(diào)度的銜接都有嚴(yán)格的要求。合理進(jìn)行生產(chǎn)和物流調(diào)度,有利于鋼鐵工業(yè)工序之間的物料緊湊銜接、減少中間等待時(shí)間,從而降低能耗、提高大型裝置的設(shè)備利用率,達(dá)到降低生產(chǎn)和物流的綜合成本、提高產(chǎn)品質(zhì)量、提高鋼鐵工業(yè)競(jìng)爭(zhēng)力的目的。 本文以鋼鐵企業(yè)的高能耗的煉鋼和初軋為背景,分別從這兩個(gè)工序中提煉出具有熱鏈物流特征的生產(chǎn)和運(yùn)輸調(diào)度問(wèn)題,進(jìn)行理論研究。基于復(fù)雜性分析、算法最壞情況分析、多項(xiàng)式時(shí)間算法、近似策略、動(dòng)態(tài)規(guī)劃等多種技術(shù)手段,主要研究三個(gè)方面的問(wèn)題：具有惡化特征的生產(chǎn)調(diào)度問(wèn)題、生產(chǎn)和運(yùn)輸協(xié)調(diào)調(diào)度問(wèn)題、考慮惡化特征的生產(chǎn)運(yùn)輸協(xié)調(diào)調(diào)度問(wèn)題。 具體內(nèi)容概括如下： 1)具有惡化特征的生產(chǎn)調(diào)度問(wèn)題研究 (1)從鋼錠在均熱爐中加熱的過(guò)程中提煉出工件帶有釋放時(shí)間和惡化特征的批處理機(jī)調(diào)度問(wèn)題,其中工件在批處理機(jī)上的加工時(shí)間是工件在批處理機(jī)前的等待時(shí)間的一個(gè)分段函數(shù),目標(biāo)函數(shù)為最大完成時(shí)間的最小化。證明了該問(wèn)題是NP-難問(wèn)題。分別從相同的釋放時(shí)間、批處理機(jī)能力無(wú)限以及工件具有優(yōu)先次序三個(gè)方面,研究了三種特殊情況的多項(xiàng)式時(shí)間算法。 (2)從模鑄到均熱的生產(chǎn)過(guò)程提煉出了并行機(jī)和批處理機(jī)兩階段生產(chǎn)的惡化調(diào)度問(wèn)題,其中工件的惡化是指工件在批處理機(jī)上的加工時(shí)間與工件在兩階段之間的等待時(shí)間有關(guān)。目標(biāo)函數(shù)既考慮了兩階段生產(chǎn)的機(jī)器利用率,又考慮了批處理機(jī)的空載懲罰,即為最大完成時(shí)間和批處理機(jī)空余的懲罰費(fèi)用之和的最小化。對(duì)于這個(gè)問(wèn)題,證明了強(qiáng)NP-難性,提出了一個(gè)啟發(fā)式算法,理論上分析了算法的最壞情況性能,并通過(guò)數(shù)值仿真實(shí)驗(yàn),驗(yàn)證了算法性能的有效性。 2)生產(chǎn)和運(yùn)輸協(xié)調(diào)調(diào)度問(wèn)題研究 (1)從鋼錠的運(yùn)輸以及均熱的過(guò)程受到啟發(fā),提煉出了多個(gè)臺(tái)車(chē)生產(chǎn)前運(yùn)輸與批處理機(jī)生產(chǎn)的協(xié)調(diào)調(diào)度問(wèn)題。目標(biāo)函數(shù)為工件總完成時(shí)間與批處理機(jī)啟動(dòng)費(fèi)用之和的最小化。首先利用劃分問(wèn)題證明了該問(wèn)題是NP-難的,通過(guò)動(dòng)態(tài)規(guī)劃提出的偽多項(xiàng)式時(shí)間算法證明了該問(wèn)題是一般意義NP-難問(wèn)題。最后提出了解決問(wèn)題的全多項(xiàng)式時(shí)間近似策略。而當(dāng)工件在臺(tái)車(chē)上的分配給定時(shí),通過(guò)動(dòng)態(tài)規(guī)劃給出了多項(xiàng)式時(shí)間的最優(yōu)算法。 (2)從模鑄到均熱的生產(chǎn)和運(yùn)輸中提煉出了二機(jī)之間帶有運(yùn)輸考慮的二機(jī)流水調(diào)度問(wèn)題,其中在運(yùn)輸?shù)倪^(guò)程中考慮工件是否占有不同的物理空間兩種情況。目標(biāo)函數(shù)為最大完成時(shí)間的最小化。對(duì)于工件體積相同的情況,給出了最壞情況性能比為2的啟發(fā)式算法。對(duì)于工件體積不相同的情況,給出了最壞情況性能比為7/3的啟發(fā)式算法。 (3)從均熱到初軋的生產(chǎn)過(guò)程提煉出了帶有阻滯和運(yùn)輸時(shí)間考慮的兩階段生產(chǎn)調(diào)度問(wèn)題,工件先在第一階段批處理機(jī)上進(jìn)行生產(chǎn),當(dāng)?shù)诙A段的單機(jī)有空閑時(shí)才可以運(yùn)輸?shù)降诙A段進(jìn)行生產(chǎn),如果單機(jī)不可利用,則批處理機(jī)上形成了阻滯。目標(biāo)函數(shù)既考慮了工件的最大完成時(shí)間,又考慮了工件在批處理機(jī)上的總阻滯時(shí)間。對(duì)于總的阻滯時(shí)間的最小化問(wèn)題,給出了多項(xiàng)式時(shí)間的最優(yōu)算法。對(duì)于最大完成時(shí)間最小化問(wèn)題,給出了強(qiáng)NP-難的證明,提出最壞情況性能比為2的啟發(fā)式算法,實(shí)驗(yàn)結(jié)果證明了算法的有效性。對(duì)于最大完成時(shí)間和總阻滯時(shí)間的線性組合最小化問(wèn)題,提出了混合整數(shù)規(guī)劃模型,給出了強(qiáng)NP-難的證明,提出了啟發(fā)式算法,并且從理論分析與實(shí)驗(yàn)結(jié)果兩個(gè)方面驗(yàn)證了算法的有效性。 (4)從初軋生產(chǎn)到成品運(yùn)輸?shù)倪^(guò)程提煉出了并行機(jī)生產(chǎn)與成品運(yùn)輸?shù)膮f(xié)調(diào)調(diào)度問(wèn)題。目標(biāo)函數(shù)為工件總完成時(shí)間與運(yùn)輸費(fèi)用之和的最小化。根據(jù)問(wèn)題所滿足的性質(zhì),通過(guò)過(guò)程劃分及動(dòng)態(tài)規(guī)劃給出了解決問(wèn)題的偽多項(xiàng)式時(shí)間算法,并且證明該問(wèn)題是一般意義NP-難問(wèn)題。對(duì)于工件在并行機(jī)上的分配給定的特殊情況,提出了多項(xiàng)式時(shí)間的最優(yōu)算法。 (5)從鋼錠在均熱爐加熱的前后生產(chǎn)過(guò)程提煉出了批處理機(jī)上生產(chǎn)與生產(chǎn)前后兩階段運(yùn)輸?shù)膮f(xié)調(diào)調(diào)度問(wèn)題。目標(biāo)函數(shù)為工件的最大完成時(shí)間與批處理機(jī)啟動(dòng)費(fèi)用之和的最小化。提出了問(wèn)題的混合整數(shù)規(guī)劃模型,給出了強(qiáng)NP-難證明。并且提出了最壞情況性能比為2的啟發(fā)式算法,實(shí)驗(yàn)結(jié)果證明了算法的有效性。對(duì)于工件的加工次序確定的情況,給出了多項(xiàng)式時(shí)間的最優(yōu)算法。 3)考慮惡化特征的生產(chǎn)運(yùn)輸協(xié)調(diào)調(diào)度問(wèn)題研究 從均熱車(chē)間中提煉出了工件生產(chǎn)前的運(yùn)輸以及批處理機(jī)生產(chǎn)的協(xié)調(diào)調(diào)度問(wèn)題,其中也考慮了工件在批處理機(jī)的生產(chǎn)的惡化特征,這里的惡化是指工件在批處理機(jī)上的加工時(shí)間是關(guān)于工件的暴露時(shí)間的分段函數(shù)。目標(biāo)函數(shù)為最大完成時(shí)間和批處理機(jī)的啟動(dòng)費(fèi)用之和的最小化。證明了問(wèn)題的一般情況以及批的數(shù)量受限的情況都是強(qiáng)NP-難問(wèn)題,給出了啟發(fā)式算法,并且進(jìn)行了最壞情況性能比分析,實(shí)驗(yàn)結(jié)果也驗(yàn)證的算法的有效性。對(duì)于工件的完成時(shí)間受限的情況,證明了該問(wèn)題也是強(qiáng)NP-難問(wèn)題。對(duì)于工件的加工順序給定的情況,給出了多項(xiàng)式時(shí)間最優(yōu)算法。
【學(xué)位單位】：東北大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位年份】：2009
【中圖分類】：F273;F426.31;F224
【文章目錄】：
摘要
Abstract
目錄
第一章 緒論
    1.1 問(wèn)題的研究目的及意義
        1.1.1 問(wèn)題來(lái)源及研究目的
        1.1.2 問(wèn)題背景及研究意義
    1.2 調(diào)度問(wèn)題的一般理論方法
        1.2.1 調(diào)度問(wèn)題的概述
        1.2.2 計(jì)算復(fù)雜性
        1.2.3 近似算法
        1.2.4 近似策略
        1.2.5 動(dòng)態(tài)規(guī)劃和整數(shù)規(guī)劃
    1.3 調(diào)度問(wèn)題的研究現(xiàn)狀
        1.3.1 批處理機(jī)調(diào)度問(wèn)題的研究現(xiàn)狀
        1.3.2 具有惡化特征的調(diào)度問(wèn)題的研究現(xiàn)狀
        1.3.3 生產(chǎn)運(yùn)輸協(xié)調(diào)物流調(diào)度問(wèn)題的研究現(xiàn)狀
        1.3.4 本文研究的調(diào)度問(wèn)題的創(chuàng)新點(diǎn)
    1.4 本文的研究路線及主要工作
        1.4.1 本文的研究路線
        1.4.2 本文的主要工作
第二章 工件帶有釋放時(shí)間的單個(gè)批處理機(jī)的惡化調(diào)度問(wèn)題
    2.1 引言
    2.2 復(fù)雜性分析
    2.3 特殊情況
j=r,a_j|C_max'>        2.3.1 問(wèn)題B|c,r_j=r,a_j|Cmax

        2.3.2 問(wèn)題B|c=∞,r_j,a_j|C_max

        2.3.3 問(wèn)題B|c,r_j,a_j,（?）|C_max

    2.4 小結(jié)
第三章 帶有惡化特征的并行機(jī)與批處理機(jī)的兩階段調(diào)度問(wèn)題
    3.1 引言
    3.2 問(wèn)題描述
    3.3 復(fù)雜性分析
    3.4 啟發(fā)式算法及性能比分析
    3.5 實(shí)驗(yàn)結(jié)果與數(shù)值計(jì)算
    3.6 小結(jié)
第四章 多個(gè)臺(tái)車(chē)運(yùn)輸與批處理機(jī)生產(chǎn)的協(xié)調(diào)調(diào)度問(wèn)題
    4.1 引言
    4.2 問(wèn)題描述
    4.3 復(fù)雜性分析
    4.4 偽多項(xiàng)式時(shí)間算法
    4.5 全多項(xiàng)式時(shí)間近似策略（FPTAS）
    4.6 特殊情況
    4.7 小結(jié)
第五章 帶有運(yùn)輸考慮的二機(jī)流水調(diào)度問(wèn)題
    5.1 引言
2|s_j=1|C_max'>    5.2 問(wèn)題TF₂|s_j=1|C_max

    5.3 問(wèn)題TF₂|s_j|C_max

    5.4 小結(jié)
第六章 帶有阻滯和運(yùn)輸時(shí)間考慮的兩階段流水調(diào)度問(wèn)題
    6.1 引言
    6.2 問(wèn)題描述
    6.3 混合整數(shù)規(guī)劃模型
    6.4 復(fù)雜性分析
    6.5 特殊情況
    6.6 啟發(fā)式算法及性能比分析
    6.7 實(shí)驗(yàn)結(jié)果與數(shù)值計(jì)算
    6.8 小結(jié)
第七章 兩個(gè)并行機(jī)與批運(yùn)輸?shù)膮f(xié)調(diào)調(diào)度
    7.1 引言
j+Dy'>    7.2 問(wèn)題P2|T|∑C_j+Dy
    7.3 特殊情況
    7.4 小結(jié)
第八章 兩階段運(yùn)輸與批處理機(jī)生產(chǎn)的協(xié)調(diào)調(diào)度問(wèn)題
    8.1 引言
    8.2 問(wèn)題描述
    8.3 混合整數(shù)規(guī)劃模型
    8.4 復(fù)雜性分析
    8.5 特殊情況
    8.6 啟發(fā)式算法及性能分析
    8.7 實(shí)驗(yàn)結(jié)果與數(shù)值計(jì)算
    8.8 小結(jié)
第九章 帶有惡化特征的運(yùn)輸和批處理機(jī)生產(chǎn)的協(xié)調(diào)調(diào)度問(wèn)題
    9.1 引言
    9.2 問(wèn)題描述
    9.3 文獻(xiàn)綜述
    9.4 復(fù)雜性分析
    9.5 多項(xiàng)式時(shí)間可解情況
    9.6 啟發(fā)式算法及分析
    9.7 實(shí)驗(yàn)結(jié)果與數(shù)值計(jì)算
    9.8 小結(jié)
第十章 結(jié)束語(yǔ)
參考文獻(xiàn)
致謝
作者博士期間發(fā)表和錄用的論文
作者博士期間科研情況
個(gè)人簡(jiǎn)歷

【共引文獻(xiàn)】

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

1 齊學(xué)梅;;無(wú)等待流水調(diào)度問(wèn)題迭代啟發(fā)式算法[J];安徽師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2009年01期

2 郭永輝;錢(qián)省三;;晶圓復(fù)雜制造系統(tǒng)在線優(yōu)化調(diào)度系統(tǒng)研究[J];半導(dǎo)體技術(shù);2007年04期

3 卓奕君;成曄;;面向大型產(chǎn)品裝配的兩維勢(shì)能調(diào)度算法研究[J];北京信息科技大學(xué)學(xué)報(bào)(自然科學(xué)版);2009年04期

4 崔建雙,李鐵克,張文新;混合流水車(chē)間調(diào)度模型及其遺傳算法[J];北京科技大學(xué)學(xué)報(bào);2005年05期

5 李裕梅;谷云東;李洪興;;調(diào)度問(wèn)題Pm|p_j=1,intree|∑C_j的兩個(gè)啟發(fā)式算法[J];北京師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2006年02期

6 袁芬;谷云東;塵非;;關(guān)于模糊工期平行機(jī)調(diào)度問(wèn)題的若干結(jié)果[J];北京師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2006年03期

7 孫秀平;谷云東;李洪興;;任務(wù)無(wú)準(zhǔn)備時(shí)間最小化加權(quán)最大延誤單機(jī)調(diào)度問(wèn)題的若干結(jié)果[J];北京師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2006年05期

8 程貞敏;李洪興;;允許中斷的同速機(jī)調(diào)度問(wèn)題的一個(gè)最優(yōu)算法[J];北京師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2008年05期

9 程貞敏;李洪興;谷敏強(qiáng);;最小化時(shí)間表長(zhǎng)的平行機(jī)調(diào)度近似算法研究[J];北京師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2012年01期

10 張淑娟;楊明明;韓翔凌;;帶學(xué)習(xí)效應(yīng)的供應(yīng)鏈排序算法研究[J];濱州學(xué)院學(xué)報(bào);2010年06期

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

1 ;A Scheduling Problem on a Single Batching Machine with Batch Deliveries[A];中國(guó)自動(dòng)化學(xué)會(huì)控制理論專業(yè)委員會(huì)D卷[C];2011年

2 ;On-line Scheduling with Rejection on Uniform Machines[A];中國(guó)運(yùn)籌學(xué)會(huì)第七屆學(xué)術(shù)交流會(huì)論文集（中卷）[C];2004年

3 柏慶國(guó);張玉忠;;有尺寸的單機(jī)在線分批排序[A];中國(guó)運(yùn)籌學(xué)會(huì)第七屆學(xué)術(shù)交流會(huì)論文集（中卷）[C];2004年

4 張玉忠;;分批排序問(wèn)題研究[A];中國(guó)運(yùn)籌學(xué)會(huì)第七屆學(xué)術(shù)交流會(huì)論文集（中卷）[C];2004年

5 張樹(shù)霞;曹志剛;張玉忠;;極小化最大完工時(shí)間的離散可控排序(英文)[A];中國(guó)運(yùn)籌學(xué)會(huì)第八屆學(xué)術(shù)交流會(huì)論文集[C];2006年

6 聞?wù)裥l(wèi);;一類平行機(jī)上的任務(wù)指派問(wèn)題及其動(dòng)態(tài)規(guī)劃算法[A];中國(guó)運(yùn)籌學(xué)會(huì)第九屆學(xué)術(shù)交流會(huì)論文集[C];2008年

7 陳榮軍;唐國(guó)春;;自由作業(yè)環(huán)境下的供應(yīng)鏈排序問(wèn)題[A];中國(guó)運(yùn)籌學(xué)會(huì)第九屆學(xué)術(shù)交流會(huì)論文集[C];2008年

8 王錚;周嵬;蔡砥;;設(shè)施區(qū)位:一個(gè)重要的科學(xué)問(wèn)題[A];中國(guó)法學(xué)會(huì)經(jīng)濟(jì)法學(xué)研究會(huì)2005年年會(huì)專輯[C];2005年

9 ;Batch Delivery Scheduling with Limited Waiting Time Constraint on a Single Machine[A];2009中國(guó)控制與決策會(huì)議論文集（2）[C];2009年

10 ;Production-Transportation Scheduling Model on a Single Batching Machine[A];2009中國(guó)控制與決策會(huì)議論文集（2）[C];2009年

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

1 馬英;考慮維護(hù)時(shí)間的機(jī)器調(diào)度問(wèn)題研究[D];合肥工業(yè)大學(xué);2010年

2 李先鋒;基于特征優(yōu)化和多特征融合的雜草識(shí)別方法研究[D];江蘇大學(xué);2010年

3 鐘雪靈;帶強(qiáng)制工期非正則目標(biāo)函數(shù)的排序問(wèn)題研究[D];暨南大學(xué);2010年

4 楊開(kāi)兵;基于進(jìn)化計(jì)算的多目標(biāo)流水車(chē)間批組調(diào)度問(wèn)題研究[D];大連理工大學(xué);2011年

5 苗翠霞;分批排序及資源約束排序中若干問(wèn)題[D];曲阜師范大學(xué);2011年

6 柳春鋒;工程項(xiàng)目中技能型員工調(diào)度問(wèn)題研究[D];合肥工業(yè)大學(xué);2011年

7 黎潔;容遲移動(dòng)傳感器網(wǎng)絡(luò)中數(shù)據(jù)傳輸與數(shù)據(jù)管理機(jī)制的研究[D];中國(guó)科學(xué)技術(shù)大學(xué);2011年

8 許瑞;基于蟻群優(yōu)化算法的批調(diào)度問(wèn)題研究[D];中國(guó)科學(xué)技術(shù)大學(xué);2011年

9 杜冰;批處理機(jī)調(diào)度問(wèn)題的模型與優(yōu)化方法研究[D];中國(guó)科學(xué)技術(shù)大學(xué);2011年

10 王磊;面向訂單生產(chǎn)的供應(yīng)鏈排序問(wèn)題研究[D];暨南大學(xué);2011年

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

1 張瑋虹;生產(chǎn)管理中的若干排序問(wèn)題[D];浙江理工大學(xué);2010年

2 吳麗華;服裝零售供應(yīng)配送中的若干問(wèn)題研究[D];浙江理工大學(xué);2010年

3 任立莉;可拒絕平行批平行機(jī)與在線平行批兩臺(tái)一致機(jī)排序[D];鄭州大學(xué);2010年

4 孟令玉;基于網(wǎng)絡(luò)流的開(kāi)放式車(chē)間調(diào)度問(wèn)題研究[D];哈爾濱工程大學(xué);2010年

5 孫慧杰;碼頭泊位延遲問(wèn)題的干擾管理模型研究[D];大連理工大學(xué);2010年

6 周雁;基于遺傳和粒子群優(yōu)化算法的軟硬件劃分方法研究[D];華東師范大學(xué);2011年

7 王悅;存在批處理設(shè)備的復(fù)雜產(chǎn)品調(diào)度研究[D];哈爾濱理工大學(xué);2010年

8 于慶蓮;基于靜態(tài)并行時(shí)間確定可增加瓶頸設(shè)備的研究[D];哈爾濱理工大學(xué);2010年

9 蘇勝龍;帶一個(gè)服務(wù)器的兩臺(tái)平行機(jī)半在線排序問(wèn)題[D];華東理工大學(xué);2011年

10 牟啟燕;帶一個(gè)服務(wù)器的兩臺(tái)機(jī)器自由作業(yè)排序問(wèn)題的近似算法[D];華東理工大學(xué);2011年

本文編號(hào)：2828564

boshi