如今,企业在市场中得以生存和发展的核心竞争力向产品多样性和个性化转变,为了提升企业经济效益,制造系统的调度问题备受关注。工件具有in-tree优先约束的作业车间调度问题(Job-shop Scheduling Problem,JSP)是当前制造领域常见的调度问题,普遍存在于装配型离散制造车间和多品种小批量生产车间中。该JSP受到工件层面和工序层面的双重生产顺序约束,在实际调度中常出现在制品库存过高的问题,是比经典JSP更为复杂的NP-hard问题。本文在对JSP和优化算法进行了较为深入的理论和应用研究的基础上,为工件具有in-tree优先约束的JSP设计了有效的算法。本文主要创新点及其相关工作内容总结如下:1.本文对近70年内JSP的研究成果进行梳理和总结后发现:遗传算法应用最为广泛和可行;逆序调度可有效控制在制品库存;对工件具有in-tree优先约束的JSP以及使用逆序调度解决JSP的研究仍比较少。针对在实际生产车间中遇到的主要痛点,结合各优化算法的优缺点,本文选择设计遗传算法和逆序调度相结合的算法,以解决工件具有in-tree优先约束的JSP。2.针对降低在制品库存的调度目标,本文总结出4个合适的调度性能评价指标。3.工件具有in-tree优先约束的JSP约束关系复杂,为了对工件内部和外部的生产顺序约束关系进行梳理,本文提出基于销售订单对所有工件构建树形图和分层。分层后,同一层级内的工件之间不存在生产顺序约束,将工件之间的in-tree优先约束简化为各层工件集合之间的链式优先约束。在此基础上:对工件具有in-tree优先约束的JSP进行描述,并建立数学模型;结合逆序调度的思想,构造算法框架,其核心是针对本文问题设计的in-tree-JSP逆序遗传算法。4.针对本文问题的特点,对in-tree-JSP逆序遗传算法的主要设计有:重新定义了基于工序的编码方式,并提出逆序的工序插入方法作为解码方式,以解码得到在制品库存更少和生产周期更短的调度方案;提出基于工件和基于销售订单的随机初始化方式,前者生成的初始种群具有较好的多样性和优良个体,后者生成的初始种群在最大化完工同步性上表现突出;提出基于工件的邻域搜索变异算子对染色体进行变异操作,以提高算法的局部搜索能力。最后,使用Python编程实现in-tree-JSP逆序遗传算法,应用实例进行验证。结果表明,in-tree-JSP逆序遗传算法具有良好的收敛性、可行性和有效性,缩短了原生产车间44.29%的加工等待时间,使得在制品库存降低,并达成100%按时交付率。