查看“︁人才调度”︁的源代码

{{NoteTA
|G1 = Math
|G2 = Physics
|G3 = IT
}}
[[File:A example of talent scheduling.png|thumb|人才调度实例，该问题共有8个演员和8个场景]]
'''人才调度'''（{{lang-en|Talent scheduling}}）是[[计算机科学]]和[[运筹学]]领域的优化问题，亦是[[组合优化]]问题。在这一问题中，剧组需要完成电影的拍摄任务，其中分為若干个场景，而每个场景需要一个或多个特定的演员。现假定剧组每天只能完成一个场景的拍摄任务，而演员的薪资则按天计算。而在这一问题中，剧组需要连续性的聘请演员，例如某位演员需要参加第一天和第三天的演出活动，该剧组必须在第一天至第三天连续雇佣这位演员三天并支付其三天工资，即使这位演员第二天处于闲置状态。该问题的最终目的是通过调整场景的拍摄顺序，使得剧组的演员薪资支出最小化。<ref name="J1993">{{cite journal |last1=Cheng |first1=T. C. E. |last2=Diamond |first2=J. E. |last3=Lin |first3=B. M. T. |title=Optimal scheduling in film production to minimize talent hold cost |url=https://link.springer.com/article/10.1007/BF00940554 |journal=Journal of Optimization Theory and Applications |access-date=2022-07-25 |pages=479–492 |language=en |doi=10.1007/BF00940554 |date=1993-12-01 |volume=79 |issue=3 |s2cid=120319128 |archive-date=2023-02-24 |archive-url=https://web.archive.org/web/20230224185731/https://link.springer.com/article/10.1007/bf00940554 |dead-url=no }}</ref>
== 数学表达式 ==
当问题中有<math>n</math>个场景与<math>m</math>个演员，现使用演员拍摄日程矩阵（day out of days matrix，DODM）<math>T^0 \in \{0,1\}_{m \times n}</math>表示某位演员是否需要参加某个场景的演出任务：
:<math>t^0_{m \times n} = \begin{cases}
  1, & \mbox{if actor i is required in scene j,}\\
  0,  & \mbox{otherwise.}
\end{cases}</math>

此外还存在薪资向量<math>\mathfrak{R}^m</math>，其元素<math>c_i</math>表示演员<math>i</math>的日薪资。此外对于场景的排列顺序，定义：
:<math>\sigma :\{1,2,...,n\} \rightarrow \{1,2,...,n\}</math>
其中<math>\sigma_n</math>是<math>n</math>个拍摄日的排列集合。接下来定义矩阵<math>T(\sigma)</math>为矩阵<math>T^0</math>的-{zh-cn:列; zh-tw:行;}-经过<math>\sigma</math>排列后的样子，其具体定义如下：
:<math>t_{i,j}(\sigma)=t^0_{i,\sigma(j)}</math> ''for'' <math>i \in \{1,2,...,n\},j \in \{1,2,...,n\}</math>

接下来用<math>l_i(\sigma)</math>以及<math>e_i(\sigma)</math>表示演员<math>i</math>在<math>\sigma</math>的排序下需要出演的最后一天与第一天。因此，演员<math>i</math>需要被雇佣的闲置天数为：
:<math>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}</math>

鉴于此，剧组需要为演员闲置天数支付的总薪资为：
:<math>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}]</math>
其中<math>K(\sigma)</math>为该问题需要最小化的值，不过考虑到<math>\sum_{j=1}^{n} t^0_{i,j}</math>为定值，因此可以在最佳化时忽略此项。<ref name="J1993" />

== 强NP困难证明 ==
该问题的难度可通过将其简化为最大线性排列问题来证明。<ref>{{cite journal |last1=Garey |first1=M. R. |last2=Johnson |first2=D. S. |last3=Stockmeyer |first3=L. |title=Some simplified NP-complete graph problems |journal=Theoretical Computer Science |date=1976-02-01 |volume=1 |issue=3 |pages=237–267 |doi=10.1016/0304-3975(76)90059-1 |language=en |issn=0304-3975|doi-access=free }}</ref>在该问题中，当所有演员的薪资皆为1时，此问题可以被简化为最大线性排列问题，因此这一问题不大可能有[[伪多项式时间]]算法。<ref>{{cite book|last1=Garey|first1=M.&nbsp;R.|author-link1=Michael R. Garey|last2=Johnson|first2=D.&nbsp;S.|author-link2=David S. Johnson|title=<!-- [[ -->Computers and Intractability: A Guide to the Theory of NP-Completeness<!-- ]] -->|year=1979|isbn=0-7167-1045-5|pages=[https://archive.org/details/computersintract0000gare/page/ x+338]|series=A Series of Books in the Mathematical Sciences|editor=Victor Klee|editor-link=Victor Klee|publisher=W.&nbsp;H.&nbsp;Freeman and Co.|location=San Francisco, Calif.|mr=519066}}</ref>
== 整数规划 ==
人才调度问题有如下整数规划形式：<ref>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).</ref>
{| cellspacing="10"
|-
| Minimize
| colspan="2" |<math>\sum_{i=1}^{m}c_i(l_i-e_i+1) </math>
|-
| subject to
|<math> \sum_{j=1}^n x_{j,k} = \sum_{k=1}^n x_{j,k}=1,</math>
|
|<math> 1 \leq j,k \leq n </math>
|-
|
|<math> t_{i,j}e_i \leq \sum_{k=1}^nt_{i,j}kx_{j,k} \leq l_i,</math>
|
|<math> 1 \leq i \leq m, 1 \leq j \leq n </math>
|-
|
|<math> l_i,e_i \geq 1,</math>
|
|<math> 1 \leq i \leq m </math>
|-
|
|<math> x_{j,k} \in \{0,1\},</math>
|
|<math> 1 \leq j,k \leq n </math>
|-
|
|<math> l_i,e_i \in \mathbb{Z},</math>
|
|<math> 1 \leq i \leq m </math>
|}

在此模型中，<math>e_i</math>与<math>l_i</math>分别表示演员<math>i</math>需要参演的第一天和最后一天，而决策变量<math>x_{j,k}</math>则表示场景<math>j</math>是否被安排到了第<math>k</math>天：
:<math> x_{j,k} = \begin{cases} 1 & \text{if scene } j \text{ is scheduled in day } k \text{ of shooting } \\ 0 & \text{otherwise} \end{cases}</math>

==参考文献==
{{reflist}}

[[Category:最佳排程]]