Practicas de modelización de problemas de búsqueda y optimización

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:

1. Definición de las variables.
2. Determinación del dominio de dichas variables.
3. 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.

...