本論文主要從算法設(shè)計(jì)與分析的角度,對(duì)機(jī)器有使用限制的排序問題進(jìn)行了研究。我們首先考慮了機(jī)器有不可用時(shí)間限制的排序問題,然后研究了既有加工,又有運(yùn)輸?shù)臋C(jī)器有不可用時(shí)間限制的供應(yīng)鏈排序問題。我們主要從離線和在線兩個(gè)方面考慮機(jī)器有使用限制的排序問題。目標(biāo)函數(shù)主要有最小化最大完工時(shí)間,最小化完工時(shí)間和,最小化最大運(yùn)輸時(shí)間與最小化運(yùn)輸時(shí)間和。全文由六個(gè)部分組成,第一章首先給出了組合優(yōu)化和排序問題的基本概念,然后介紹了機(jī)器有不可用時(shí)間限制的排序問題的研究近況,以及有加工和運(yùn)輸?shù)墓⿷?yīng)鏈排序問題的一些概念和研究進(jìn)展。第二章首先研究了單臺(tái)機(jī)器有一個(gè)不可用時(shí)間限制的排序問題,目標(biāo)為最小化最大完工時(shí)間。對(duì)于這個(gè)問題,我們?cè)O(shè)計(jì)了一個(gè)4/3近似算法和一個(gè)動(dòng)態(tài)規(guī)劃算法,并給出了一個(gè)競(jìng)爭(zhēng)比為2的最優(yōu)在線算法。然后,我們研究了單臺(tái)機(jī)器帶一個(gè)不可用時(shí)間限制的排序問題,目標(biāo)為最小化完工時(shí)間和。對(duì)于這個(gè)問題,我們?cè)O(shè)計(jì)了一個(gè)時(shí)間復(fù)雜性為O（n log n）的算法,并證明了該算法的性能比為17/15。第三章考慮了兩臺(tái)機(jī)器的排序問題,其中一臺(tái)機(jī)器有一個(gè)不可用時(shí)間限制,而另一臺(tái)機(jī)器一直可用,工件在加工過程中不可恢復(fù),其目標(biāo)為最小化... 

【文章來源】：華東理工大學(xué)上海市 211工程院校 教育部直屬院校

【文章頁(yè)數(shù)】：101 頁(yè)

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

【文章目錄】：
摘要
Abstract
第1章 緒論
    1.1 組合優(yōu)化問題
    1.2 算法和計(jì)算復(fù)雜性
    1.3 排序問題概述
    1.4 文獻(xiàn)綜述
        1.4.1 經(jīng)典排序問題和在線排序問題
        1.4.2 機(jī)器有不可用時(shí)間限制的排序問題
        1.4.3 機(jī)器有不可用時(shí)間限制的加工與運(yùn)輸問題
    1.5 論文概述
第2章 單臺(tái)機(jī)器有一個(gè)不可用時(shí)間限制的排序問題
    2.1 引言
    2.2 問題1,h_1|nr,r_j|C_(max)
    2.3 問題1,h_1|nr,r_j,online|C_(max)
    2.4 問題1,h_1|nr|∑G_j
第3章 兩臺(tái)機(jī)器有一個(gè)不可用時(shí)間限制的排序問題
    3.1 引言
    3.2 2-近似算法
    3.3 動(dòng)態(tài)規(guī)劃算法
    3.4 FPTAS
第4章 兩臺(tái)機(jī)器有周期性不可用時(shí)間限制的排序問題
    4.1 引言
    4.2 工件不可恢復(fù)的情形
    4.3 工件可恢復(fù)的情形
        4.3.1 問題最優(yōu)值的一個(gè)下界
        4.3.2 近似算法
    4.4 工件可恢復(fù)的在線問題
第5章 單臺(tái)機(jī)器有一個(gè)不可用時(shí)間限制的加工與運(yùn)輸問題
    5.1 引言
    5.2 問題1,h_1|P→D,v(1,z)|D_(max)
    5.3 問題1,h_1|D→P,v(1,z)|C_(max)
    5.4 問題1,h_1|P→D,v(1,z)|∑D_j
第6章 單臺(tái)機(jī)器有周期性不可用時(shí)間限制的加工與運(yùn)輸問題
    6.1 引言
    6.2 問題1,PU|P→D,v(1,z)|D_(max)
    6.3 問題1,PU|D→P,v(1,z)|C_(max)
第7章 總結(jié)與展望
參考文獻(xiàn)
致謝
附錄：博士在讀期間完成的論文



本文編號(hào)：3570355