調(diào)度問題是組合優(yōu)化、計(jì)算機(jī)科學(xué)、管理科學(xué)等領(lǐng)域的經(jīng)典問題之一,其研究?jī)?nèi)容是指在滿足一定約束的前提下,將一定時(shí)間內(nèi)的不同任務(wù)分配給有限的處理機(jī),以優(yōu)化一至多個(gè)目標(biāo)。眾多優(yōu)化目標(biāo)之中,任務(wù)的誤工損失是一個(gè)與其交付期有關(guān)的懲罰量,等于其滯后于交付期加工的部分。以最小化任務(wù)誤工損失為優(yōu)化目標(biāo)的調(diào)度問題于1984年提出,已被持續(xù)研究超過30年。在前人基礎(chǔ)上,本文繼續(xù)研究了該類問題的若干形式,并利用精確算法、近似算法、元啟發(fā)式算法等主流方法對(duì)它們進(jìn)行求解。主要成果包括:(1)研究了同型機(jī)環(huán)境下、帶公共交付期的最小化誤工損失問題。通過理論分析表明當(dāng)處理機(jī)數(shù)量作為參數(shù)之一的情況下,該問題是強(qiáng)NP難問題;針對(duì)兩臺(tái)同型機(jī)的特殊情況,提出了一種偽多項(xiàng)式時(shí)間動(dòng)態(tài)規(guī)劃算法,從而證明在該情況下問題的復(fù)雜性降為弱NP難;隨后,證明最大處理時(shí)間優(yōu)先算法(LPT算法)的近似比為10。(2)將上述問題擴(kuò)展到非公共交付期的形式。通過定義解的表達(dá)方式、上下界計(jì)算方法以及支配規(guī)則等,提出了一種求解兩臺(tái)同型機(jī)問題的分支定界算法;同時(shí),利用任務(wù)劃分思想,提出了一種求解上述問題的窮舉算法;當(dāng)處理機(jī)數(shù)量為m(m≥ 2)時(shí),提出了一種遺...

【文章頁數(shù)】：117 頁

【學(xué)位級(jí)別】：博士

【文章目錄】：
摘要
ABSTRACT
主要符號(hào)表
1 緒論
    1.1 調(diào)度問題及其表示方法
        1.1.1 問題概述
        1.1.2 調(diào)度問題三參數(shù)表示法
        1.1.3 離線、在線、半在線調(diào)度
    1.2 復(fù)雜性理論
    1.3 求解復(fù)雜問題的算法分類及評(píng)估方法
        1.3.1 精確算法
        1.3.2 基于質(zhì)量保證的近似算法
        1.3.3 基于數(shù)值實(shí)驗(yàn)的啟發(fā)式算法
    1.4 以誤工損失為優(yōu)化目標(biāo)的調(diào)度問題研究現(xiàn)狀
        1.4.1 單機(jī)調(diào)度問題研究情況
        1.4.2 平行機(jī)調(diào)度問題研究情況
        1.4.3 串聯(lián)機(jī)調(diào)度問題研究情況
    1.5 論文主要貢獻(xiàn)及組織結(jié)構(gòu)
2 帶公共交付期的同型機(jī)調(diào)度問題
    2.1 P|dj=d|Y問題的復(fù)雜性研究
    2.2 求解P2|d_j=d|Y問題的若干算法
        2.2.1 偽多項(xiàng)式時(shí)間的動(dòng)態(tài)規(guī)劃算法
        2.2.2 指數(shù)時(shí)間的窮舉算法
        2.2.3 多項(xiàng)式時(shí)間的近似算法
    2.3 數(shù)值實(shí)驗(yàn)
        2.3.1 實(shí)驗(yàn)數(shù)據(jù)集及測(cè)試平臺(tái)
        2.3.2 結(jié)果分析
    2.4 本章小結(jié)
3 非公共交付期的同型機(jī)調(diào)度問題
    3.1 求解P2||Y問題的分支定界算法
        3.1.1 解的編碼方式及搜索樹結(jié)構(gòu)
        3.1.2 全局上界獲取及更新方法
        3.1.3 局部解下界計(jì)算方法
        3.1.4 節(jié)點(diǎn)間的支配規(guī)則
        3.1.5 B&B算法整體結(jié)構(gòu)
    3.2 求解P2||Y問題的窮舉算法
    3.3 求解Pm||Y問題的遺傳算法
        3.3.1 染色體初始化
        3.3.2 交叉操作
        3.3.3 變異操作
        3.3.4 GA算法整體結(jié)構(gòu)
    3.4 數(shù)值實(shí)驗(yàn)
        3.4.1 實(shí)驗(yàn)數(shù)據(jù)集及測(cè)試平臺(tái)
        3.4.2 小規(guī)模實(shí)例測(cè)試結(jié)果分析
        3.4.3 大規(guī)模實(shí)例測(cè)試結(jié)果分析
    3.5 本章小結(jié)
4 流水作業(yè)調(diào)度問題
    4.1 F3|d_j=d|Y問題的復(fù)雜性研究
    4.2 求解Fm|LE|Y問題的粒子群算法
        4.2.1 考慮學(xué)習(xí)效應(yīng)的調(diào)度問題
        4.2.2 Fm|LE|Y問題描述
        4.2.3 PSO算法設(shè)計(jì)
        4.2.4 PSO算法整體結(jié)構(gòu)
    4.3 數(shù)值實(shí)驗(yàn)
        4.3.1 實(shí)驗(yàn)數(shù)據(jù)集及測(cè)試平臺(tái)
        4.3.2 結(jié)果分析
    4.4 本章小結(jié)
5 半在線調(diào)度問題
    5.1 競(jìng)爭(zhēng)比分析方案
    5.2 P2|online,SUM&MAX,d_j=d|Y問題
        5.2.1 問題定義
        5.2.2 ALGO_SM算法及其競(jìng)爭(zhēng)比分析
        5.2.3 問題下界
    5.3 P2|online,MAX,d_j=d|Y問題
        5.3.1 問題定義
        5.3.2 ALGO_M算法及其競(jìng)爭(zhēng)比分析
        5.3.3 問題下界
    5.4 本章小結(jié)
6 結(jié)論與展望
    6.1 結(jié)論
    6.2 創(chuàng)新點(diǎn)
    6.3 展望
參考文獻(xiàn)
攻讀博士學(xué)位期間科研項(xiàng)目及科研成果
致謝
作者簡(jiǎn)介



本文編號(hào)：3841353