Catálogo de publicaciones - tesis
Título de Acceso Abierto
Un enfoque poliedral del problema de secuenciamiento de tareas en procesadores heterogéneos bajo relaciones de precedencia
Pablo E. Coll Celso C. Ribeiro
publishedVersion.
Resumen/Descripción – provisto por el repositorio digital
Estudiamos un algoritmo exacto para el problema de secuenciamiento de tareas en procesadores heterogéneos bajo relaciones de precedencia. En este problema contamos con conjuntos de procesadores y tareas. Las tareas están descriptas por sus duraciones y por un digrafo acíclico de precedencias. El conjunto de procesadores heterogéneos es tal que no pueden establecerse relaciones entre procesadores, tareas y tiempos de procesamiento. No se permitiran las interrupciones de las tareas una vez comenzadas. El objetivo del problema es minimizar el tiempo necesario para completar todas las tareas. Una aplicación se presenta en el contexto de asignar tareas de programas paralelos en computadoras multiprocesador o sistemas distribuidos. Se propone una nueva formulación como problema de programación lineal entera. Esta formulación tiene menos restricciones y variables que las formulaciones previas. Se estudia un poliedro acotado consistente de un subconjunto de desigualdades de la nueva formulación. El poliedro de partición en ordenes lienales (PLO) por sus siglas en inglés, es una relajación y una proyección del poliedro original. Se estudia en detalle el poliedro PLO y se encuentra que muchos resultados son una generalización de aquellos hallados para el poliedro de partición en subgrafos completos [21]. Las desigualdades obtenidas para este poliedro es muy probable que jueguen un importante papel en la formulación y resolución exacta a través de algoritmos de bifurcación y corte de una familia de problemas de secuenciamiento de múltiples máquinas. Finalmente, se desarrolla un algoritmo de bifurcación y corte basado en los cortes específicos desarrollados para el problema en cuestión e igualdades que definen facetas del poliedro PLO y se detallan los resultados computacionales.Palabras clave – provistas por el repositorio digital
No disponibles.
Disponibilidad
| Institución detectada | Año de publicación | Navegá | Descargá | Solicitá |
|---|---|---|---|---|
| No requiere | 2002 | Biblioteca Digital (FCEN-UBA) (SNRD) |
|
Información
Tipo de recurso:
tesis
Idiomas de la publicación
- español castellano
País de edición
Argentina
Fecha de publicación
2002
Información sobre licencias CC