随着工业4.0时代的到来,制造业将迎来智能工厂和智能生产两大重要命题。迅速的响应客户定制需求,在有效时间内生产出高质量和个性化产品成为了未来工厂核心竞争力,在此背景下的制造系统调度问题研究变得十分重要。本文在综述现有制造系统调度问题这一类组合优化问题的求解方法的基础上,对基于Petri网可达图启发式搜索的求解方法展开了基础性问题的研究,提出了多种能够提高求解效率的方法。该方法求解调度问题的主要思路是利用时间Petri网的执行能力,结合搜索算法产生可达图,并在搜索过程中加入启发式函数进行引导,以变迁激发顺序的方式给出调度策略。但是该方法存在可达图状态数会随着问题变大而指数性增长的问题,为了提高求解效率,现有研究均产生部分可达图进行求解,两大要素影响着该方法的效率：可达图产生方法和启发式函数设计。本文围绕以上两个关键点,由浅入深做了以下内容研究：1)对于最小完成时间调度问题,机器启发式函数计算每台机器的剩余操作时间,并选取最大值对整个过程完成时间的下限进行预测,是一类重要的的启发式函数,但是现有函数存在以下两个重要问题：在柔性制造系统环境下,没有准确分类剩余加工操作,会导致求解结果非最优；没有考虑未完成操作的剩余时间,求解效率受到影响。本文针对以上情况提出了改进方法,在保证最优性的前提下,提高了最小完成时间的预测下限,使得库所延迟Petri网下的可达图搜索方法求解效率更高。2)现有启发式函数均是在库所延迟Petri网框架下设计的,受模型框架限制,整体效率不高。本文首次提出在变迁延迟Petri网框架下设计启发式函数,该方法能够有效利用token时间戳这一时间属性添加方式的优势,综合考虑每个资源的可行时间,对完成时间的下限从机器和产品两个角度进行预测。此外,现有方法均采用单个变迁激发方式扩展可达图,而对于JSP (Job-shop Scheduling Problem,车间调度)这一特殊问题,本文证明在模型结构条件满足下,部分变迁能够合并激发,在不影响结果最优性的前提下能够直接探索更深的后继标识。以上两个方法均能够提高用Petri网求解JSP的效率。3)时间属性添加方式上的不同,使得库所延迟Petri网能够抑制更多的可达图冗余标识,而变迁延迟Petri网下能够设计更加高效的启发式函数,所以本文提出一种结合两者优势的混合算法框架,在该框架中,前者用于构建算法框架以产生部分可达图并限制冗余标识,后者用以设计启发式函数计算完成时间下限引导可达图扩展。至此,基于Petri网的可达图启发式搜索的调度问题求解方法效率得到了明显的提高。4)本文提出的启发式设计方法和混合框架不仅适用于制造系统的调度问题,同时具备可拓展性,能够推广到其他带有顺序约束的组合优化命题。本文以石化企业MES全业务流程为例,设计了一种基于石化企业MES业务流程的工作流控制系统。针对业务流程调度问题,在系统工作流服务器设计中融入了本文算法和框架,并针对更为复杂的Petri网结构,调整了现有启发式函数,使之能够求解最小完成时间工作流调度问题。最后,在总结全文内容的基础上,提出了基于Petri网可达图启发式搜索求解调度问题方法有待研究的几个问题。