Magíster en Ciencias de la Ingeniería, Mención Matemáticas Aplicadas / En este trabajo se estudia una versión en línea del problema de Cubrimiento de Máquinas Paralelas. En este problema buscamos asignar trabajos a una cierta cantidad de máquinas idénticas, maximizando la carga de la máquina menos cargada. En el problema en linea los trabajos son revelados uno a uno sucesivamente, y ante la llegada de cada trabajo el programador debe decidir a qué máquina asignar el trabajo. A diferencia del modelo clásico, donde las decisiones son irrevocables, se considera un modelo dinámico introducido por Sanders et al. \cite{SSS09}. En este modelo, ante la llegada de un trabajo nuevo, algunos trabajos anteriores pueden ser reasignados. Sin embargo la carga total de trabajos migrados debe ser a lo más proporcional al tamaño del trabajo entrante. La constante de proporcionalidad se denomina \emph{factor de migración} del algoritmo, y mide la robustez de las soluciones construidas.
En primer lugar se estudian algoritmos de búsqueda local, ya que gran parte de estos algoritmos pueden ser adaptados de manera sencilla al contexto en línea con migración. Se demuestra que para la vecindad de \emph{Saltos} e \emph{Intercambios}, el factor de aproximación de una solución localmente óptima yace en el intervalo $[1.691, 1.723]$. Además, usando técnicas de sensibilidad para programación entera, se da una vecindad para la cual las soluciones localmente óptimas son $(1+\e)$-aproximadas y pueden ser halladas en una cantidad polinomial de iteraciones, obteniéndose un PTAS basado exclusivamente en búsqueda local.
Posteriormente se analizan y diseñan algoritmos para el problema en línea con migración. El primer resultado es una mejora en la cota inferior del factor de competitividad alcanzable con migración constante de $\frac{20}{19}$ obtenida por Skutella y Verschae \cite{SV10} a $\frac{17}{16}$. Luego, utilizando un procedimiento de redondeo para la instancia distinto al usado en trabajos anteriores, denominado redondeo a múltiplos, se diseña una versión en línea de optimalidad local respecto a saltos con factor de migración $O\left(\frac{1}{\e}\log\frac{1}{\e}\right)$. Modificando esta propiedad levemente, se obtiene un algoritmo $\left(\frac{3}{2} + \e\right)$-competitivo usando factor de migración $O\left(\frac{1}{\e}\log\frac{1}{\e}\right)$. Finalmente, explotando la simetría otorgada por el redondeo a múltiplos, se diseña una versión en línea de $\LPT$, que es una $(\frac{4}{3}+\e)$-aproximación para el problema de Cubrimiento de Máquinas, con factor de migración $O\left(\frac{1}{\e^3}\log\frac{1}{\e}\right)$. Usando la intuición generada por esta simetría junto a las técnicas de programación entera y \emph{configuraciones} de máquinas, se obtiene un nuevo programa entero para el problema que es más simple y abre las puertas a obtener un PTAS para el problema de Minimización de Makespan en línea cuyo factor de migración tenga dependencia polinomial en $\frac{1}{\e}$, lo que aún es un problema abierto.
| Identifer | oai:union.ndltd.org:UCHILE/oai:repositorio.uchile.cl:2250/137502 |
| Date | January 2015 |
| Creators | Gálvez Verdugo, Waldo Elías |
| Contributors | Soto San Martín, José, Facultad de Ciencias Físicas y Matemáticas, Departamento de Ingeniería Matemática, Verschae Tannenbaum, José, Correa Haeussler, José |
| Publisher | Universidad de Chile |
| Source Sets | Universidad de Chile |
| Language | Spanish |
| Detected Language | Spanish |
| Type | Tesis |
| Rights | Atribución-NoComercial-SinDerivadas 3.0 Chile, http://creativecommons.org/licenses/by-nc-nd/3.0/cl/ |
Page generated in 0.0017 seconds