Sesion1

Metodología RdP a PSR

Metodología RdP a PSR

1. Optimización y Simulación como herramientas en la mejora de la producción Daniel Riera i Terrén Abril 2006

2. Programación con Restricciones y PSR’s 3. Formalismo de modelado: Redes de Petri

Universitat Oberta de Catalunya Universitat Autònoma de Barcelona

4. Metodología RdP-PSR 5.

Ejemplo

6.

Conclusiones y trabajo actual/futuro

Metodología RdP a PSR 1. Optimización y Simulación como herramientas en la mejora de la producción 2. Programación con Restricciones y PSR’s

Principales factores que fuerzan el diseño de nuevas arquitecturas de producción: • Competencia globalizada • Demandas aleatorias en vez de estacionarias • Tiempo de vida corto de los productos

3. Formalismo de modelado: Redes de Petri 4. Metodología RdP-PSR 5.

Ejemplo

6.

Conclusiones y trabajo actual/futuro

Nuevas reglas de producción: Make to order Make to stock Gran diversidad Grandes volúmenes de producción de producción

b

a

CNC1

CNC2

CNC3

FMS

• Optimización

Producto final

Materia prima CNCn

• Simulación

• Modelo simplificado • Óptimo (real?)

Política de scheduling

• Modelo detallado • Resultados para ciertos escenarios

Unidades de procesado

Programación con Restricciones

Metodología RdP a PSR 1. Optimización y Simulación como herramientas en la mejora de la producción 2. Programación con Restricciones y PSR’s

¿Qué es la PR? • Potente herramienta de optimización • Aspectos importantes: • Resultados (BA, Cisco Systems, etc.) • Metodología simple

3. Formalismo de modelado: Redes de Petri 4. Metodología RdP-PSR 5.

Ejemplo

6.

Conclusiones y trabajo actual/futuro

• '63 Sketchpad • Evolución: • Modelado declarativo • Propagación de restricciones • Control de la búsqueda explícito

Programación con Restricciones

– PR :

Programación con Restricciones

– PR :

• Lenguage host. • Restricciones.

• Lenguage host. • Restricciones.

– Incorpora técnicas de:

– Incorpora técnicas de:

• Matemáticas. • Algoritmos de búsqueda. • I.A. • ...

• Matemáticas. • Algoritmos de búsqueda. • I.A. • ...

– Se aplica a: • • • •

• • • •

– PR : Sist. de restricciones

Modelado Espacio de soluciones

• Lenguage host. • Restricciones.

– Incorpora técnicas de:

Lenguage host

Sist. de restricciones

Modelado Espacio de soluciones

• Matemáticas. • Algoritmos de búsqueda. • I.A. • ...

– Se aplica a: Scheduling. Planning. Routing. ...

Programación con Restricciones

– PR : Lenguage host

• Matemáticas. • Algoritmos de búsqueda. • I.A. • ... • • • •

Espacio de soluciones

Scheduling. Planning. Routing. ...

Programación con Restricciones

– Incorpora técnicas de:

Modelado

– Se aplica a:

Scheduling. Planning. Routing. ...

• Lenguage host. • Restricciones.

Lenguage host

– Se aplica a: Muy importantes ya que nos permiten eliminar soluciones no factibles

• • • •

Scheduling. Planning. Routing. ...

Alg.’s de búsqueda

Heurísticas

Programación con Restricciones

• PSR (Problema de Satisfacción de Restricciones) ¾ Conjunto de variables que permitan representar el sistema a optimizar ¾ Dominio de valores factibles que puede tomar cada variable ¾ Restricciones que limitan los valores compatibles para las variables del sistema

Programación con Restricciones

Tipos de restricciones (depende del solver): • Lineales

• No lineales

• Suspensiones

Programación con Restricciones

• PSR (Problema de Satisfacción de Restricciones) • Paradigma basado en la generación de árbol de soluciones • Utiliza técnicas de Forward Checking para eliminar soluciones no factibles. Esto lo hace mediante propagación de restricciones • Control de la búsqueda explícito: • Aplicación de heurísticas propias de la PR • Combinación con algoritmos de búsqueda local y otros

Programación con Restricciones

Heurísticas para la búsqueda: • Orden de selección de las variables. • Orden de selección valores de los dominios.

21

Heurísticas comunes: • deletemin • deleteff • deleteffc

27

Programación con Restricciones

Metodología RdP a PSR

