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

Mostrar todas las versiones(3)

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 conju...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autor principal: Coll, Pablo E.
Otros Autores: Ribeiro, Celso C.
Formato: Tesis doctoral publishedVersion
Lenguaje:Español
Publicado: Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales 2002
Acceso en línea:https://hdl.handle.net/20.500.12110/tesis_n3468_Coll
http://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesis&d=tesis_n3468_Coll_oai
Aporte de:
Repositorio Digital de la Universidad de Buenos Aires (UBA) de Universidad de Buenos Aires
id I28-R145-tesis_n3468_Coll_oai
record_format dspace
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-145
collection Repositorio Digital de la Universidad de Buenos Aires (UBA)
language Español
orig_language_str_mv spa
description 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.
author2 Ribeiro, Celso C.
author_facet Ribeiro, Celso C.
Coll, Pablo E.
format Tesis doctoral
Tesis doctoral
publishedVersion
author Coll, Pablo E.
spellingShingle Coll, Pablo E.
Un enfoque poliedral del problema de secuenciamiento de tareas en procesadores heterogéneos bajo relaciones de precedencia
author_sort Coll, Pablo E.
title Un enfoque poliedral del problema de secuenciamiento de tareas en procesadores heterogéneos bajo relaciones de precedencia
title_short Un enfoque poliedral del problema de secuenciamiento de tareas en procesadores heterogéneos bajo relaciones de precedencia
title_full Un enfoque poliedral del problema de secuenciamiento de tareas en procesadores heterogéneos bajo relaciones de precedencia
title_fullStr Un enfoque poliedral del problema de secuenciamiento de tareas en procesadores heterogéneos bajo relaciones de precedencia
title_full_unstemmed Un enfoque poliedral del problema de secuenciamiento de tareas en procesadores heterogéneos bajo relaciones de precedencia
title_sort un enfoque poliedral del problema de secuenciamiento de tareas en procesadores heterogéneos bajo relaciones de precedencia
publisher Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales
publishDate 2002
url https://hdl.handle.net/20.500.12110/tesis_n3468_Coll
http://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesis&d=tesis_n3468_Coll_oai
work_keys_str_mv AT collpabloe unenfoquepoliedraldelproblemadesecuenciamientodetareasenprocesadoresheterogeneosbajorelacionesdeprecedencia
_version_ 1766015572766621696
spelling I28-R145-tesis_n3468_Coll_oai2023-04-26 Ribeiro, Celso C. Coll, Pablo E. 2002 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. 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. Fil: Coll, Pablo E.. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. application/pdf https://hdl.handle.net/20.500.12110/tesis_n3468_Coll spa Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales info:eu-repo/semantics/openAccess https://creativecommons.org/licenses/by-nc-sa/2.5/ar Un enfoque poliedral del problema de secuenciamiento de tareas en procesadores heterogéneos bajo relaciones de precedencia info:eu-repo/semantics/doctoralThesis info:ar-repo/semantics/tesis doctoral info:eu-repo/semantics/publishedVersion http://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesis&d=tesis_n3468_Coll_oai

Ejemplares similares