根子树纵横预调度的综合调度研究
摘要
综合调度是考虑加工和装配并行处理的调度问题，比传统调度方法更符合
树状约束关系的单件复杂产品生产需求。部分综合调度算法是从挖掘工艺树的
整体纵横特性出发，使用统一的纵向为主或者横向为主调度规则解决所有工序
的竞争问题，而忽略工艺树内部纵横特性对不同产品调度效果的影响；分布式
综合调度算法过于注重纵向优化和设备负载均衡，以及未考虑特殊工序加工属
性对优化目标的影响，这些因素可能会产生不必要的工序迁移操作，导致工序
调度不够紧凑；柔性综合调度算法注重设备利用率而忽视加工设备总负载，并
且将工序加工设备的选择及工序的冲突竞争问题同时进行考虑，需要搜索并比
较所有空闲设备的可调度工序组合方案，降低算法求解效率。鉴于目前综合调
度算法存在的问题，本文从分析工艺树内部纵横特性的角度出发，提出根子树
纵横预调度的综合调度解决方案，以最小化完工时间为目标，优化一般综合调
度问题、资源对称型和资源非对称型分布式综合调度问题；同时，将上述研究
成果扩展应用到柔性综合调度领域中。具体研究内容包含以下四个部分：
针对一般综合调度问题，提出根子树纵横预调度的同设备工序排序综合调
度算法。该算法将工艺树拆分为若干根子树，利用纵向预调度策略和横向预调
度策略分析根子树的纵横特性，通过分析结果获取设备工序预启动时刻和根子
树优先级对工序进行排序，挖掘工序调度的紧迫性；在此基础上，提出根子树
工序融合冲突调整策略，将工序加载到对应设备队列中，在每一轮调度过程中
确定所有队首工序的开始加工时间，进而完成根子树工序在工艺树纵向和设备
横向约束条件下的融合操作。实例对比结果验证了该算法处理一般综合调度问
题的有效性和可行性。
针对资源对称型分布式综合调度问题，从“工序找设备”的角度出发，提
出根子树纵横预调度的对称二车间综合调度算法。该算法采用横向设备约束的
工序冲突调整策略，在单车间环境下通过纵横预调度方式对同设备根子树工序
进行分组排序，增强工序调度的并行紧凑性；在摒弃设备均衡策略和考虑工序
迁移时间的基础上，提出二车间纵向工艺树约束的工序冲突调整策略，将队首
工序同时出队并确定其加工车间，保障工序尽早加工和选择加工车间的灵活性，
-I-
提高算法的求解效率。实例对比结果表明，该算法能够有效地处理对称二车间
综合调度问题。
针对资源非对称型分布式综合调度问题，从“设备找工序”的角度出发，
提出虚拟单车间根子树纵横预调度的非对称二车间综合调度算法，解决了现有
非对称分布式综合调度算法忽视特殊工序加工属性而影响整体调度效果的问
题。该算法采用虚拟单车间根子树工序排序策略，以当前设备资源种类作为预
调度背景对根子树工序进行分组排序，解决非对称二车间设备上的工序调度横
向冲突问题；在考虑设备空闲时间段和特殊工序加工属性的基础上，设计了考
虑工序属性的加工车间优化调度策略为可出队工序寻找合适的加工车间，提高
加工设备利用率。实例对比结果表明，该算法具有较好的优化性能。
针对柔性综合调度问题，从“工序与设备”双向互选的角度出发，提出根
子树纵横预调度的动态确定加工设备柔性综合调度算法。该算法设计了同计划
加工设备根子树工序排序策略，基于预调度方式对改进工艺树的根子树工序进
行分组排序，并完成计划加工工序和计划加工设备之间的计划绑定关系，保障
加工设备总负载；采用动态确定工序的柔性加工设备优化调度策略，在每一个
设备驱动时刻梳理根子树工序的调度状态及加工设备的工作状态，充分发挥柔
性设备的特点确定工序的加工设备，避免加工设备的非必要柔性选择；通过工
序分组和多设备同时处理方式，缩小可调度工序组合方案的搜索范围，降低工
序与设备之间互选的复杂度。实例对比结果表明，该算法能够有效地求解柔性
综合调度问题，并且较好地保障加工设备总负载。
关键词综合调度；特殊工序；根子树纵横预调度；工序迁移时间；加工设备总
负载
-II-
ResearchonIntegratedSchedulingBasedon
Root-SubtreeVerticalandHorizontalPre-scheduling
Abstrac