Problema de gestión de proyectos con recursos limitados

El problema de la gestión de proyectos con recursos limitados es un problema de optimización combinatoria, estudiado en la programación . Es conocido por el acrónimo inglés RCPSP (Problema de programación de proyectos con restricciones de recursos).

El problema es NP-hard en el sentido más fuerte, por lo que solo puede resolverse de manera óptima mediante algoritmos de complejidad exponencial. El estado de la técnica permite resolverlo de manera óptima en un tiempo razonable, en instancias de 60 tareas como máximo.

Descripción

Conceptos

Los recursos son medios de producción renovables, pero de capacidad limitada. Un equipo de cuatro trabajadores con las mismas habilidades puede considerarse un recurso de habilidad 4.

Las tareas se definen por la duración del trabajo y la cantidad de cada recurso que es necesario para su implementación. Se supone que las tareas no son interrumpibles: una vez que ha comenzado la ejecución, continúan sin interrupciones hasta su finalización. Un bien manufacturado puede tardar dos horas en fabricarse y requiere el trabajo de dos trabajadores y una máquina.

Existen relaciones de precedencia entre las tareas , lo que significa clásicamente que una tarea solo puede comenzar si algunas otras tareas se terminan. Estas relaciones permiten representar la organización del proyecto mediante un gráfico de precedencia (o red PERT ): una tarea está representada por un nodo, cada relación de precedencia es un arco orientado desde el predecesor al sucesor, que se valora por la duración del predecesor. Un gráfico de precedencia no debe presentar un circuito, una tarea no puede, directa o indirectamente, ser su propio predecesor.

Clásicamente, el problema consiste en minimizar la fecha de finalización del proyecto, dadas las limitaciones de precedencia y recursos.

Formalización

Sea n tareas yq recursos.

Se anotan los recursos y se anotan sus capacidades . $R_ {k}$ $B_k$

Las tareas están designadas por y sus duraciones son , una tarea i requiere una cantidad del recurso k . Generalmente se agregan dos tareas ficticias, tienen una duración cero y no consumen recursos: es el predecesor de las otras tareas ( vértice fuente del gráfico), es el sucesor de todas las tareas ( vértice sumidero del gráfico de precedencia). Las precedencias son declaradas por un conjunto . $Tengo}$ $Pi}$ ${\ Displaystyle b_ {ik}}$ $A_0$ ${\ Displaystyle A_ {n + 1}}$ ${\ Displaystyle E = \ {(i, j) / A_ {i} \ rightarrow A_ {j} \}}$

Una solución S al problema es un vector que contiene las fechas de inicio de cada una de las tareas. ${\ Displaystyle R_ {n + 2}}$

Hay dos tipos de restricciones:

las restricciones de precedencia: ya sea tareas y como ( precede ), no puede comenzar antes del final de , $Tengo}$ $A_ {j}$ ${\ Displaystyle (A_ {i}, A_ {j}) \ in E}$ $Tengo}$ $A_ {j}$ $A_ {j}$ $Tengo}$ ${\ Displaystyle S_ {j} \ geq S_ {i} + p_ {i}}$
Restricciones de recursos: en cualquier momento y para cada recurso , la suma de solicitudes de tareas en curso no excede $k$ $B_k$

Métodos de resolución

Se utilizaron varias herramientas para resolver el problema:

Lista de algoritmos

Los primeros métodos, creados en la década de 1960, son heurísticas basadas en listas. Las listas de prioridades definen una priorización en la ejecución de tareas, de acuerdo con criterios a menudo heurísticos como el tiempo de procesamiento de la tarea o el margen. Una lista de prioridades debe respetar las restricciones de precedencia.

El algoritmo de orden estricto consiste en colocar las tareas una a una, lo antes posible, en el orden exacto de la lista de prioridades.

t\leftarrow 0

Tant que la liste de priorité est non vide soit la tâche

i

que l'on retire au début de la liste de priorité

r_{i}=max(t,max_{j\in Pred(i)}(t_{j}+p_{j}))

la date à laquelle on peut ordonnancer

i

au plus tôt (

p_{j}

est la durée de la tâche j) soit

t_{i}\geq r_{i}

, la première date à laquelle les ressources sont disponibles pour l'exécution placer la tâche à la date

t_i

t\leftarrow t_{i}

Fin Tant Que

Determinación de un límite inferior

Dada la complejidad del problema, a menudo es ilusorio querer determinar soluciones exactas al problema. En la investigación operativa, para evaluar concretamente un método de resolución, la calidad de una solución se evalúa comparando la fecha de finalización obtenida con un límite inferior . El límite inferior es un valor que sabemos que es más bajo que la fecha de finalización de la solución óptima, pero debemos obtener un valor lo suficientemente alto como para acercarnos al valor óptimo. La calidad de una solución se mide en porcentaje de diferencia con el límite inferior: . ${\ Displaystyle C_ {max}}$ ${\ displaystyle LB}$ ${\ Displaystyle {\ frac {C_ {max} -LB} {LB}}}$

Método del camino crítico

Ruta crítica mejorada

Razonamiento enérgico

Extensiones

El modelo básico de RCPSP se ha adaptado a muchas aplicaciones industriales, de ahí la aparición de variantes del problema.

Gestión de proyectos de habilidades múltiples

Esta variante es adecuada para la planificación de proyectos en empresas de servicios, en particular empresas de servicios de TI . Definimos un conjunto de habilidades, los recursos representan a las personas que participan en el proyecto, la capacidad de cada recurso es 1. Una tarea ya no se define por las cantidades requeridas de cada recurso, sino por el número de personas que tienen tales habilidades. Por ejemplo, una tarea de "Pruebas unitarias" puede requerir dos personas con la habilidad de "Desarrollador" y una persona con la habilidad de "Analista".

Tareas multimodo

La misma tarea se puede realizar de diferentes formas o modos . Cada modo define su propia duración y demandas de recursos. Parte del problema es elegir un modo para realizar una tarea.

Programación robusta

Se han desarrollado enfoques de programación sólidos para RCPSP. Los modelos robustos en la gestión de proyectos consideran cuatro tipos de perturbaciones:

alteraciones del gráfico del proyecto: se añaden o eliminan tareas (o enlaces de precedencia)
interrupciones en las tareas: modificaciones de duraciones, solicitudes
interrupciones en los recursos: los recursos dejan de estar disponibles (averías, ausencias) o su capacidad está temporalmente limitada
cambios de tiempo

Ver también

Fuentes y referencias

Problema de gestión de proyectos con limitaciones de recursos - enfoques y métodos de resolución GOThA - grupo "Gestión de proyectos con limitaciones de recursos y sus extensiones"

Gang Yu, Xiangtong Qi Disruption management: framework, models and applications , 2004