Job Allocation And Scheduling In Multi Robotic Tasks Considering Collision Free Operation

摘要

This paper presents a method of job allocation and scheduling that determines optimal job allocation and the shortest paths for robots having collision regions. The problem described in this paper is an application of a classical flexible job-shop scheduling problem with shared resources. A genetic algorithm and a TABU search are used for the job allocation and scheduling procedures. Overlapping activities in a collision region can result in robot collisions. This should be a hard constraint in which a non-overlapping condition is guaranteed. To achieve this, the sequencing in a collision region should be determined. Job assignments, ordering in non-collision regions of each robot, and priorities in regions shared between various robots are encoded using a genetic representation in which the objective is to minimize the job completion time. As the search space is extremely large, a genetic algorithm is used for global searches and TABU is used for local searches. The most viable solution is obtained using the genetic algorithm. The TABU search enhances the solution by changing the path order of each robot in non-collision regions as well as the priorities in regions shared by various robots. A genetic encoding method and a procedure to calculate the makespan value under non-collision constraints was developed. To use the TABU search, neighborhoods were developed to boost the local search capability. As a verification test, the proposed method was applied to real problems in the automobile industry.