人才调度（）是计算机科学和运筹学领域的优化问题，亦是组合优化问题。在这一问题中，剧组需要完成电影的拍摄任务，其中分為若干个场景，而每个场景需要一个或多个特定的演员。现假定剧组每天只能完成一个场景的拍摄任务，而演员的薪资则按天计算。而在这一问题中，剧组需要连续性的聘请演员，例如某位演员需要参加第一天和第三天的演出活动，该剧组必须在第一天至第三天连续雇佣这位演员三天并支付其三天工资，即使这位演员第二天处于闲置状态。该问题的最终目的是通过调整场景的拍摄顺序，使得剧组的演员薪资支出最小化。
数学表达式
当问题中有n个场景与m个演员，现使用演员拍摄日程矩阵（day out of days matrix，DODM）T^0 \in \{0,1\}_{m \times n}表示某位演员是否需要参加某个场景的演出任务：
:t^0_{m \times n} = \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的-{zh-cn:列; zh-tw:行;}-经过\sigma排列后的样子，其具体定义如下：
:t_{i,j}(\sigma)=t^0_{i,\sigma(j)} 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^0_{i,j}
鉴于此，剧组需要为演员闲置天数支付的总薪资为：
:K(\sigma)=\sum_{i=1}^{m}c_ih_i(\sigma)=\sum_{i=1}^{m}c_i[l_i(\sigma)-e_i(\sigma)+1-\sum_{j=1}^{n} t^0_{i,j}]
其中K(\sigma)为该问题需要最小化的值，不过考虑到\sum_{j=1}^{n} t^0_{i,j}为定值，因此可以在最佳化时忽略此项。在该问题中，当所有演员的薪资皆为1时，此问题可以被简化为最大线性排列问题，因此这一问题不大可能有伪多项式时间算法。
整数规划
人才调度问题有如下整数规划形式：
在此模型中，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}
参考文献
评论 (0)