MÁQUINAS EN PARALELO NO RELACIONADAS
Este problema consta de un conjunto de máquinas que deben de ejecutar un conjunto de trabajos. Cada trabajo requiere de una sola operación para ser terminado. Cada máquina puede realizar cualquier trabajo, pero el tiempo de procesamiento de cada trabajo depende de la máquina que lo realice.
El modelo Pm | | S Cj, es un modelo de tipo NP-completo. Este problema se puede formular como un problema de programación lineal entera (PLI) con una estructura especial la cual hace que el problema se pueda resolver con un algoritmo en tiempo polinomial. La contribución a la función objetivo de este problema de cada trabajo j a realizarse, depende de la máquina i donde se realice el trabajo j y también de la posición k en la que se ejecute el trabajo en la máquina i dentro del conjunto ordenado de trabajos a ejecutar por la máquina i. De acuerdo a esto último el trabajo j contribuye kpij al valor de la función objetivo. El problema de programación lineal entera se formula como sigue.
En este modelo, las restricciones en (4), indican que las variables x toman solamente valores de 0 ó 1. Si xikj = 1, entonces el trabajo j se asigna a la máquina i en la k-ésima posición. Si xikj = 0 es lo contrario. Las restricciones en (2), aseguran que cada trabajo se asigna solamente a una posición k. Las restricciones en (3), aseguran que cada posición k sobre cada máquina i se toma a lo más por un trabajo j. Este modelo se puede mapear al problema de transporte si el conjunto de restricciones en (4) se reemplaza por un conjunto de restricciones de no negatividad, esto es, xikj >= 0. Esto es importante porque con este modelo relajado se pueden obtener cotas con algoritmos exactos para problemas NP-completos, como lo es el Pm | | S Cj. En el caso del modelo con la estructura presentada, la formulación relajada en programación lineal continua (PL) da como resultado en las variables x, sólo valores de 1 ó 0.
Un caso especial del problema de transporte es el problema del conjunto independiente de arcos en un grafo bipartido ponderado ó WBMP (por sus siglas en inglés, Weighted Bipartite Matching Problem). Entonces, el modelo Pm | | S Cj para la estructura definida en PLI, también se puede representar como un WBMP. La figura 1, presenta una instancia de 3 trabajos y 2 máquinas del problema de máquinas en paralelo no relacionadas mediante un grafo bipartido. El grafo se compone por un lado de los n trabajos y por el otro lado de las mn posiciones donde cada máquina puede procesar a lo más n trabajos. El trabajo j que se asigna a la posición ik, presenta un costo kpij. El objetivo es determinar la asignación ik para cada j en el grafo bipartido con un costo de tiempo total mínimo.
Figura 1. Instancia del problema Pm | | S Cj con 3 trabajos y 2 máquinas, representada con un grafo bipartita
La formulación del modelo Pm | | S Cj con esta estructura especial del problema del transporte, hace que el problema Pm | | S Cj sea un problema de tipo P y por lo mismo, se pueda resolver bajo la estructura de este modelo de PL mediante un algoritmo determinístico de tiempo polinomial, como por ejemplo utilizando métodos de punto interior. La solución del modelo de PL dará como resultado en las variables xikj, únicamente valores de 0 y 1. Otro camino para resolver este tipo de modelo de forma más simple o para encontrar un UB en instancias de problemas grandes, es utilizar algoritmos no determinísticos de tiempo polinomial, como lo son Recocido Simulado, Algorítmos Genéticos, Colonia de Hormigas y otras meta heurísticas.
