机器带使用限制的若干排序问题的算法研究

发布时间：2022-01-05 12:34

　　本论文主要从算法设计与分析的角度,对机器有使用限制的排序问题进行了研究。我们首先考虑了机器有不可用时间限制的排序问题,然后研究了既有加工,又有运输的机器有不可用时间限制的供应链排序问题。我们主要从离线和在线两个方面考虑机器有使用限制的排序问题。目标函数主要有最小化最大完工时间,最小化完工时间和,最小化最大运输时间与最小化运输时间和。全文由六个部分组成,第一章首先给出了组合优化和排序问题的基本概念,然后介绍了机器有不可用时间限制的排序问题的研究近况,以及有加工和运输的供应链排序问题的一些概念和研究进展。第二章首先研究了单台机器有一个不可用时间限制的排序问题,目标为最小化最大完工时间。对于这个问题,我们设计了一个4/3近似算法和一个动态规划算法,并给出了一个竞争比为2的最优在线算法。然后,我们研究了单台机器带一个不可用时间限制的排序问题,目标为最小化完工时间和。对于这个问题,我们设计了一个时间复杂性为O（n log n）的算法,并证明了该算法的性能比为17/15。第三章考虑了两台机器的排序问题,其中一台机器有一个不可用时间限制,而另一台机器一直可用,工件在加工过程中不可恢复,其目标为最小化... 

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

【文章页数】：101 页

【学位级别】：博士

【文章目录】：
摘要
Abstract
第1章 绪论
    1.1 组合优化问题
    1.2 算法和计算复杂性
    1.3 排序问题概述
    1.4 文献综述
        1.4.1 经典排序问题和在线排序问题
        1.4.2 机器有不可用时间限制的排序问题
        1.4.3 机器有不可用时间限制的加工与运输问题
    1.5 论文概述
第2章 单台机器有一个不可用时间限制的排序问题
    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章 两台机器有一个不可用时间限制的排序问题
    3.1 引言
    3.2 2-近似算法
    3.3 动态规划算法
    3.4 FPTAS
第4章 两台机器有周期性不可用时间限制的排序问题
    4.1 引言
    4.2 工件不可恢复的情形
    4.3 工件可恢复的情形
        4.3.1 问题最优值的一个下界
        4.3.2 近似算法
    4.4 工件可恢复的在线问题
第5章 单台机器有一个不可用时间限制的加工与运输问题
    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章 单台机器有周期性不可用时间限制的加工与运输问题
    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章 总结与展望
参考文献
致谢
附录：博士在读期间完成的论文



本文编号：3570355