人才排程

人才排程實例，該問題共有8個演員和8個場景

人才排程（英語：Talent scheduling）是電腦科學和作業研究領域的最佳化問題，亦是組合最佳化問題。在這一問題中，劇組需要完成電影的拍攝任務，其中分為若干個場景，而每個場景需要一個或多個特定的演員。現假定劇組每天只能完成一個場景的拍攝任務，而演員的薪資則按天計算。而在這一問題中，劇組需要連續性的聘請演員，例如某位演員需要參加第一天和第三天的演出活動，該劇組必須在第一天至第三天連續僱傭這位演員三天並支付其三天工資，即使這位演員第二天處於閒置狀態。該問題的最終目的是通過調整場景的拍攝順序，使得劇組的演員薪資支出最小化。

數學表達式

當問題中有$n$個場景與$m$個演員，現使用演員拍攝日程矩陣（day out of days matrix，DODM）$T^{0}\in \{0,1\}_{m\times n}$表示某位演員是否需要參加某個場景的演出任務：

$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}$，其元素$c_{i}$表示演員$i$的日薪資。此外對於場景的排列順序，定義：

$\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}$ for $i\in \{1,2,...,n\},j\in \{1,2,...,n\}$

接下來用$l_{i}(\sigma )$以及$e_{i}(\sigma )$表示演員$i$在$\sigma$的排序下需要出演的最後一天與第一天。因此，演員$i$需要被僱傭的閒置天數為：

$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 )$為該問題需要最小化的值，不過考慮到$\sum _{j=1}^{n}t_{i,j}^{0}$為定值，因此可以在最佳化時忽略此項。

強NP困難證明

該問題的難度可通過將其簡化為最大線性排列問題來證明。在該問題中，當所有演員的薪資皆為1時，此問題可以被簡化為最大線性排列問題，因此這一問題不大可能有偽多項式時間演算法。

整數規劃

人才排程問題有如下整數規劃形式：

Minimize	$\sum _{i=1}^{m}c_{i}(l_{i}-e_{i}+1)$
subject to	$\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}$與$l_{i}$分別表示演員$i$需要參演的第一天和最後一天，而決策變數$x_{j,k}$則表示場景$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}}$