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

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

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

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

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

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

【參考文獻(xiàn)】

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

1 原晉江,林詒勛;關(guān)于具有主次指標(biāo)的單機(jī)排序的注記[J];高校應(yīng)用數(shù)學(xué)學(xué)報(bào)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)化排序問(wèn)題研究[D];鄭州大學(xué);2016年

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

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

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

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

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

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

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

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

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

本文編號(hào)：2894396

boshi