人才调度

人才调度实例，该问题共有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}}$