PROBLEM DECOMPOSITION IN DISTRIBUTED PROBLEM-SOLVING SYSTEMS

Distributed Problem Solving (DPS) is defined as the cooperative soluti on of problems by a decentralized and loosely coupled collection of pr oblem solvers (agents), each of them knowing how to execute only some of the necessary tasks. This approach considers the problem-solving pr ocess as occurring in three phases: problem decomposition, subproblem solution, and answer synthesis. In the problem decomposition phase, on e has to determine which tasks will be executed by each agent and when . One of the key research questions in the problem decomposition proce ss is how to decompose a problem in order to minimize the cost of reso urces needed for its solution. In this article, we construct mathemati cal programming models in order to describe the decomposition process under the above criterion, study its complexity, and present exact and heuristic algorithms for its solution. Our work was motivated by the operation of an actual system that can be considered as a distributed problem solver for the assessment of irrigation projects design.