1  El orden de los trabajos

Lo primero que habría que observar es que la noción de obra impone una restricción de orden sobre los trabajos; es decir, según los grafos dirigidos acíclicos de cada obra, un trabajo no puede efectuarse hasta que no se hayan efectuado los precedentes en el grafo dirigido acíclico de su obra.

La manera de considerar el orden de los trabajos es obtener el ordenamientos topológicos por rangos. Así, por ejemplo, una obra O_i se dividiría en O_i = R₁, R₂, …, R_m = {T₁, T2,}, {T₃,T₄,T₅}, …, {T₁₁, T₁₂}. Esto quiere decir que para poder hacer un trabajo que pertenezca al rango R_i antes hay que haber hecho todos trabajos que pertenezcan a los rangos previos …, R_i−2, R_i−1.

2  Las demandas de instrumentos de los trabajos

Cada trabajo requiere instrumentos. En este caso requerir es una demanda. Por consiguiente, en un modelo de red de flujo, los trabajos serían demandantes de instrumentos. Así, por ejemplo, dos trabajos T₁ y T₂ podrían especificarse como:

Los arcos de instrumentos hacia trabajos son exactamente las relaciones instrumentos/trabajo, pero invertidas porque los trabajos fungen de demandantes de instrumentos. Los costes son cero, pues el coste lo da el ofertante (la empresa).

Cada trabajo se conecta a un suprasumidero con capacidad infinita y coste cero.

3  Las ofertas de instrumentos

Las empresas (como en la inmensa mayoría de circunstancias de la vida real), cumplen un rol de ofertantes; es nuestro caso de alquiler de instrumentos.

Puesto que lo que se oferta son instrumentos y son ellos “el fluido”, los nodos ofertantes deben relacionar instrumentos. Así, por cada instrumento de cada empresa, se crean nodos ofertantes de la siguiente manera:

Cada nodo indica el instrumento I_i perteneciente a la empresa E_j. Cada nodo se conecta a un suprafuente cuya capacidad es la cantidad de instrumentos que posea la empresa y el coste se corresponde con el coste de alquiler.

Modelo final y proceso de asignación

Red global

A partir de la unión global de los rangos topológicos R₁ calculados según 1 de cada trabajo se crea una red de flujo cuyos nodos demandantes son los trabajos que deben realizarse de primero (que preceden a otros en las obras). La estructura de los trabajos demandantes se corresponde con lo explicado en 2.

Las ofertas de instrumentos expresada por la red de ofertantes explicada en 3 se conecta con las demandas según los requerimientos de instrumentos del trabajo y con capacidad infinita a coste cero. Por ejemplo:

Una mejora que redunda en eficiencia es sustituir las conexiones de los nodos ofertantes con los nodos instrumentos por un solo arco. Pero esto es irrelevante a efectos del modelo.

Algoritmo de asignación

El algoritmo general de asignación sería:

1. Calcular los rangos topológicos para todas las obras. Luego calcular la unión R_i^′ = R_1,1 ∪ R_1,2∪ …∪ R_l,N. Cada elemento R_i,j representa el rango i de la obra j. Así cada R_i^′ es el conjunto total de trabajos del rango topológico i para todas las obras.
2. Sea R₀^′ = ∅.
3. ∀ R_k^′, k=1,2,…,n (n es el máximo rango)
   1. Construya una red global como en 3 con todos los trabajos de R_k^′.

   2. Maximice el flujo de red a coste mínimo.

      Del resultado anterior, se eliminan los trabajos para los cuales todos los arcos de entrada I_i—→ T_j están saturados. Esto indica que el trabajo obtuvo toda la asignación y puede ser hecho. Al eliminar un trabajo de este tipo se eliminan sus arcos.

      Por cada arco de entrada I_i—→ T_j se busca una asignación de instrumento/empresa mirando los arcos de entrada de su nodo I_i I_i/E_j—→ I_I con flujo distinto de cero. En caso de que hayan varias empresas, es indistinto los que se escojan, pero en todo caso, se deben eliminar los arcos I_i I_i/E_j—→ I_I que se hayan asignado.

      Si sobran trabajos, lo idóneo es cotejarlos con sus obras para intentar meterlos en el siguiente rango R_k+1^′; si no es posible, entonces la red resultante se vuelve a maximizar.

Comentario final

En mi opinión, el problema es bastante sencillo si se tiene experiencia en el modelado de asignaciones mediante flujo máximo a coste mínimo. En lo particular de este curso, si se estudió bien la sección 7.12.4 del libro creo que el problema es sencillo.

La parte más dificultosa es respetar el orden de los trabajos e identificar el vínculo del problema con el ordenamiento topológico. La técnica explicada aquí se presenta en la sección 7.12.4.1 página 516 del libro.

This document was translated from L^AT_EX by H^EV^EA.