Multi-Agent systems are being more and more widely used to address many distributed combinatorial real-world problems. One such problem is meeting scheduling (MS) that is characterized essentially by two features defined from both its inherently distributed and dynamic nature. In addition, in real world applications, users usually have conflicting preferences, which make the search for an optimal solution an NP-hard problem.

However, the majority of the existing works on MS tackle it as a static problem, allow for the relaxation of any constraints and do not deal with achieving any level of consistency. In an attempt to overcome these limitations, the main contribution of this work is a new distributed approach based on the DRAC model (distributed reinforcement of arc consistency) to solve dynamic MS problems. In this approach we authorize only the relaxation of users? preferences while maintaining arc-consistency on the problem. The underlying protocol is able to efficiently reach optimal solution (satisfying some predefined optimality criteria) whenever possible, using only localized asynchronous communications. This purpose is achieved with minimal message passing and without compromising the privacy of involved users. A comparative analysis divulges that our approach is scalable and worthwhile especially handling strong constraints.