Practicas de modelización de problemas de búsqueda y optimización
Enviado por jorgecasanova58 • 14 de Diciembre de 2016 • Trabajo • 299 Palabras (2 Páginas) • 96 Visitas
Practicas de modelización de problemas de búsqueda y optimización
Curso 2003 – 2004
Práctica 1
Para modelizar un problema de búsqueda y optimización tenemos que pasar necesariamente por tres etapas:
- Definición de las variables.
- Determinación del dominio de dichas variables.
- Restricciones del problema.
En primer lugar vamos a definir las variables y sus dominios que intervienen en nuestro problema de búsqueda:
Debemos realizar t tareas:
T = {Ti | 1 ≤ i ≤ t}
El dominio de la variable tarea es:
D = {1,t}
De cara a la optimización de la solución tenemos que definir una variable que nos determine el tiempo máximo que tardarán en ejecutarse todas las tareas para cada distribución:
MAXT
Una vez están determinadas todas las variables y sus dominios tenemos que imponer las restricciones del problema:
En las tares de la lista L = (Ti1,Tj2) ha de realizarse antes Ti1 antes que Tj2 :
∀ i,j 1 ≤ j ≤ t Ti1+Di ≤ Tj2
Un operador no puede realizar dos tareas al mismo tiempo:
∀ i,j 1 ≤ i < j ≤ t (OTi= OTj ⇒ Ti+Di ≤ Tj ∨ Tj+Dj ≤ Ti )
Una máquina no puede realizar dos tareas al mismo tiempo :
∀ i,j 1 ≤ i < j ≤ t (MTi= MTj ⇒ Ti+Di ≤ Tj ∨ Tj+Dj ≤ Ti )
Ahora necesitamos un parámetro que nos indique el tiempo que tardan en realizarse todas las tareas para cada distribución diferente:
MAXT = max { ti + Di ⏐ 1
Nuestra solución óptima será la distribución de tareas cuya duración MAXT sea la menor de todas.
...