排序是指在一定的約束條件下分配有限的資源于時間空間去完成多項任務(wù)使得一個或者多個目標(biāo)達到理想或最優(yōu).排序的好壞直接影響著生產(chǎn)商成本的高低和利潤的大小.因此,排序論對提高效率、科學(xué)決策、資源的開發(fā)與配置等方面都起到重要的作用.在排序論中,人們把任務(wù)統(tǒng)稱為“工件”,而把資源統(tǒng)稱為“機器”.本學(xué)位論文主要研究了若干新型排序問題的計算復(fù)雜性.在第二章中,我們研究了 GDD或ADD假設(shè)下的單機排序.在GDD假設(shè)下,工期按照EDD順序進行排列,并按照工件完工時間的遞增順序連續(xù)分配給工件使得第i個工期分配給第i個完工的工件.而在ADD假設(shè)下,工期在分配給工件時是相互獨立的.我們證明了兩個歷史遺留問題1|GDD|∑(Ei+Ti)和1|ADD|∑(Ei+Ti)都是常數(shù)界不可近似的.我們的證明也意味著這兩個問題都是一元NP-困難的.此外,我們還證明了歷史遺留問題1|GDD|∑wiTi是一元NP-困難的.在第三章中,我們研究了單機上工件有位置限制的Pareto排序.首先,我們修正了歷史文獻中的推理錯誤.然后,對問題1｜σ[Jj]≤kj,prec|#(fmax,gmax),我們給出一個O(n4)-時間算法,其中“σ[Jj]≤ kj”表示工件Jj只能在前kj個位置上進行加工,“prec”表示工件的序約束限制.我們進一步證明了雙代理排序問題l｜σ[Jj]≤kj,pre｜#(fmaxA,gmaxB)在O(nA3nB+nAnB3)時間內(nèi)可解.在第四章中,我們研究了工件可自由下線的無界平行分批排序,其中可自由下線工件意味著每個工件的完工時間等于包含這個工件的批的開工時間與該工件的加工時間之和.首先,我們證明了問題p-batch(+∞)|drop-line,rj|Lmax是二元NP-困難的.此外,我們證明了,對每個γ∈{fmax,∑fj｝,問題p-batch(+∞)｜drop-line,rj|γ在偽多項式時間內(nèi)可解,并且當(dāng)工件實例有常數(shù)個不同的加工時間或常數(shù)個不同的到達時間時,該問題在多項式時間內(nèi)可解.在第五章中,我們研究了工件有一致的到達時間和加工時間的無界平行分批排序.我們考慮兩種類型的工件:批工件和自由下線工件.對批工件而言,每個工件的完工時間等于包含這個工件的批的完工時間.對雙指標(biāo)問題p-batch(+∞)|β*,(rj,pj)-agreeable|#(Cmax,fmax),其中 β*∈ {batch,drop-line},我們給出一個O(n3log（rmax+∑pj))-時間算法和一個O(n4)-時間算法.對單指標(biāo)問題p-batch(+∞)|β*,(rj,pj)-agreeable|∑ wjUj,其中β*∈ {batch,drop-line},我們證明了該問題是二元NP-困難的,并給出了一個偽多項式時間算法和一個全多項式時間近似方案.在第六章中,我們研究了單臺平行批機器上最小化最大完工時間的雙代理排序,其中工件是批工件,有各自的到達時間和線性退化的加工時間.目標(biāo)函數(shù)是,在代理B的最大完工時間不超過給定上界的條件下,最小化代理A的最大完工時間.Tang等人[144]對該排序模型給出了系統(tǒng)的研究.特別地,他們對下面四個問題給出了多項式時間算法.在第一個問題中,批容量無界且兩個代理兼容.在第二個問題中,批容量有界,兩個代理不兼容，A-工件有一個固定數(shù)目的正常加工時間,并且B-工件有一個相同的到達時間.在第三個問題和第四個問題中,批容量有界,兩個代理兼容,并且工件的到達時間和正常加工時間是一致的或者反一致的.在這一章中,我們證明了他們對這四個問題給出的算法都是無效的.我們對第一個問題給出了一個新的多項式時間算法并且證明了其他三個問題都是二元NP-困難的.我們進一步對批容量有界,兩個代理不兼容,并且A-工件和B-工件各有一個相同的到達時間的這種情形,給出了一個偽多項式時間算法.最后,我們對批容量無界且兩個代理不兼容的情形,給出了一個強多項式時間算法.
【學(xué)位單位】：鄭州大學(xué)
【學(xué)位級別】：博士
【學(xué)位年份】：2018
【中圖分類】：O223
【文章目錄】：
摘要
Abstract
第一章 緒論
    1.1 排序簡介
    1.2 記號與規(guī)則
    1.3 概念與術(shù)語
    1.4 相關(guān)模型介紹及文獻綜述
        1.4.1 多指標(biāo)排序
        1.4.2 多代理排序
        1.4.3 平行分批排序
        1.4.4 工件線性退化排序
        1.4.5 與工件位置相關(guān)的排序
    1.5 本文結(jié)果
