Efficient mapping algorithms for scheduling autonomous vehicles and robotic computations

This research addresses the intensive computational problems of routing autonomous vehicles in a material handling system of a flexible manufacturing system (FMS) and of computing the robot inverse dynamics for servoing robot manipulators in real time. All these problems are known to be NP-complete. Various efficient scheduling and mapping algorithms are proposed to obtain fast and suboptimal or optimal solutions. The problem of optimal task (or routing) assignment of p autonomous vehicles among m workstations in a material handling system of an FMS is formulated as an equivalent problem of destinating m workstations among p autonomous vehicles. Optimization of the objective function is based on the minimax of the job execution time and the minimization of max-min of the traveling time and the min-max of the waiting time of the autonomous vehicles. Using the state-space A;The problem of scheduling the robot inverse dynamics computation consisting of m computational modules with precedence relationship to be executed on a multiprocessor system consisting of p identical homogeneous processors to achieve minimum computation time is considered. This problem is formulated as an optimal matching between a computational task graph and a processor graph. Minimizing the maximum processor finishing time is used as an objective function for the scheduling optimization. Without considering the communication costs among the processors, a heuristic search algorithm called Dynamical Highest Level First/Most Immediate Successors First (DHLF/MISF) is first proposed to find a fast but suboptimal schedule. For an optimal schedule, the minimum-scheduled-length problem can be solved by the A...