Tesis > Documento


Ver el documento (formato PDF)   Coll, Pablo E..  "Un enfoque poliedral del problema de secuenciamiento de tareas en procesadores heterogéneos bajo relaciones de precedencia"  (2002)
Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires
URL:
     
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 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 . 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.

Abstract:
We study an exact algorithm for the problem of scheduling unrelated processors under precedence constraints. In this problem we are given sets of tasks and processors. The tasks are described by their processing times and by a directed acyclic graph representing the precedence constraints. The set of unrelated processors is such that no proportional relations can be established between processors, tasks, and processing times. Preemption is not allowed. The goal of the Optimization problem is the minimization of the makespan, i.e., time needed to complete all tasks. An application arises in the context of scheduling tasks of parallel programs in multi-processor computers or distributed systems. A new integer programming formulation for the problem is proposed. This formulation has less contraints and variables than previous formulations. A polytope consisting of the subset of inequalities of the new formulation that defines a partition in linear orderings is studied. The partition in linear orderings (PLO) polytope is a relaxation and a projection of the original polytope. The PLO polytope is studied in detail and many results are found to be generalizations of those of the clique partition polytope . The inequalities obtained for this polyhedron are likely to play an important role in the formulation and exact solution via branch-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 problem under consideration and on facet defining inequalities for the PLO polytope. Computational results are reported.

* A este resumen le pueden faltar caracteres especiales. Consulte la versión completa en el documento en formato PDF

Registro:
Título : Un enfoque poliedral del problema de secuenciamiento de tareas en procesadores heterogéneos bajo relaciones de precedencia    
Autor : Coll, Pablo E.
Director : Ribeiro, Celso C.
Director Asistente : Carvalho de Souza, Cid
Año : 2002
Editor : Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires
Filiación : Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales
Departamento de Computación
Pontifícia Universidade Católica do Rio de Janeiro (PUC-Rio)
Universidade Estadual de Campinas (Unicamp)
Grado obtenido : Doctor en Ciencias de la Computación
Ubicación : Preservación - http://digital.bl.fcen.uba.ar/gsdl-282/cgi-bin/library.cgi?a=d&c=tesis&d=Tesis_3468_Coll
Idioma : Español
Area Temática : 
URL al Documento : 
URL al Registro : 
hola chau _gs.DocumentHeader_ chau2 _documentheader_ chau3
Estadísticas:
     http://digital.bl.fcen.uba.ar
Biblioteca Central Dr. Luis Federico Leloir - Facultad de Ciencias Exactas y Naturales - Universidad de Buenos Aires
Intendente Güiraldes 2160 - Ciudad Universitaria - Pabellón II - C1428EGA - Tel. (54 11) 4789-9293 int 34