紧密衔接工序组联动的综合调度算法

由于现有的工序间存在紧密衔接条件的复杂产品综合调度问题, 采用的移动交换算法不易于软件实现且没有考虑移动工序后产生的连锁反应引起较高算法复杂度的问题, 提出将具有紧密衔接约束条件的工序组进行统一联动的综合调度算法.该算法利用将具有紧密衔接约束条件的工序分组的扩展加工工艺树模型, 按路径上属于工序组的工序个数多少确定所在路径工序组调度的次序, 通过降低对工序组的限制要求降低算法复杂度; 对于被调度工序组中各工序的前序工序, 按工序组中工序的加工顺序确定调度次序, 对某个工序的前序工序采用复杂度较低的拟关键路径法确定工序的调度次序; 调度完所有紧密衔接工序组后, 剩余的标准工序按拟关键路径法确定调度顺序; 采取工序首次适应调度算法调度标准工序和工序组, 由于工序组中工序采取按序紧密衔接的联动调度方式确定工序组的开始时间, 避免了二次调整, 进一步降低了算法复杂度. 分析和实例表明, 所提出的综合算法比以往算法复杂度更低, 调度结果更优且更易于实现.

Integrated Scheduling Algorithm with No-wait Constraint Operation Group

The movement and exchange algorithm can hardly resolve the existing complex products scheduling problem with no-wait constraint between operations. An integrated scheduling algorithm is proposed which makes no-wait constraint operation group (NWCOG) into linkage. The algorithm uses the expansion processing tree to make the operations with no-wait constraint into operation group, and determines the scheduling order of the operation group according to the number of operations which belong to NWCOG on path. Then lower complexity is obtained by reducing the restrictions of the NWCOG. For the preorder operations of each operation scheduled in the group, the scheduling order is determined by the processing order of operations in the group. For preorder operation of some operation, the scheduling order is determined by the allied critical path method (ACPM) which has lower complexity. After each of NWCOG is finished scheduling, the remained standard operations are scheduled by ACPM. Then, the first fit scheduling method (FFSM) is used to schedule the standard operations and the NWCOG. As the start time of the operation group is determined by the linkage-scheduling method, the secondary adjustments can be avoided and the complexity can be reduced. Analysis and examples show that the proposed algorithm has a lower complexity, better scheduling results and can be easier to implement.