带有机器准备时间和加工资格限制的平行机排序问题

发布时间：2024-03-27 20:44

　　本文讨论了带有机器准备时间和加工资格限制的平行机排序,分别研究了目标函数为最大完工时间和最大延误时间的极小化问题.论文首先分析问题的NP-难性,然后讨论问题在多种特殊情形下的最优算法,最后在此基础上对原问题提出时间复杂度较好的启发式算法.第一部分,考虑极小化最大完工时间问题.首先针对问题Pm,Ri|pj=p,Mj|Cmax给出了时间复杂度分别为O(m3/2n5/2logmn)和O(n logn)的最优算法,然后针对问题Pm,Ri| Mj| Cmax提出了三个时间复杂度均为O(n log n)的启发式算法.第二部分,考虑极小化最大延误问题.首先分别证明了问题Pm,Ri| pj=1,Mj|Lmax、问题Pm | intree,pj=1,Mj| Lmax 和问题 P2 | prec,pj=1,Mj| Lmax 存在时间复杂度为O(n log n)、O(n log n)和O(n2)的最优算法,然后针对问题Pm,Ri|Mj| Lmax提出了时间复杂度为O(nlogn)的启发式算法.第三部分,考虑带有机器准备时间、加工资格限制和工件准备时间的平行机排序问题.针对问题Pm,Ri|rj,Mj| Cma...

【文章页数】：50 页

【学位级别】：硕士

【文章目录】：
中文摘要
Abstract
第一章 引言
    1.1 研究背景及现状
    1.2 现有算法及结论
    1.3 假设和符号说明
    1.4 研究内容及结构
第二章 带有机器准备时间和加工资格限制的极小化最大完工时间问题
    2.1 问题的NP-难性及可解性分析
    2.2 问题P_m,R_i|p_j=p,M_j|Cmax

    2.3 问题P_m,R_i|p_j,M_j|C_max

第三章 带有机器准备时间和加工资格限制的极小化最大延误时间问题
    3.1 问题的NP-难性及可解性分析
    3.2 问题P_m,R_i|p_j=1,M_j|L_max

    3.3 问题P_m,R_i|p_j,M_j|L_max

第四章 带有机器、工件准备时间和加工资格限制的平行机排序问题
    4.1 问题P_m,R_i|p_j,r_j,M_j|C_max

    4.2 问题P_m,R_i|p_j,r_j,M_j|L_max

第五章 总结和展望
    5.1 研究总结
    5.2 研究展望
参考文献
致谢



本文编号：3940469

suoshi