Mapping Flows onto Networks to Optimize Organizational Processes
Abstract
Interdependence of tasks in a mission necessitates information flow among the organizational elements (agents) assigned to these tasks. This information flow introduces communication delays. An effective task schedule that minimizes the total execution time, including task processing and coordination delays, is an important issue in designing an organization and its task processing strategy. This paper defines the structure of information-dependent tasks, and describes an approach to map this structure to a network of organizational elements (agents). Since the general problem of scheduling tasks with communication is NP-hard, only fast heuristic (e.g., list scheduling and linear clustering) algorithms are discussed. The authors modify the priority calculation for list scheduling methods, matching the critical path with a network of heterogeneous agents. They then present their algorithm, termed Heterogeneous Dynamic Bottom Level (HDBL), and compare it with various list-scheduling heuristics. The results show that HDBL exhibits superior performance to all list scheduling algorithms, providing an improvement of over 25% in schedule length for communication-intensive task graphs.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 2005
- Accession Number
- ADA440387
Entities
People
- David Lee Kleinman
- Georgiy M. Levchuk
- Krishna R. Pattipati
- Yuri N. Levchuk
Organizations
- University of Connecticut