存在多设备工序的综合调度算法

Integrated Scheduling Algorithm with Multiple-devices-operation

针对工序集中存在需要多台设备协同完成加工的多设备工序的综合调度问题,提出一种把多设备工序设计成在多个相关设备上同时加工的多个虚拟工序的方法。该算法把产品加工树转化为多设备工序被设计成虚拟工序组的虚拟加工工艺树,为了优先调度虚拟工序组,将虚拟加工工艺树分解为以虚拟工序组为根结点的子树和剩余标准工序组成的子树,优先调度以虚拟工序组为根结点的子树;当以虚拟工序组为根结点的子树不唯一时,按子树上虚拟工序组个数多少确定子树的调度次序;对每个以虚拟工序组为根结点的子树,优先调度虚拟工序组个数较多的路径上工序;为了使相关虚拟工序同时开始加工,提出虚拟工序动态调整策略。理论分析和实例表明,所提出的调度算法能够较好地解决存在多设备工序的综合调度问题。

Aiming at integrated scheduling problem with multiple-devices-operation, a method to change multiple-devices-operation into multiple related virtual operations which processes on multiple related machines at the same time is proposed. Product processing tree is changed into virtual processing tree, on which each multiple-devices-operation is changed into a virtual operation group. Virtual processing tree is decomposed into subtree whose root node is virtual operation group and subtree that composed of remaining standard operations. The subtree whose root node is virtual operation group is scheduled previously; When the subtree whose root node is virtual operation group is not unique, the scheduling order of the subtree is determined according to the number of virtual operation group. The scheduling order of operations on subtree whose root node is virtual operation group is determined according to the number of virtual operation group on the path. In order to make related virtual operations start at the same time, virtual operation dynamic adjustment strategy is proposed. Theoretical analysis and examples show that the scheduling algorithm proposed is an effective solution to the scheduling problem with multiple-devices-operation.