一种异步蚁群算法求解柔性作业车间调度问题

An Asynchronous Parallel Ant Colony Optimization for Flexible Job-Shop Scheduling Problem

调度问题广泛存在于资源共享型系统中,大多数的调度问题都属于混合整数规划问题.大规模混合整数规划问题是计算科学领域中的NP-hard经典问题之一,一般认为无法用精确计算求解.生产调度是调度的一个重要分支,是实现智能制造关键环节之一.针对多品种变批量柔性作业车间调度问题,以最小制造期为优化目标,设计了一种基于Petri网的异步并行蚁群算法,其中:提出了一种基于Petri网的步可达图构造方法,用于蚁群算法解空间的构造;探讨了传统蚁群算法搜索机制,并给出了一种基于异步仿真时钟的蚁群并行搜索方法;仿真结果表明,多线程控制方法可以有效地避免算法的早熟收敛问题.将所提出的算法应用于某安防件智能制造系统的柔性作业车间调度中,降低了系统的总制造时间,获得较好工程效果的同时验证了算法的有效性.

Scheduling problem widely exists in the systems of resource-sharing,mainly in the form of mixed integer programming.Large-scale mixed-integer programming problem is one of the classic NP-hard problems in the field of computational science,which cannot be solved through precise computation in general.Job-shop scheduling is a major sub-field of scheduling and a key aspect of intelligent manufacturing.Aiming at the flexible job-shop scheduling problems of multi-products and variety batch,a Petri nets-based asynchronous parallel ant colony optimization is proposed with the optimization target of minimizing the time consuming of manufacturing cycle.A Petri nets-based method of creating step-reachability graph is put forward,which is used for construction of search space of ant colony optimization.On the basis of discussing the search mechanism of traditional ant colony algorithm,a search method of asynchronous parallel for ant colony is presented based on asynchronous simulation clock.A multi-threaded control method for update of pheromone is used.Simulation results show that the multi-threaded control method can overcome the premature convergence effectively.The proposed approach is illustrated by a case of flexible job shop scheduling for an intelligent manufacturing system of defense and security facilities,through which solutions of high quality can be found quickly.In sum,the proposed optimization has obtained a good effect in engineering applications while the validity of optimization has been proved.