基于Petri网和启发式搜索的调度算法研究

发布时间：2023-12-24 14:14

　　随着工业4.0时代的到来,制造业将迎来智能工厂和智能生产两大重要命题。迅速的响应客户定制需求,在有效时间内生产出高质量和个性化产品成为了未来工厂核心竞争力,在此背景下的制造系统调度问题研究变得十分重要。本文在综述现有制造系统调度问题这一类组合优化问题的求解方法的基础上,对基于Petri网可达图启发式搜索的求解方法展开了基础性问题的研究,提出了多种能够提高求解效率的方法。该方法求解调度问题的主要思路是利用时间Petri网的执行能力,结合搜索算法产生可达图,并在搜索过程中加入启发式函数进行引导,以变迁激发顺序的方式给出调度策略。但是该方法存在可达图状态数会随着问题变大而指数性增长的问题,为了提高求解效率,现有研究均产生部分可达图进行求解,两大要素影响着该方法的效率：可达图产生方法和启发式函数设计。本文围绕以上两个关键点,由浅入深做了以下内容研究：1)对于最小完成时间调度问题,机器启发式函数计算每台机器的剩余操作时间,并选取最大值对整个过程完成时间的下限进行预测,是一类重要的的启发式函数,但是现有函数存在以下两个重要问题：在柔性制造系统环境下,没有准确分类剩余加工操作,会导致求解结果非最优；...

【文章页数】：137 页

【学位级别】：博士

【文章目录】：
致谢
摘要
Abstract
缩写、符号清单、术语表
1 绪论
    1.1 研究背景
    1.2 调度问题的一般性研究方法
    1.3 Petri网的发展历史与调度问题应用
    1.4 本文研究路线以及创新点
2 Petri网和调度问题求解算法
    2.1 Petri网定义
    2.2 时间Petri网
    2.3 可达图模型
    2.4 B&B和A^*算法
    2.5 本章小结
3 PTPN下启发式函数改进
    3.1 启发式函数的重要作用
    3.2 FMS调度问题的Petri网建模
    3.3 现有启发式函数存在的问题与改进
    3.4 案例分析
    3.5 本章小结
4 TTPN下启发式函数设计
    4.1 TTPN框架下启发式函数的特点
    4.2 TTPN下的JSP建模
    4.3 TIPN下的f_lbr和fε

    4.4 基于token时间戳的TTPN启发式函数设计
    4.5 TTPN框架中的多变迁激发策略
    4.6 案例分析
    4.7 本章小结
5 混合搜索框架和算法
    5.1 混合框架提出的背景
    5.2 PTPN和TTPN的对比
    5.3 混合搜索框架与算法
    5.4 案例分析
    5.5 本章小结
6 基于Petri网的工作流调度系统和算法设计
    6.1 本文方法的可拓展性
    6.2 工作流的Petri网建模
    6.3 MES工作流系统设计
    6.4 应急流程调度工程案例分析
    6.5 本章小结
7 总结与展望
    7.1 研究工作总结
    7.2 研究展望
参考文献
附录
作者简历



本文编号：3874672

boshi