若干新型排序问题的复杂性与算法研究

发布时间：2021-02-02 19:28

　　本文研究了若干新型排序问题,主要包括工件可拒绝的平行机代理排序问题、工件带退化和拒绝的分批排序问题、工件带退化和拒绝的多代理排序问题、带有人员不可用区间的两台机器流水车间排序问题以及工件可拒绝的供应链排序问题五个方面。针对不同的问题,我们分别给出了相应的算法,并对一些问题的计算复杂性进行了分析。第一章首先给出了组合优化和排序论方面的一些基本概念和定义,然后介绍了与本文内容相关方向的研究现状,最后介绍了本文的主要研究成果。第二章研究了工件可拒绝的平行机代理排序问题。给定两个代理A和B以及两台平行机,每个代理有一批工件需要在机器上加工,两个代理的工件互不相同。对于任意一个工件,可以被拒绝并支付一定的拒绝费用,或者被接受并安排在机器上加工。目标是在代理B的接受工件对应的目标函数fB与拒绝B-工件的总拒绝费用之和不超过一给定上界的情况下,极小化代理A的接受工件对应的目标函数fA与拒绝A-工件的总拒绝费用之和,其中fA和fB分别是关于代理A和代理B的接受工件的完工时间的正则函数。我们研究了四种不同的目标函数组合,fA=∑CjA,fB∈（?）当（fA,fB）={∑CjA,CmaxB),我们给出了两... 

【文章来源】：华东理工大学上海市 211工程院校 教育部直属院校

【文章页数】：124 页

【学位级别】：博士

【文章目录】：
摘要
Abstract
第1章 绪论
    1.1 组合优化问题
    1.2 算法和计算复杂性
    1.3 排序问题简介
    1.4 文献综述
    1.5 论文概述
第2章 工件可拒绝的两代理平行机排序问题
    2.1 引言
    2.2 问题描述
max
B+∑_Ji^B∈RB ej
B≤Q|∑Ji
A∈AA Cj
A+∑Jj
A∈R_A ej
A">    2.3 问题 P2|rej,Cmax
B+∑_Ji^B∈RB ej
B≤Q|∑Ji
A∈AA Cj
A+∑Jj
A∈R_A ej
A

        2.3.1 动态规划算法
        2.3.2 近似算法
max
B+∑J_{j
B∈RB ej
B≤Q|∑Jj
A∈AA Cj
A+∑Jj
A∈RA ej
A">    2.4 问题 P2|rej,Lmax
B+∑Jj
B∈RB ej
B≤Q|∑Jj
A∈AA Cj
A+∑Jj
A∈RA ej
A}

    2.5 问题 P2|rej,∑w_{j
BUj
B≤Q|∑Jj
A∈AA Cj
A+∑Jj
A∈RA ej
A}

第3章 工件带退化和拒绝的两代理单机排序问题
    3.1 引言
    3.2 问题描述
j
X=b_{j
X（a+bt）,Cmax
B+∑ej
B≤Q|∑Cj
A+∑ej
A">    3.3 问题 1|rej,pj
X=bj
X（a+bt）,Cmax
B+∑ej
B≤Q|∑Cj
A+∑ej
A}

        3.3.1 动态规划算法
        3.3.2 近似算法
j
X=b_{j
X（a+bt）,∑Cj
B+∑ej
B≤Q|∑Cj
A+∑ej
A">    3.4 问题 1|rej,pj
X=bj
X（a+bt）,∑Cj
B+∑ej
B≤Q|∑Cj
A+∑ej
A}

第4章 工件带退化和拒绝的单机批处理排序问题
    4.1 引言
    4.2 问题描述
max的情形">    4.3 最大完工时间C_max的情形
        4.3.1 复杂性分析
j=b_jt,r_j,b=∞,∑J_j∈R e_j≤Q|C_max">        4.3.2 问题 1|rej,p-batch,p_j=b_jt,r_j,b=∞,∑J_j∈R e_j≤Q|C_max

        4.3.3 问题 1|rej,p-batch,p_j=b_jt,r_j,b=∞,C_max≤Y|∑J_j∈R e_j

    4.4 加权总完工时间∑J_i∈A w_jC_j的情形
        4.4.1 复杂性分析
j=b_jt,b=∞,∑J_j∈R e_j≤Q|∑J_j∈A w_jC_j">        4.4.2 问题 1|rej,p-batch,P_j=b_jt,b=∞,∑J_j∈R e_j≤Q|∑J_j∈A w_jC_j

        4.4.3 问题 1|rej,p-batch,P_j=b_jt,b=∞,∑J_i∈R e_j≤Q|T_max

    4.5 问题 1|rej,p-batch,P_j=b_jt,b=∞,∑J_j∈R e_j≤Q|T_max

第5章 带有人员不可用区间的流水车间排序问题
    5.1 引言
    5.2 符号说明及基本性质
    5.3 复杂性分析
    5.4 近似算法
第6章 工件可拒绝的供应链排序问题的一个改进算法
    6.1 引言
    6.2 问题描述及基本性质
    6.3 近似算法
第7章 结论与展望
参考文献
致谢
博士在读期间完成的论文


【参考文献】：
博士论文
[1]带不可用时间段的若干单机供应链排序问题的算法研究[D]. 范静.华东理工大学 2015
[2]机器带使用限制的若干排序问题的算法研究[D]. 李刚刚.华东理工大学 2015



本文编号：3015250

boshi