**Objectives** A mobile agent system is a single, unified framework
in which many
distributed applications can be easily designed using agents. The
goal of this research is to develop the matching and scheduling
algorithms that allow multiple distributed applications to effectively
share the resources within a mobile agent system.
We propose to build a hierarchical scheduling framework, in which a
global (or local) resource manager is a special agent that provides
matching and scheduling services to applications, in heterogeneous
environment. This kind of multi-agent-multi-resource scheduling
problem has several major differences compared with scheduling in
traditional computation systems: a mobile agent system has much larger
data transfer delay, more diversified network links and wider spectrum
of machine speeds.

**Problem Definition** Given a multi agent application in which
each
agent has to visit multiple resources in order to complete a task,
find a schedule for giving agents access to resources that optimizes
the system throughput. The agents may have sequential or parallel
constraints on accessing resources. This suggests a natural
representation of the problem as a DAG scheduling problem. Given a
weighted Directed Acyclic Graph (DAG) G = (J, E) that represents a
distributed application, where J is the set of agents (tasks) and
E is the set of weighted edges that represents precedence
constraints and data paths among tasks, find a schedule of minimal
makespan that allocates tasks onto a set of machines M.

**Technical Approach** The challenge in this research is to
develop scheduling algorithms
that are effective in the context of mobile agent system, where many
assumptions used in traditional scheduling algorithms become
unrealistic. Scheduling algorithms for mobile agent system must work
in a heterogeneous environment where (1) the number of machines is
limited; (2) the task graph structure is general; (3) the data transfer
delay is general; and (4) the task duplication is not allowed. This
problem is NP_Complete. We have already developed two offline
scheduling algorithms. We proved an upper bound for these algorithms in
homogeneous environment and showed their good performance in
heterogeneous environment by extensive simulations. Our results show
that our algorithm outperforms one major existing algorithm ([1]) that
attempts to address data transfer delays in homogeneous networks
when the data transfer delays are large. We
have also shown a performance improvement for our extension
of ([1]) over heterogeneous environments.

**Open Problems** Many aspects of this multi-agent-multi-resource
scheduling problem are remained for our future work, including: (1)
expanding our model to represent a wider range of mobile-agent-based
distributed applications; (2) developing some local adjustment
techniques to improve performance; (3) computing an upper bound in
heterogeneous environment; (4) developing an online scheduling algorithm;
(4) developing a distributed version of these algorithms.

[1] G.C.Sih and E.A. Lee, "A compile-time scheduling heuristic for interconnection-constrained heterogeneous processor architectures", IEEE Trans. Parallel and Distributed Systems, vol.4, pp175-187, Feb.1993.