Programación de talentos

La planificación de talentos representa un desafío de optimización complejo dentro de los campos de la informática y la investigación operativa , específicamente categorizado dentro de la optimización combinatoria . Consideremos, por ejemplo, un caso que involucra la producción de múltiples películas, cada una con varias escenas que requieren la participación de uno o más actores. Es importante destacar que solo se puede filmar una escena por día, y la remuneración de los actores se calcula diariamente. Una restricción crítica en este problema es que los actores deben ser contratados para días consecutivos; por ejemplo, un actor no puede ser contratado para filmar el primer y tercer día sin ser contratado también para el segundo día intermedio. Además, durante todo el período de contratación, los productores están obligados a compensar a los actores, incluso en los días en que no participan activamente en la filmación. El objetivo principal de la planificación de talentos es minimizar el gasto total en salarios para los actores optimizando la secuencia en la que se filman las escenas. ^{[ 1 ]}

Consideremos un rodaje cinematográfico compuesto por${\displaystyle n}$días de rodaje y que involucran un total de${\displaystyle m}$actores. Luego usamos la matriz de días fuera de los días (DODM).${\displaystyle T^{0}\in \{0,1\}_{m\times n}}$para representar los requisitos para los distintos días de rodaje. La matriz con el${\displaystyle (i,j)}$Entrada proporcionada por:

${\displaystyle t_{m\times n}^{0}={\begin{cases}1,&{\mbox{si el actor i es requerido en la escena j,}}\\0,&{\mbox{en otro caso.}}\end{cases}}}$

Luego definimos el vector de pago${\displaystyle {\mathfrak {R}}^{m}}$, con el${\displaystyle i}$-ésimo elemento dado por${\displaystyle c_{i}}$lo que significa tasa de pago por día de la${\displaystyle i}$actor. Sea v cualquier permutación de las n columnas de${\displaystyle T^{0}}$, tenemos:

${\displaystyle \sigma$ :\{1,2,...,n\}\rightarrow \{1,2,...,n\}}

${\displaystyle \sigma _{n}}$es el conjunto de permutaciones de los n días de rodaje. Entonces definimos${\displaystyle T(\sigma )}$ser la matriz${\displaystyle T^{0}}$con sus columnas permutadas según${\displaystyle \sigma }$, tenemos:

${\displaystyle t_{i,j}(\sigma )=t_{i,\sigma (j)}^{0}}$para${\displaystyle i\in \{1,2,...,n\},j\in \{1,2,...,n\}}$

Luego usamos${\displaystyle l_{i}(\sigma )}$y${\displaystyle e_{i}(\sigma )}$para representar y denotar respectivamente los días más tempranos y más tardíos en el cronograma${\displaystyle S}$determinado por un que requiere actor${\displaystyle i}$Así que podemos encontrar al actor.${\displaystyle i}$será contratado para${\displaystyle l_{i}(\sigma )-e_{i}(\sigma )+1}$días. Pero en estos días, solo${\displaystyle r_{i}=\sum _{j=1}^{n}t_{ij}^{0}}$En realidad se requieren días, lo que significa${\displaystyle h_{i}(S)}$Los días son innecesarios, tenemos:

${\displaystyle h_{i}(S)=h_{i}(\sigma )=l_{i}(\sigma )-e_{i}(\sigma )+1-r_{i}=l_{i}(\sigma )-e_{i}(\sigma )+1-\sum _{j=1}^{n}t_{i,j}^{0}}$

El coste total de los días innecesarios es:

${\displaystyle K(\sigma )=\sum _{i=1}^{m}c_{i}h_{i}(\sigma )=\sum _{i=1}^{m}c_{i}[l_{i}(\sigma )-e_{i}(\sigma )+1-\sum _{j=1}^{n}t_{i,j}^{0}]}$

${\displaystyle K(\sigma )}$será la función objetivo que debemos minimizar. ^{[ 1 ]}

Se puede demostrar que el problema de programación de talentos es NP-difícil mediante una reducción al problema de arreglo lineal óptimo (OLA). ^{[ 2 ]} Incluso si restringimos el problema exigiendo que cada actor sea necesario solo por dos días y que todos los salarios de los actores sean 1, sigue siendo polinomialmente reducible al problema OLA. Por lo tanto, es improbable que este problema tenga un algoritmo pseudopolinomial . ^{[ 3 ]}

El modelo de programación entera viene dado por: ^{[ 4 ]}

En este modelo,${\displaystyle e_{i}}$significa el día de rodaje más temprano para el talento${\displaystyle i}$,${\displaystyle l_{i}}$es el último día de rodaje para el talento${\displaystyle i}$,${\displaystyle x_{j,k}}$es la programación del proyecto, es decir

${\displaystyle x_{j,k}={\begin{cases}1&{\text{si la escena }}j{\text{ está programada para el día }}k{\text{ del rodaje }}\\0&{\text{en otro caso}}\end{cases}}}$