Journal article
On the Problem of Scheduling Parallel Computations of Multibody Dynamic Analysis
Journal of dynamic systems, measurement, and control, Vol.121(3), pp.370-376
09/01/1999
DOI: 10.1115/1.2802484
Abstract
A formulation of a graph problem for scheduling parallel computations of multibody dynamic analysis is presented. The complexity of scheduling parallel computations for a multibody dynamic analysis is studied. The problem of finding a shortest critical branch spanning tree is described and transformed to a minimum radius spanning tree, which is solved by an algorithm of polynomial complexity. The problems of shortest critical branch minimum weight spanning tree (SCBMWST) and the minimum weight shortest critical branch spanning tree (MWSCBST) are also presented. Both problems are shown to be NP-hard by proving that the bounded critical branch bounded weight spanning tree (BCBBWST) problem is NP-complete. It is also shown that the minimum computational cost spanning tree (MCCST) is at least as hard as SCBMWST or MWSCBST problems, hence itself an NP-hard problem. A heuristic approach to solving these problems is developed and implemented, and simulation results are discussed.
Details
- Title: Subtitle
- On the Problem of Scheduling Parallel Computations of Multibody Dynamic Analysis
- Creators
- J. F Liu - Department of Mechanical Engineering and Center for Computer Aided Design, The University of Iowa, Iowa City, IA 52242K. A Abdel-Malek - Department of Mechanical Engineering and Center for Computer Aided Design, The University of Iowa, Iowa City, IA 52242
- Resource Type
- Journal article
- Publication Details
- Journal of dynamic systems, measurement, and control, Vol.121(3), pp.370-376
- Publisher
- ASME
- DOI
- 10.1115/1.2802484
- ISSN
- 0022-0434
- eISSN
- 1528-9028
- Language
- English
- Date published
- 09/01/1999
- Academic Unit
- Roy J. Carver Department of Biomedical Engineering; Mechanical Engineering
- Record Identifier
- 9984064117702771
Metrics
17 Record Views