人才调度

人才调度（）是计算机科学和运筹学领域的优化问题，亦是组合优化问题。在这一问题中，剧组需要完成电影的拍摄任务，其中分為若干个场景，而每个场景需要一个或多个特定的演员。现假定剧组每天只能完成一个场景的拍摄任务，而演员的薪资则按天计算。而在这一问题中，剧组需要连续性的聘请演员，例如某位演员需要参加第一天和第三天的演出活动，该剧组必须在第一天至第三天连续雇佣这位演员三天并支付其三天工资，即使这位演员第二天处于闲置状态。该问题的最终目的是通过调整场景的拍摄顺序，使得剧组的演员薪资支出最小化。
 数学表达式 
当问题中有个场景与个演员，现使用演员拍摄日程矩阵（day out of days matrix，DODM）表示某位演员是否需要参加某个场景的演出任务：

此外还存在薪资向量，其元素表示演员的日薪资。此外对于场景的排列顺序，定义：

其中是个拍摄日的排列集合。接下来定义矩阵为矩阵的-{zh-cn:列; zh-tw:行;}-经过排列后的样子，其具体定义如下：
 for 

接下来用以及表示演员在的排序下需要出演的最后一天与第一天。因此，演员需要被雇佣的闲置天数为：

鉴于此，剧组需要为演员闲置天数支付的总薪资为：

其中为该问题需要最小化的值，不过考虑到为定值，因此可以在最佳化时忽略此项。

 强NP困难证明 
该问题的难度可通过将其简化为最大线性排列问题来证明。在该问题中，当所有演员的薪资皆为1时，此问题可以被简化为最大线性排列问题，因此这一问题不大可能有伪多项式时间算法。
 整数规划 
人才调度问题有如下整数规划形式：Close
Kochetov, Y. (2011). Iterative local search methods for the talent scheduling problem. In Proceedings of 1st international symposium and 10th Balkan conference on operational research, September 22, Thessaloniki, Greece (pp. 282–288).
 Minimize subject to

在此模型中，与分别表示演员需要参演的第一天和最后一天，而决策变量则表示场景是否被安排到了第天：

参考文献

Category:最佳排程