técnicas distribuidas para problemas de scheduling a gran escala

Técnicas Distribuidas para Problemas

de Scheduling a Gran Escala

Miguel A. Salido, M. Abril, F. Barber, P. Tormos, A. Llova, L. Ingolotti

Univerisdad Politécnica de Valencia España

GTI-IA, DSIC

IV Workshop Planificación, Scheduling y Razonamiento Temporal

Santiago de Compostela, 15 de Noviembre de 2005

Santiago de Compostela, 15/11/2005 PSRT’05 Workshop sobre Planificación, Scheduling y Razonamiento Temporal

Introducción Modelo Ejemplo Aplicación Evaluación Conclusiones

Índice

1. Introducción

2. Modelo Distribuido

3. Ejemplo

4. Planificación de Rutas ferroviarias

5. Evaluación

6. Conclusiones y Trabajo Futuro



Definitions

CSP• Variables: x1, x2, ....., xn

• Domains : xiDi:{ai, bi} : i=1..n

• Constraints: {c1,c2,..,ck}

Railway Scheduling Problem

• Variables: departure & arrival time at stations

• Domain: Integers

• Constraints:

• Railway infrastructure• User Requirements • Traffic Rules Graph Partitioning

• Objective: Divide the graph into a set of regions:

• Each region has roughly the same number of nodes

• The sum of all edges connecting different regions is minimized.



A distributed CSP is a CSP in which the variables and constraints are

distributed among block agentsblock agents and there are interagent constraints.

Distributed CSP

A block agent is a virtual entity that essentially has the following

properties: autonomy, sociability, reactivity and pro-activity.

• Each block agent has a semi-independent subproblem Each block agent has a semi-independent subproblem

(variables and constraints) and attempts to determine the (variables and constraints) and attempts to determine the

variable values.variable values.

• these values must also satisfy the interagent constraints.these values must also satisfy the interagent constraints.



Distributed Model

Preprocessing Agent

Problem solutionProblem Solutions Storage

Agent 2

Variables involved: v2,v2

Co

nstr

aint

invo

lved

Domain of new variables v2

Assigment of

managed variables

Partial problem solutions

Agent 1

Variables involved: v1

Co

nstr

aint

invo

lved

Domain of new variables v1

Assigment of

managed variables

Agent k

Variables involved: vk,vk

Co

nstr

aint

invo

lved

Domain of new variables vk

Partial problem solutions

Assigment of

managed variables

ca

br1

r3

r2

h

g

f

r9

r8

r7

d

e

r6

c

h

g

fa

b

d

e

r1

r3

r2

r4

r9

r8

r7r5r6

i

j

r11r10



Preprocessing Agent

• Preprocessing Agent carries out a partition of the original problem in semi-independent subproblems.

• It uses a graph partitioning software called METIS*.METIS*.

• METISMETIS solves the partition problem efficiently.

14.000 nodes14.000 nodes

410.000 edges410.000 edges

2 seconds2 seconds

*www-users.cs.umn.edu/karypis/metis/index.html



Block Agents

Variables involved: vid,vid

Assigmentof

managedvariables

Partialproblemsolutions

Domain of new variables vid

SubproblemSubproblem

c1:2x1+x3+2x5

c2:x1-x3

c3:x3-2x5+x7

c4:2x3+x5-2x7

Var:x1,x3,x5,x7

c5:x1+4x2+2x5

c6:x1+x2+x3

c7:3x1-2x7+x8

c8:2x3+x5-2x7

c9:2x2+x3-2x8

Used Variables:x1,x3,x5,x7

New Variables:x2,x4,x8

Domains: x2,x4,x8

(3,-,1,-,2,-,3,-,...)

x1 x3 x5 x7

(3,4,1,1,2,-,3,-2,...)x2 x4 x8

c

h

g

fa

b

d

e

r1

r3

r2

r4

r9

r8

r7r5r6

Agent Id.

Con

stra

ints

invo

lved



Example

Agentmar 1 abr

2 121154 1073 8

1

2

6 9 1 2 3

Time steps

c2

c1

Block agents 1 2 3 4 5 6 7

(-,1,1)

