EFFICIENT SCHEDULING ALGORITHMS FOR ROBOT INVERSE DYNAMICS COMPUTATION ON A MULTIPROCESSOR SYSTEM.

C. L. Chen, C. S.G. Lee, E. S.H. Hou

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations

Abstract

The problem of scheduling an inverse dynamics computation consisting of m computational modules to be executed on a multiprocessor system consisting of p identical homogeneous processors to achieve a minimum-scheduled length is presented. To achieve the minimum computation time, the Newton-Euler equations of motion are expressed in the homogeneous linear recurrence form, which results in achieving maximum parallelism. To speed up the searching for a solution, a heuristic search algorithm called dynamical highest level first/most immediate successors first (DHLF/MISF) is proposed to find a fast but suboptimal schedule. For an optimal schedule, the minimum-scheduled-length problem can be solved by a state-space search method. An objective function is defined in terms of the task execution time, and the optimization of the objective function is based on the minimax of the execution time. The proposed optimization algorithm solves the minimum-scheduled-length problem in pseudopolynomial time and can be used to solve various large-scale problems in a reasonable time.

Original languageEnglish (US)
Title of host publicationUnknown Host Publication Title
PublisherIEEE
Pages1146-1151
Number of pages6
ISBN (Print)0818608528
StatePublished - Jan 1 1988
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Fingerprint Dive into the research topics of 'EFFICIENT SCHEDULING ALGORITHMS FOR ROBOT INVERSE DYNAMICS COMPUTATION ON A MULTIPROCESSOR SYSTEM.'. Together they form a unique fingerprint.

Cite this