Combinación con otras tecnologías:

1. Optimización y Simulación como herramientas en la mejora de la producción

• Algoritmos de búsqueda: • Simulated annealing • Tabu search • Algoritmos genéticos • Investigación operativa: • Programación lineal • Programación cuadrática

2. Programación con Restricciones y PSR’s 3. Formalismo de modelado: Redes de Petri 4. Metodología RdP-PSR 5.

Ejemplo

6.

Conclusiones y trabajo actual/futuro

Redes de Petri

Redes de Petri

¿Qué herramienta de modelado usar? Red de Petri: Sistemas de producción b

a

CNC1

CNC2

CNC3

Producto final

Materia prima CNCn

Sistema Orientado a Eventos Discretos (SOED)

Unidades de procesado

Hoy en día, no hay una metodología aceptada por la comunidad dedicada a la simulación para formalizar el conocimiento acerca de sistemas de producción y logísticos. Los SOEDs son sistemas complejos. Esta complejidad no es una propiedad inherente al sistema sino debida a la falta de una metodología y herramientas que permitan especificar y formalizar el conocimiento que tenemos del sistema.

9 Modela estructura estática y dinámica 9 Concurrencia, sincronización, recursos compartidos 9 Optimización:

Redes de Petri

Metodología RdP a PSR Características de las RdP con las que trabaja la metodología presentada:

1. Optimización y Simulación como herramientas en la mejora de la producción 2. Programación con Restricciones y PSR’s

• Generalizada (pesos en los arcos) • Marcada • Con capacidad finita • Temporizada • Sin arcos inhibidores

3. Formalismo de modelado: Redes de Petri 4. Metodología RdP-PSR 5.

Ejemplo

6.

Conclusiones y trabajo actual/futuro

Introducción

Introducción

Metodología: Vista general

Metodología para la optimización de Sistemas de Producción modelados mediante Redes de Petri.

Solución óptima Modelo RdP,

Modelo

M0 y Mf

PSR

Solver de PR

Metodología: Vista general

Simulador

• Idea: • Dada una RdP, identificar los componentes del PSR (i.e. variables, dominios y restricciones) Variables:

Metodología: Vista general

Metodología: Vista general

Metodología: Vista general

Metodología: Vista general

• Idea: • Dada una RdP, identificar los componentes del PSR (i.e. variables, dominios y restricciones)

• Idea: 9 Dada una RdP, identificar los componentes del PSR (i.e. variables, dominios y restricciones) • Generar restricciones de las estructuras encontradas en la RdP: - Lugares - Transiciones - Recursos compartidos

Dominios:

Generación de restricciones

Generación de restricciones

Estructuras consideradas: Plazas Sequence Branch

Generación de restricciones

[Balance de marcas]

Meet

Meet-Branch

IS y C

Sequence Branch

p

t

in

t

in1

tin

t

in2

t

ink

t

in1

t

t

in2

ink

p

p

t

t

t

t

t

t

o u t1

o u t2

tin

o u tq

p in 1

tout

t

1

Transiciones Transition ti

t

2

t

k

t

out

t

out1

t

out2

in 2

in k

t

outq

p

tout

Meet

Meet-Branch

IS y C

Generación de restricciones

Generación de restricciones

Generación de restricciones

Generación de restricciones

[Balance de marcas]

[Balance de marcas]

Sequence Branch t

tin

Meet

Meet-Branch

IS y C

Sequence Branch

in

t

tin

p

in

Meet t

in1

t

in2

Meet-Branch

IS y C

t

ink

p

p

tout

t

t

1

2

tout

t

k

t

t

1

2

t

t

out

k

Generación de restricciones

Generación de restricciones

Generación de restricciones

Generación de restricciones

[Balance de marcas]

[Balance de marcas]

Sequence Branch t

tin

in

Meet t

in1

t

in2

Meet-Branch t

ink

t

in1

t

t

in2

ink

IS y C

Sequence Branch t

tin

in

Meet t

in1

p

t

in2

Meet-Branch t

ink

t

in1

t

1

t

2

ink

p

p

p

t

p

t

in2

p

tout

IS y C

t

k

t

out

p

t

out1

t

out2

t

outq

tout

t

1

t

2

t

k

t

out

t

t

t

t

t

t

o u t1

t

out1

t

out2

o u t2

o u tq

t

outq

in 1

in 2

in k

p

Generación de restricciones

Generación de restricciones

