基于混合遗传算法的柔性作业车间机器和AGV规划

A hybrid GA approach to the scheduling of machines and automated guided vehicles in flexible job shops

摘要:

为解决柔性作业车间多自动导引小车（AGV）配送的调度问题，以加工过程中AGV运送工件从毛坯库到成品库总时间最短为目标，提出基于时间表和A*算法的混合遗传算法。提出两种方案分别解决AGV路径规划中的冲突碰撞问题和AGV在机器位置等待时的占用问题。将机器和AGV调度集成在划分好的任务单元中，设计了基于任务单元的染色体编码方式，改进了种群初始化方案，交叉变异算子和精英保留策略，在解码操作中根据时间表信息，使用A*算法和冲突解决方案规划出每个任务单元中小车无碰撞和占用冲突的最佳路径。最后，算例对比验证了该算法的可行性和有效性。

Abstract:

This work proposes a hybrid genetic algorithm based on timetable and A* algorithm to solve the scheduling problem of multiautomatic guided vehicle (AGV) distribution in the flexible workshop, and the optimization goal of the algorithm is to minimize the total time for the AGV to transport the workpieces from the rough library to the finished product warehouse. Two schemes are proposed to solve the collision problem in AGV path planning and the problem of position occupation while the AGV is waiting at the position of machine. The machine and AGV scheduling is integrated in the divided task unit. Then the chromosome coding method based on the task unit is designed. The population initialization scheme, the cross and mutation operator and the elite retention strategy are improved. In the decoding operation, according to the schedule information, the A* algorithm and conflict resolution are used to plan out the best path without collisions and occupation conflicts in each task unit. Finally, the feasibility and effectiveness of the algorithm are verified by the numerical examples.