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

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

【學位級別】：博士

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



本文編號：3841353