Планирование талантов

Пример планирования талантов с 8 актерами и 8 сценами.

Планирование талантов является проблемой оптимизации в информатике и исследовании операций , а также проблемой комбинаторной оптимизации . Предположим, нам нужно снимать фильмы, и каждый фильм содержит несколько сцен. Каждую сцену должен снимать один или несколько актеров. Предположим, вы можете снимать только одну сцену в день. Заработная плата этих актеров рассчитывается посуточно. В этой задаче мы можем нанимать каждого актера только последовательно. Например, мы не можем нанять актера в первый и третий дни, но не во второй день. В период найма продюсерам все равно придется платить актерам, даже если они не участвуют в съемках. Цель планирования талантов — минимизировать общую зарплату актеров за счет корректировки последовательности сцен.

Математическая формулировка

Рассмотрим съемку фильма, состоящего из $n$ съемочных дней и включающих в общей сложности $m$ актеры. Затем мы используем матрицу дней из дней (DODM). $T^{0}\in \{0,1\}_{m\times n}$ представлять требования к различным съемочным дням. Матрица с. $(i,j)$ запись предоставлена:

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

Затем мы определяем вектор оплаты ${\mathfrak {R}}^{m}$, с $i$th элемент, заданный $c_{i}$ что означает ставку заработной платы за день $i$й актер. Пусть v обозначает любую перестановку n столбцов таблицы $T^{0}$, у нас есть:

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

$\sigma _{n}$ — набор перестановок из n съемочных дней. Затем определите $T(\sigma )$ быть матрицей $T^{0}$ со столбцами, переставленными в соответствии с $\sigma$, у нас есть:

$t_{i,j}(\sigma )=t_{i,\sigma (j)}^{0}$ для $i\in \{1,2,...,n\},j\in \{1,2,...,n\}$

Затем мы используем $l_{i}(\sigma )$ и $e_{i}(\sigma )$ для обозначения обозначают соответственно самые ранние и последние дни в расписании $S$ определяется, который требует актера $i$. Итак, мы можем найти актера $i$ будет нанят для $l_{i}(\sigma )-e_{i}(\sigma )+1$ дни. Но в наши дни только $r_{i}=\sum _{j=1}^{n}t_{ij}^{0}$ дней на самом деле необходимы, что означает $h_{i}(S)$ дни не нужны, у нас есть:

$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}$

Общая стоимость ненужных дней составляет:

$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}]$

$K(\sigma )$ будет целевой функцией, которую мы должны минимизировать.

Доказательство высокой NP-твердости

В задаче планирования талантов мы можем доказать, что она является NP-сложной, путем сокращения задачи оптимального линейного расположения (OLA). И в этой задаче, даже если мы ограничим каждого актера двумя днями, а зарплаты всех актеров равны 1, это все равно полиномиально сводится к задаче OLA. Таким образом, данная задача вряд ли имеет псевдополиномиальный алгоритм .

Целочисленное программирование

Модель целочисленного программирования определяется следующим образом:

Свернуть	$\sum _{i=1}^{m}c_{i}(l_{i}-e_{i}+1)$
при условии	$\sum _{j=1}^{n}x_{j,k}=\sum _{k=1}^{n}x_{j,k}=1,$		$1\leq j,k\leq n$
	$t_{i,j}e_{i}\leq \sum _{k=1}^{n}t_{i,j}kx_{j,k}\leq l_{i},$		$1\leq i\leq m,1\leq j\leq n$
	$l_{i},e_{i}\geq 1,$		$1\leq i\leq m$
	$x_{j,k}\in \{0,1\},$		$1\leq j,k\leq n$
	$l_{i},e_{i}\in \mathbb {Z} ,$		$1\leq i\leq m$

В этой модели $e_{i}$ означает самый ранний съемочный день для таланта $i$, $l_{i}$ это последний съемочный день для талантов $i$, $x_{j,k}$ это планирование проекта, т.е.

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