Registro:
| Documento: | Tesis Doctoral |
| Título: | Un enfoque poliedral del problema de secuenciamiento de tareas en procesadores heterogéneos bajo relaciones de precedencia |
| Autor: | Coll, Pablo Enrique |
| Editor: | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales |
| Lugar de trabajo: | Departamento de Computación
|
| Publicación en la Web: | 2017-03-01 |
| Fecha de defensa: | 2002 |
| Fecha en portada: | 2002-09-06 |
| Grado Obtenido: | Doctorado |
| Título Obtenido: | Doctor en Ciencias de la Computación |
| Departamento Docente: | Departamento de Computación |
| Director: | Ribeiro, Celso C. |
| Director Asistente: | Carvalho de Souza, Cid |
| Idioma: | Español |
| Formato: | PDF |
| Handle: |
https://hdl.handle.net/20.500.12110/tesis_n3468_Coll |
| PDF: | https://bibliotecadigital.exactas.uba.ar/download/tesis/tesis_n3468_Coll.pdf |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/tesis/document/tesis_n3468_Coll |
| Ubicación: | COM 003468 |
| Derechos de Acceso: | Esta obra puede ser leída, grabada y utilizada con fines de estudio, investigación y docencia. Es necesario el reconocimiento de autoría mediante la cita correspondiente. Coll, Pablo Enrique. (2002). Un enfoque poliedral del problema de secuenciamiento de tareas en procesadores heterogéneos bajo relaciones de precedencia. (Tesis Doctoral. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales). Recuperado de https://hdl.handle.net/20.500.12110/tesis_n3468_Coll |
Resumen:
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 computadorasmultiprocesador 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 yuna 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 importantepapel en la formulación y resolución exacta a través de algoritmos de bifurcación y corte de una familiade 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.
Abstract:
We study an exact algorithm for the problem of scheduling unrelated processors under precedenceconstraints. In this problem we are given sets of tasks and processors. The tasks are described by their processingtimes and by a directed acyclic graph representing the precedence constraints. The set of unrelatedprocessors is such that no proportional relations can be established between processors, tasks, andprocessing times. Preemption is not allowed. The goal of the Optimization problem is the minimizationof the makespan, i.e., time needed to complete all tasks. An application arises in the context of scheduling tasks of parallel programs in multi-processorcomputers or distributed systems. A new integer programming formulation for the problem is proposed. This formulation has lesscontraints and variables than previous formulations. A polytope consisting of the subset of inequalities of the new formulation that defines a partitionin linear orderings is studied. The partition in linear orderings (PLO) polytope is a relaxation anda projection of the original polytope. The PLO polytope is studied in detail and many results arefound to be generalizations of those of the clique partition polytope [21]. The inequalities obtainedfor this polyhedron are likely to play an important role in the formulation and exact solution viabranch-and-cut algorithms of a family of multiple machines scheduling problems. Finally, a branch-and-cut algorithm is developed based on cuts specific to the scheduling problemunder consideration and on facet defining inequalities for the PLO polytope. Computational resultsare reported.
Citación:
---------- APA ----------
Coll, Pablo Enrique. (2002). Un enfoque poliedral del problema de secuenciamiento de tareas en procesadores heterogéneos bajo relaciones de precedencia. (Tesis Doctoral. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/tesis_n3468_Coll
---------- CHICAGO ----------
Coll, Pablo Enrique. "Un enfoque poliedral del problema de secuenciamiento de tareas en procesadores heterogéneos bajo relaciones de precedencia". Tesis Doctoral, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2002.https://hdl.handle.net/20.500.12110/tesis_n3468_Coll
Estadísticas:
Descargas totales desde :
Descargas mensuales
https://bibliotecadigital.exactas.uba.ar/download/tesis/tesis_n3468_Coll.pdf
