Un enfoque poliedral del problema de secuenciamiento de tareas en procesadores heterogéneos bajo relaciones de precedencia

Coll, Pablo E.

Registro:

Documento:	Tesis Doctoral
Disciplina:	computacion
Título:	Un enfoque poliedral del problema de secuenciamiento de tareas en procesadores heterogéneos bajo relaciones de precedencia
Autor:	Coll, Pablo E.
Editor:	Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales
Filiación:	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
Director:	Ribeiro, Celso C.
Director Asistente:	Carvalho de Souza, Cid
Idioma:	Español
Formato:	PDF
Handle:	http://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:	Dep.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 E.. (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 http://hdl.handle.net/20.500.12110/tesis_n3468_Coll

Resumen:

Estudiamos un algoritmo exacto para el problema de secuenciamiento de tareas en procesadoresheterogéneos bajo relaciones de precedencia. En este problema contamos con conjuntos de procesadores y tareas. Las tareas están descriptas porsus duraciones y por un digrafo acíclico de precedencias. El conjunto de procesadores heterogéneos estal que no pueden establecerse relaciones entre procesadores, tareas y tiempos de procesamiento. No sepermitiran las interrupciones de las tareas una vez comenzadas. El objetivo del problema es minimizarel 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óntiene 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 muchosresultados 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 desarrolladospara el problema en cuestión e igualdades que definen facetas del poliedro PLO y se detallanlos 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 E.. (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 E.. "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 :

Navegar

Colección

Tesis Doctoral