SUPPLY CHAIN FORMATION IN OPEN, MARKET-BASED MULTI-AGENT SYSTEMS

Efficient allocation of services to form a supply chain to solve complex tasks is a crucial problem. Optimal service allocation based on a single criterion is NP-Complete. Furthermore, complex tasks in general have multiple criteria that may be conflicting and non-commensurable. This paper presents a two-stage brokering algorithm for optimal anytime service allocation based on multiple criteria. In the first stage, a hierarchical task network planner is used to identify the services required to solve a task. In the second stage, a genetic algorithm (GA) determines service providers based on multiple criteria to provide the services identified by the planner. We present our algorithm and results from various experiments conducted to analyze the effect of various parameters that influence the complexity of the problem. In general, the results show the GA finds optimal solutions much quicker than a standard search algorithm. The empirical results also indicate the performance of the algorithm is sub-linear or polynomial time for various parameters. The algorithm has the ability to deal with any number of criteria. By addressing this problem, we expand the range of problems being addressed to any that require simultaneous optimization of multiple criteria and/or planning.