Distributed Constraints for Large-Scale Scheduling Problems | Zendy

Montserrat Abril | Zendy; Miguel Á. Salido | Zendy; Federico Barber | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Distributed Constraints for Large-Scale Scheduling Problems

Author(s) -

Montserrat Abril,

Miguel Á. Salido,

Federico Barber

Publication year - 2005

Publication title -

lecture notes in computer science

Language(s) - English

Resource type - Book series

SCImago Journal Rank - 0.249

H-Index - 400

eISSN - 1611-3349

pISSN - 0302-9743

DOI - 10.1007/11564751_75

Subject(s) - computer science , scheduling (production processes) , partition (number theory) , graph partition , distributed computing , constraint satisfaction problem , parallel computing , mathematical optimization , graph , theoretical computer science , artificial intelligence , mathematics , combinatorics , probabilistic logic

Many problems of theoretical and practical interest can be formulated as Constraint Satisfaction Problems (CSPs). The general CSP is known to be NP-complete; however, distributed models may re- duce the exponential complexity by partitioning the problem into a set of subproblems. In this work, we present a distributed model for solving large-scale CSPs in which agents are committed to sets of constraints. Our technique carries out a partition over the constraint network by a graph partitioning software, such as each subproblem is as indepen- dent as possible and, it can be solved in a reasonable time. We have focused our research to railway scheduling problem where the resultant CSP maintains thousand of variables and constraints.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research