基于拟关键路径的二车间综合调度算法

Integrated Scheduling Algorithm of Two Workshops Based on ACPM

针对如何将复杂产品工序有效地分配到具有相同设备资源的二车间加工的问题,提出了基于拟关键路径法的二车间综合调度算法。为了让二车间负载平衡并进行充分的并行处理,尽早结束产品加工,该算法按拟关键路径法(ACPM)对工序排序,再采取二车间加工结束时间接近的预调度策略进行调度。为了减少二车间工序的迁移次数,该算法将入度不小于2的工序放入其紧前工序分配较多的车间;将入度小于2且其紧后工序的入度不小于2的工序分配到能让其尽早结束的车间;对于其他唯一紧前紧后工序与其叶子节点所形成的工序串按预调度策略进行整串调度。实例表明,该算法可以在二次复杂度内较优地实现具有相同设备资源的二车间分布式综合调度。

Aiming at the problem that how processes of complex products are effectively allocated to two workshops with the same equipment resources,this paper proposed integrated scheduling algorithm of two workshops based on ACPM.In order to let the two workshops load balancing and fully parallel processed,and complete products processing as soon as possible,the algorithm according to the ACPM,takes the pre-scheduled strategy for scheduling for the end of the two workshops in which processed time is close.In order to reduce the number of relocation of two workshops,the algorithm assigns fork point process for in-degree no less than two into the workshop in which predecessor assigned is more;assigns the processes of their in-degree less than 2,at the same time having the successor with the in-degree no less than 2 into the workshop which makes them early finished,to take pre-scheduled strategy for the other processes which have the only predecessor and successor formed by their leaf nodes to finishing a whole string.Examples show that the algorithm has better achieved the two workshop distributed scheduling with the same equipment resources in which in the two time complexity.