Generación de restricciones

Generación de restricciones

[Restr. temporales] Sequence Branch

Meet

[Restr. temporales]

Meet-Branch

Transition

tin

Sequence Branch t

tin

Meet

Meet-Branch

Transition

in

p

tout

tout

t

t

1

2

t

k

Generación de restricciones

Generación de restricciones

Generación de restricciones

Generación de restricciones

[Restr. temporales]

[Restr. temporales]

Sequence Branch t

tin

in

Meet t

in1

t

in2

Meet-Branch Transition t

ink

Sequence Branch t

tin

in

Meet t

in1

p

t

in2

Meet-Branch Transition t

ink

t

in1

t

t

in2

ink

p

p p

tout

t

1

t

2

t

k

t

out

p

tout

t

1

t

2

t

k

t

out

t

out1

t

out2

t

outq

Metodología: Vista general

Generación de restricciones

Generación de restricciones Methodología: Vista general

[Simetrías] Sequence Branch t

tin

in

Meet t

in1

t

in2

Meet-Branch t

ink

t

in1

t

Transition

t

in2

ink

p

p

ti

p

tout

t

1

t

2

t

t

out

k

t

out1

t

out2

t

• Idea: 9 Dada una RdP, identificar los componentes del PSR (i.e. variables, dominios y restricciones) 9 Generar restricciones de las estructuras encontradas en la RdP

outq

9 Algoritmos de pre-procesado 9 Buena estrategia de búsqueda (orden en las variables, búsqueda dicotómica, etc.)

Búsqueda

Búsqueda

Búsqueda

Búsqueda

Orden de instanciación: Cost Número de disparos Booleanas/Orden Tiempos de disparos

Búsqueda dicotómica

Búsqueda dicotómica: DCost

Middle-deleteffc

Checked value

x

LB0

UB0

Solution found? Yes

Heurísticas

x

LB0 LB1

No

x LB1

UB0

Búsqueda

Búsqueda

Metodología RdP a PSR

Heurísticas: • middle Variables de disparo • deleteffc • Recursos compartidos • Límites temporales superior e inferior • Límites temporales dinámicos • Caminos seguidos por las marcas • En estructuras M, B y MB, asignación de pesos a caminos (búsqueda incompleta)

1. Optimización y Simulación como herramientas en la mejora de la producción 2. Programación con Restricciones y PSR’s 3. Formalismo de modelado: Redes de Petri 4. Metodología RdP-PSR 5.

Ejemplo

6.

Conclusiones y trabajo actual/futuro

Ejemplo

Ejemplo

Ejemplo

Ejemplo Red de Petri:

Sistema:

Stock A

Stock B M1 Free

t1

Estructuras:

t2 Proc B in M1

Proc A in M1

A F APBP

t3

t4 M2 Free

M1 B

Assemble

Stock AP

Stock BP t5 Mounting

t6 Stock F

Ejemplo

Metodología RdP a PSR

Ejemplo

1. Optimización y Simulación como herramientas en la mejora de la producción 2. Programación con Restricciones y PSR’s t1 t3, t4

3. Formalismo de modelado: Redes de Petri

t5

4. Metodología RdP-PSR

t6 t2

5.

Ejemplo

6.

Conclusiones y trabajo actual/futuro

Conclusiones

Conclusiones • Se abre una nueva aproximación a la resolución del problema de scheduling de sistemas flexibles basada en RdP como formalismo de modelado y PR como metodología de optimización.

Trabajo futuro

Trabajo Futuro • Adición de nuevas restricciones basadas en estructuras de las RdP o estructuras más complejas como simetrías, etc. • Trabajando en nuevos algoritmos de pre-procesado (límites, etc.). • Mejora de la estrategia de búsqueda mediante: • Diseño de heurísticas para acelerarla.

• La metodología presentada ha demostrado funcionar para ejemplos académicos y, con el uso de búsqueda inteligente, pequeños casos industriales. • La validación del scheduling encontrado mediante un simulador es inmediata dado que el modelo en RdP ya está construido.

• Consideración de búsqueda incompleta. • Trabajo con tipos de RdP más potentes, capaces de incluir más información acerca del sistema. •Utilización de parte de las restricciones para cooperación con árbol de cobertura podando ramas para evitar su generación.

Metodología RdP a PSR Daniel Riera i Terrén Abril 2006 Universitat Oberta de Catalunya Universitat Autònoma de Barcelona