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

发布时间: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 问题Pm,Ri|pj=p,Mj|Cmax
  •     2.3 问题Pm,Ri|pj,Mj|Cmax
  • 第三章 带有机器准备时间和加工资格限制的极小化最大延误时间问题
        3.1 问题的NP-难性及可解性分析
        3.2 问题Pm,Ri|pj=1,Mj|Lmax
  •     3.3 问题Pm,Ri|pj,Mj|Lmax
  • 第四章 带有机器、工件准备时间和加工资格限制的平行机排序问题
        4.1 问题Pm,Ri|pj,rj,Mj|Cmax
  •     4.2 问题Pm,Ri|pj,rj,Mj|Lmax
  • 第五章 总结和展望
        5.1 研究总结
        5.2 研究展望
    参考文献
    致谢



    本文编号:3940469

  • 资料下载
    论文发表

    本文链接:https://www.wllwen.com/shoufeilunwen/benkebiyelunwen/3940469.html


    Copyright(c)文论论文网All Rights Reserved | 网站地图 |

    版权申明:资料由用户6b306***提供,本站仅收录摘要或目录,作者需要删除请E-mail邮箱bigeng88@qq.com