Programación de talentos

Un ejemplo de programación de talentos con 8 actores y 8 escenas

La programación de talentos es un problema de optimización en informática e investigación de operaciones , y también es un problema de optimización combinatoria . Supongamos que necesitamos hacer películas, y cada película contiene varias escenas. Cada escena debe ser filmada por uno o más actores. Y supongamos que solo puede filmar una escena al día. Los salarios de estos actores se calculan por día. En este problema, solo podemos contratar a cada actor consecutivamente. Por ejemplo, no podemos contratar a un actor el primer y tercer día, pero no el segundo día. Durante el período de contratación, los productores aún deben pagar a los actores incluso si no están involucrados en la tarea de filmación. El propósito de la programación de talentos es minimizar el salario total de los actores ajustando la secuencia de escenas. ^[1]

Formulación matemática

Consideremos un rodaje de película compuesto por días de rodaje y en el que participan un total de actores. Luego, utilizamos la matriz de días fuera de días (DODM) para representar los requisitos para los distintos días de rodaje. La matriz con la entrada dada por: ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle T^{0}\in \{0,1\}_{m\times n}}$ ${\displaystyle (i,j)}$

${\displaystyle t_{m\times n}^{0}={\begin{cases}1,&{\mbox{if actor i is required in scene j,}}\\0,&{\mbox{otherwise.}}\end{cases}}}$

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

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

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

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

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

${\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]

Prueba de dureza NP fuerte

En el problema de programación de talentos, podemos demostrar que es NP-hard mediante una reducción del problema de arreglo lineal óptimo (OLA). ^[2] Y en este problema, incluso si restringimos que cada actor sea necesario solo por dos días y que los salarios de todos los actores sean 1, sigue siendo polinomialmente reducible al problema OLA. Por lo tanto, es poco probable que este problema tenga un algoritmo pseudopolinomial . ^[3]

Programación de enteros

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

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

${\displaystyle x_{j,k}={\begin{cases}1&{\text{if scene }}j{\text{ is scheduled in day }}k{\text{ of shooting }}\\0&{\text{otherwise}}\end{cases}}}$

Referencias

1. Cheng, TCE; Diamond, JE; Lin, BMT (1 de diciembre de 1993). "Programación óptima en la producción cinematográfica para minimizar el costo de retención de talento". Journal of Optimization Theory and Applications . 79 (3): 479–492. doi :10.1007/BF00940554. S2CID  120319128 . Consultado el 25 de julio de 2022 .
2. Garey, MR; Johnson, DS; Stockmeyer, L. (1 de febrero de 1976). "Algunos problemas simplificados de grafos NP-completos". Ciencias de la Computación Teórica . 1 (3): 237–267. doi : 10.1016/0304-3975(76)90059-1 . ISSN  0304-3975.
3. Garey, M. R. ; Johnson, D. S. (1979). Victor Klee (ed.). Computadoras e intratabilidad: una guía para la teoría de la NP-completitud . Una serie de libros sobre las ciencias matemáticas. San Francisco, California: W. H. Freeman and Co. pp. x+338. ISBN 0-7167-1045-5.Sr. 0519066  .
4. Cerrar Kochetov, Y. (2011). Métodos iterativos de búsqueda local para el problema de programación de talentos. En Actas del 1.er simposio internacional y 10.ª conferencia balcánica sobre investigación operativa, 22 de septiembre, Tesalónica, Grecia (pp. 282–288).