Abstract: Based on the characteristics of job-shop robotic manufacturing cell scheduling problem,an improved genetic algorithm by integrating heuristic rules and neighborhood search strategy was researched,which was aimed at minimizing the maximum completion time.A mathematical optimization model and an improved disjunctive graph model for job-shop robotic manufacturing cell scheduling problem were established.Based on key path of disjunctive graph model,the moving machine block,changing robot block and adjusting robot task allocation were used to construct the search neighborhood,and the three layer scheduling method by integrating procedure insertion method and task allocation method of heuristic moving were used to initialize the population.Neighborhood structures-based local search algorithm was combined with three layer scheduling-based genetic algorithm to solve the problem effectively.Benchmark tests showed that the improved genetic algorithm was effective and was superior to other algorithms.

Key words: job-shop, multi-robots, manufacturing cell, scheduling, disjunctive graph, genetic algorithms, neighborhood search

摘要： 针对带多台机器人的作业车间类型机器人制造单元调度问题的特点,研究了以最小化最大完工时间为优化目标、将邻域搜索策略与启发式规则相结合的混合遗传算法,建立了作业车间类型多机器人制造单元调度问题的数学优化模型和析取图模型。基于析取图关键路径,采取移动机床块、交换机器人块、调整任务分配来构建搜索邻域;用启发式搬运工序插入法和启发式搬运任务分配法相结合的三层调度方法初始化种群;将基于邻域结构的局部搜索算法和基于三层调度的遗传算法相结合,有效实现问题的求解。通过基准算例测试表明,混合遗传算法有效并优于其他算法。

关键词: 作业车间, 多机器人, 制造单元, 调度, 析取图, 遗传算法, 邻域搜索