(1,1,1)

(-,1,2)

(2,1,1)

(-,2,1)

(3,1,1)

(-,2,2)

(1,2,2)

(-,2,3)

(2,2,2) (3,2,2)

Three variables:x1, x2, x3

Domains:

d1:{1,2,3}d2:{1,2}d3:{1,2,3}

Constraints:c1: x2 = x3

c2: x1 ≠ x2



Railway Scheduling Problem

TIME

Initial departure

time

Stations(crossing and overtaking)

Halts(only commercial stops)

New Trains to be added

Periodic Trains(frequency) or notor notOne, two-way

tracksOver a set of previouslyOver a set of previously

scheduled trainsscheduled trains

The problem:The problem: To assist to railway managers in order to obtain

a correct railway schedule.

The problem:The problem: To assist to railway managers in order to obtain

a correct railway schedule.



Our Approach: CSP

The railway scheduling problem as a Constraint Satisfaction Problem:

VariablesVariables (departure & arrival time to stations): {Train{Trainii_Arrival_Arrivaljj, Train, Trainii_Departure_Departurejj}}

Interpretation domainInterpretation domain: Integers : Integers

Constraints:Constraints:

Infrastructure Constraints:Infrastructure Constraints:

Travel time between stations.

Maintenance times

Number of tracks in stations and sections,…

Traffic constraintsTraffic constraints:

Crossing and Overtaking.

Reception-time, Expedition-time.

Succession time between two consecutive trains,…

User Requirements:User Requirements:

Initial departure of first train, frequency, maximum travel time.

Type and Number of trains.

Commercial Stops,…

In typical and simple cases thousandsand thousands of alternatives

In typical and simple cases thousandsand thousands of alternatives

Exponential Search Space



How distribute the problem?

1. The preprocessing agent carries out the partition by means of METIS 1. The preprocessing agent carries out the partition by means of METIS

2. It divides the running map into clusters composed by contiguos stations



How distribute the problem?

1. The preprocessing agent carries out the partition by type of train



ProblemsDistributed

CSPCentralized

CSP

<50,25,10> 12 3

<100,25,10> 12 14

<150,25,10> 15 37

<200,25,10> 16 75

<250,25,10> 17 98

<300,25,10> 19 140

<350,25,10> 23 217

<400,25,10> 30 327

<450,25,10> 32 440

<500,25,10> 42 532

Random Problems

< n,a,p >

n: variables

a: arity

p: partition size



Number of Constraints & Running Time

0

500

1000

1500

2000

2500

78 (3

5)

157(

70)

241(

110)

378(

203)

527(

308)

676(

413)

859(

552)

1078

(727

)

Number of Constraints

Tim

e (s

c).

Complete

distribuited

Distributed Railway



Distributed Railway

Constraints&Running Time

1

10

100

1000

10000

100000

1000000

10000000

100000000

157

378

676

1078

1711

,432

8

2717

,070

7

4313

,621

5

6848

,305

4

1087

2,37

1726

0,97

4

2740

3,52

3

Number of Constraints

Tim

e in

Sec

on

ds

distributed

complete



Conclusions

•A distributed model for solving large-scale CSPs was present • A preprocessing agent partitions the problem in semi-independent sub-CSPs

• A set of block agents incrementally and concurrently built partial solutions until a global solution is found.

• Each block agent may solve its subproblem with different algorithms

• Large CSPs (Railway Scheduling Problems) could be solved more efficiently.



Future Works

• The Railway Scheduling Problem can be partitioned by different ways.

• We are working on techniques to partition the problem, depending on the problems objective.

• Evaluate the ways in which Railway Scheduling Problem can be distributed.

Técnicas Distribuidas para Problemas

de Scheduling a Gran Escala

Miguel A. Salido, M. Abril, F. Barber, P. Tormos, A. Llova, L. Ingolotti

Univerisdad Politécnica de Valencia España

GTI-IA, DSIC

IV Workshop Planificación, Scheduling y Razonamiento Temporal

Santiago de Compostela, 15 de Noviembre de 2005

técnicas distribuidas para problemas de scheduling a gran escala

Documents