第二章 GDD假設(shè)下的排序
    2.1 引言
i+T_i）'>    2.2 排序問題1|GDD|∑（E_i+T_i）
iT_i'>    2.3 排序問題1|GDD|∑w_iTi

第三章 工件有位置限制的Pareto排序
    3.1 引言
    3.2 修正文獻中的錯誤
max和g_max'>    3.3 最小化f_max和g_max

    3.4 最小化f_{max
A和gmax
B}

    3.5 其他相關(guān)結(jié)果
第四章 工件可自由下線的無界平行分批排序
    4.1 引言
    4.2 預(yù)備工作
    4.3 二元NP-困難性證明
    4.4 偽多項式時間算法
    4.5 兩種子情形
        4.5.1 K是常數(shù)
        4.5.2 E是常數(shù)
第五章 工件到達時間和加工時間一致的無界平行分批排序
    5.1 引言
    5.2 預(yù)備工作
max和f_max'>    5.3 最小化C_max和f_max

        5.3.1 第一個算法
        5.3.2 第二個算法
jU_j'>    5.4 最小化∑w_jU_j

        5.4.1 二元NP-困難性證明
        5.4.2 偽多項式時間算法
        5.4.3 全多項式時間近似方案
第六章 工件線性退化的雙代理平行分批排序
    6.1 引言
    6.2 一個基本算法
    6.3 第一個問題
        6.3.1 文獻中的錯誤
        6.3.2 我們的算法
    6.4 問題5的研究及擴展
        6.4.1 二元NP-困難性證明
        6.4.2 IF假設(shè)下的問題5
    6.5 問題6的一個新算法
第七章 結(jié)論與展望
參考文獻
個人簡歷、在學(xué)期間參加的科研項目及獲獎情況
在學(xué)期間論文發(fā)表情況
致謝

【參考文獻】

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

1 原晉江,林詒勛;關(guān)于具有主次指標(biāo)的單機排序的注記[J];高校應(yīng)用數(shù)學(xué)學(xué)報A輯(中文版);1996年02期

2 ;THE NP-HARDNESS OF THE SINGLE MACHINE COMMON DUE DATE WEIGHTED TARDINESS PROBLEM[J];Systems Science and Mathematical Sciences;1992年04期

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

1 耿志超;Pareto優(yōu)化排序問題研究[D];鄭州大學(xué);2016年

2 何程;多目標(biāo)分批排序及其相關(guān)課題[D];鄭州大學(xué);2009年

3 王吉波;工件加工時間可變的現(xiàn)代排序問題[D];大連理工大學(xué);2005年

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

1 張源;可用性及位置限制下的單機排序研究[D];鄭州大學(xué);2017年

2 賀守燕;單機上Pareto最優(yōu)排序問題的幾個結(jié)果[D];鄭州大學(xué);2015年

3 尚明明;帶有GDD假設(shè)的幾類重新排序問題研究[D];鄭州大學(xué);2015年

4 高園;單機上的幾類Pareto最優(yōu)排序問題研究[D];鄭州大學(xué);2014年

5 酒明珠;自由下線平行分批排序的計算復(fù)雜性[D];鄭州大學(xué);2014年

6 衛(wèi)志剛;可自由離線批處理機最小化加權(quán)完工時間和排序[D];鄭州大學(xué);2011年

本文編號：2894396

boshi