新型排序问题的计算复杂性研究

发布时间：2020-11-22 08:14

　　 排序是指在一定的约束条件下分配有限的资源于时间空间去完成多项任务使得一个或者多个目标达到理想或最优.排序的好坏直接影响着生产商成本的高低和利润的大小.因此,排序论对提高效率、科学决策、资源的开发与配置等方面都起到重要的作用.在排序论中,人们把任务统称为“工件”,而把资源统称为“机器”.本学位论文主要研究了若干新型排序问题的计算复杂性.在第二章中,我们研究了 GDD或ADD假设下的单机排序.在GDD假设下,工期按照EDD顺序进行排列,并按照工件完工时间的递增顺序连续分配给工件使得第i个工期分配给第i个完工的工件.而在ADD假设下,工期在分配给工件时是相互独立的.我们证明了两个历史遗留问题1|GDD|∑(Ei+Ti)和1|ADD|∑(Ei+Ti)都是常数界不可近似的.我们的证明也意味着这两个问题都是一元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)时间内可解.在第四章中,我们研究了工件可自由下线的无界平行分批排序,其中可自由下线工件意味着每个工件的完工时间等于包含这个工件的批的开工时间与该工件的加工时间之和.首先,我们证明了问题p-batch(+∞)|drop-line,rj|Lmax是二元NP-困难的.此外,我们证明了,对每个γ∈{fmax,∑fj｝,问题p-batch(+∞)｜drop-line,rj|γ在伪多项式时间内可解,并且当工件实例有常数个不同的加工时间或常数个不同的到达时间时,该问题在多项式时间内可解.在第五章中,我们研究了工件有一致的到达时间和加工时间的无界平行分批排序.我们考虑两种类型的工件:批工件和自由下线工件.对批工件而言,每个工件的完工时间等于包含这个工件的批的完工时间.对双指标问题p-batch(+∞)|β*,(rj,pj)-agreeable|#(Cmax,fmax),其中 β*∈ {batch,drop-line},我们给出一个O(n3log（rmax+∑pj))-时间算法和一个O(n4)-时间算法.对单指标问题p-batch(+∞)|β*,(rj,pj)-agreeable|∑ wjUj,其中β*∈ {batch,drop-line},我们证明了该问题是二元NP-困难的,并给出了一个伪多项式时间算法和一个全多项式时间近似方案.在第六章中,我们研究了单台平行批机器上最小化最大完工时间的双代理排序,其中工件是批工件,有各自的到达时间和线性退化的加工时间.目标函数是,在代理B的最大完工时间不超过给定上界的条件下,最小化代理A的最大完工时间.Tang等人[144]对该排序模型给出了系统的研究.特别地,他们对下面四个问题给出了多项式时间算法.在第一个问题中,批容量无界且两个代理兼容.在第二个问题中,批容量有界,两个代理不兼容，A-工件有一个固定数目的正常加工时间,并且B-工件有一个相同的到达时间.在第三个问题和第四个问题中,批容量有界,两个代理兼容,并且工件的到达时间和正常加工时间是一致的或者反一致的.在这一章中,我们证明了他们对这四个问题给出的算法都是无效的.我们对第一个问题给出了一个新的多项式时间算法并且证明了其他三个问题都是二元NP-困难的.我们进一步对批容量有界,两个代理不兼容,并且A-工件和B-工件各有一个相同的到达时间的这种情形,给出了一个伪多项式时间算法.最后,我们对批容量无界且两个代理不兼容的情形,给出了一个强多项式时间算法.
【学位单位】：郑州大学
【学位级别】：博士
【学位年份】：2018
【中图分类】：O223
【文章目录】：
摘要
Abstract
第一章 绪论
    1.1 排序简介
    1.2 记号与规则
    1.3 概念与术语
    1.4 相关模型介绍及文献综述
        1.4.1 多指标排序
        1.4.2 多代理排序
        1.4.3 平行分批排序
        1.4.4 工件线性退化排序
        1.4.5 与工件位置相关的排序
    1.5 本文结果
第二章 GDD假设下的排序
    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 其他相关结果
第四章 工件可自由下线的无界平行分批排序
    4.1 引言
    4.2 预备工作
    4.3 二元NP-困难性证明
    4.4 伪多项式时间算法
    4.5 两种子情形
        4.5.1 K是常数
        4.5.2 E是常数
第五章 工件到达时间和加工时间一致的无界平行分批排序
    5.1 引言
    5.2 预备工作
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假设下的问题5
    6.5 问题6的一个新算法
第七章 结论与展望
参考文献
个人简历、在学期间参加的科研项目及获奖情况
在学期间论文发表情况
致谢

【参考文献】

相关期刊论文 前2条

1 原晋江,林诒勋;关于具有主次指标的单机排序的注记[J];高校应用数学学报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期

相关博士学位论文 前3条

1 耿志超;Pareto优化排序问题研究[D];郑州大学;2016年

2 何程;多目标分批排序及其相关课题[D];郑州大学;2009年

3 王吉波;工件加工时间可变的现代排序问题[D];大连理工大学;2005年

相关硕士学位论文 前6条

1 张源;可用性及位置限制下的单机排序研究[D];郑州大学;2017年

2 贺守燕;单机上Pareto最优排序问题的几个结果[D];郑州大学;2015年

3 尚明明;带有GDD假设的几类重新排序问题研究[D];郑州大学;2015年

4 高园;单机上的几类Pareto最优排序问题研究[D];郑州大学;2014年

5 酒明珠;自由下线平行分批排序的计算复杂性[D];郑州大学;2014年

6 卫志刚;可自由离线批处理机最小化加权完工时间和排序[D];郑州大学;2011年

本文编号：2894396

boshi