Optimización de ganancias cóncavas en máquinas paralelas

Abstract

El problema de Optimizaci\'on de Ganancias C\'oncavas en M\'aquinas Paralelas consiste en, dados conjuntos $J$ de trabajos, $I$ de m\'aquinas que pueden procesar dichos trabajos y $\{f_j\}_{j \in J}$ de funciones de ganancias c\'oncavas asociados a cada trabajo, encontrar una funci\'on $A:I \times J \to \Q_+$ que \emph{asigna} a cada trabajo $j$ un tiempo de proceso $A_{ij}$ en la m\'aquina $i$ (si $A_{ij}=0$, entonces $j$ no es procesado en la m\'aquina $i$), de modo que $A$ maximiza la ganancia obtenida por el procesamiento de dichos trabajos y al mismo tiempo satisface la capacidad que tienen las m\'aquinas para procesar dichos trabajos. En este trabajo se tratan dos variantes de este problema, las cuales se llaman GCMP \emph{con transferencia} y \emph{sin transferencia}, donde la primera consiste en el caso en que se permite que un mismo trabajo pueda ser procesado en m\'as de una m\'aquina (sin ser simult\'aneo), y en la segunda no. Se demuestra primero que el caso de GCMP con transferencia se puede resolver en tiempo polinomial, usando para esto la soluci\'on de knapsack fraccional. Mostramos luego que GCMP sin transferencia es \emph{NP-completo}, probando para esto que existe una reducc\'on del problema $3-$Partici\'on al problema de decisión asociado a GCMP sin transferencia. Lo anterior nos lleva a demostrar como resultado principal de este trabajo que GCMP sin transferencia admite un PTAS, lo cual se realiza en tres etapas: se ve el caso de GCMP sin transferencia solo trabajos cortos; solo trabajos largos; y de largos arbitrario.