This paper studies the case of a supply chain made up of autonomous facilities (represented by software agents). They need to coordinate their manufacturing operations in order to optimize customer satisfaction. Most of the coordination mechanisms used in practice can be described as heuristics. We show how they can be generalized to consider the entire coordination space, which can be represented as a tree. This reformulation of the coordination problem as a tree calls for its optimization using a distributed tree search algorithm (e.g. SyncBB). This allows for the exploration of alternative solutions by the agents while maintaining current business relationships, responsibilities and local decision-making algorithms. SyncBB provided great improvements in solution quality in comparison with current practice. The main contribution of this paper is MacDS, a novel method which permits agents to systematically search the solution space (thus look for the optimal solution) but aims at producing good solutions in a short period of time. It uses the concept of discrepancy so that agents collectively prioritize the parts of the tree to search first. Moreover, MacDS allows agents to work concurrently so as to speed up the search process. Use of this mechanism has improved the quality of solutions and computation time for both real industrial problems and generated problems.