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

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

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

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

Рассмотрим съемку фильма, состоящую из съемочных дней и включающую общее количество актеров. Затем мы используем матрицу «день из дней» (DODM) для представления требований для различных съемочных дней. Матрица с записью, заданной как: ${\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}}}$

Затем мы определяем вектор оплаты , с элементом th, заданным , который означает ставку оплаты за день для th-го актера. Пусть v обозначает любую перестановку n столбцов , мы имеем: ${\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}}$— это набор перестановок n дней съемки. Тогда определим, что это матрица со столбцами, переставленными в соответствии с , имеем: ${\displaystyle T(\sigma )}$ ${\displaystyle T^{0}}$ ${\displaystyle \sigma }$

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

Затем мы используем и для представления обозначают соответственно самые ранние и самые поздние дни в расписании, определяемом a, которые требуют актера . Таким образом, мы можем найти актера, который будет нанят на дни. Но в этих днях фактически требуются только дни, что означает, что дни не нужны, у нас есть: ${\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}}$

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

${\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 )}$будет целевой функцией, которую мы должны минимизировать. ^[1]

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

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

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

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

В этой модели означает самый ранний день съемок для таланта , - самый поздний день съемок для таланта , - это график проекта, т.е. ${\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}}}$

Ссылки

1. Cheng, TCE; Diamond, JE; Lin, BMT (1 декабря 1993 г.). «Оптимальное планирование в кинопроизводстве для минимизации затрат на удержание талантов». Журнал теории оптимизации и приложений . 79 (3): 479–492. doi :10.1007/BF00940554. S2CID  120319128. Получено 25 июля 2022 г.
2. Garey, MR; Johnson, DS; Stockmeyer, L. (1 февраля 1976 г.). «Некоторые упрощенные NP-полные задачи на графах». Теоретическая информатика . 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 (ред.). Computers and Intractability: A Guide to the Theory of NP-Completeness . Серия книг по математическим наукам. Сан-Франциско, Калифорния: W. H. Freeman and Co. стр. x+338. ISBN 0-7167-1045-5. МР  0519066.
4. Закрыть Кочетов, Ю. (2011). Итеративные методы локального поиска для задачи планирования талантов. В трудах 1-го международного симпозиума и 10-й Балканской конференции по операционным исследованиям, 22 сентября, Салоники, Греция (стр. 282–288).