人才排程 (英語:Talent scheduling )是電腦科學 和作業研究 領域的最佳化問題,亦是組合最佳化 問題。在這一問題中,劇組需要完成電影的拍攝任務,其中分為若干個場景,而每個場景需要一個或多個特定的演員。現假定劇組每天只能完成一個場景的拍攝任務,而演員的薪資則按天計算。而在這一問題中,劇組需要連續性的聘請演員,例如某位演員需要參加第一天和第三天的演出活動,該劇組必須在第一天至第三天連續僱傭這位演員三天並支付其三天工資,即使這位演員第二天處於閒置狀態。該問題的最終目的是通過調整場景的拍攝順序,使得劇組的演員薪資支出最小化。[ 1]
人才排程實例,該問題共有8個演員和8個場景
當問題中有
n
{\displaystyle n}
個場景與
m
{\displaystyle m}
個演員,現使用演員拍攝日程矩陣(day out of days matrix,DODM)
T
0
∈
{
0
,
1
}
m
×
n
{\displaystyle T^{0}\in \{0,1\}_{m\times n}}
表示某位演員是否需要參加某個場景的演出任務:
t
m
×
n
0
=
{
1
,
if actor i is required in scene j,
0
,
otherwise.
{\displaystyle t_{m\times n}^{0}={\begin{cases}1,&{\mbox{if actor i is required in scene j,}}\\0,&{\mbox{otherwise.}}\end{cases}}}
此外還存在薪資向量
R
m
{\displaystyle {\mathfrak {R}}^{m}}
,其元素
c
i
{\displaystyle c_{i}}
表示演員
i
{\displaystyle i}
的日薪資。此外對於場景的排列順序,定義:
σ
:
{
1
,
2
,
.
.
.
,
n
}
→
{
1
,
2
,
.
.
.
,
n
}
{\displaystyle \sigma :\{1,2,...,n\}\rightarrow \{1,2,...,n\}}
其中
σ
n
{\displaystyle \sigma _{n}}
是
n
{\displaystyle n}
個拍攝日的排列集合。接下來定義矩陣
T
(
σ
)
{\displaystyle T(\sigma )}
為矩陣
T
0
{\displaystyle T^{0}}
的行經過
σ
{\displaystyle \sigma }
排列後的樣子,其具體定義如下:
t
i
,
j
(
σ
)
=
t
i
,
σ
(
j
)
0
{\displaystyle t_{i,j}(\sigma )=t_{i,\sigma (j)}^{0}}
for
i
∈
{
1
,
2
,
.
.
.
,
n
}
,
j
∈
{
1
,
2
,
.
.
.
,
n
}
{\displaystyle i\in \{1,2,...,n\},j\in \{1,2,...,n\}}
接下來用
l
i
(
σ
)
{\displaystyle l_{i}(\sigma )}
以及
e
i
(
σ
)
{\displaystyle e_{i}(\sigma )}
表示演員
i
{\displaystyle i}
在
σ
{\displaystyle \sigma }
的排序下需要出演的最後一天與第一天。因此,演員
i
{\displaystyle i}
需要被僱傭的閒置天數為:
h
i
(
σ
)
=
l
i
(
σ
)
−
e
i
(
σ
)
+
1
−
r
i
=
l
i
(
σ
)
−
e
i
(
σ
)
+
1
−
∑
j
=
1
n
t
i
,
j
0
{\displaystyle 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
(
σ
)
=
∑
i
=
1
m
c
i
h
i
(
σ
)
=
∑
i
=
1
m
c
i
[
l
i
(
σ
)
−
e
i
(
σ
)
+
1
−
∑
j
=
1
n
t
i
,
j
0
]
{\displaystyle 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
(
σ
)
{\displaystyle K(\sigma )}
為該問題需要最小化的值,不過考慮到
∑
j
=
1
n
t
i
,
j
0
{\displaystyle \sum _{j=1}^{n}t_{i,j}^{0}}
為定值,因此可以在最佳化時忽略此項。[ 1]
該問題的難度可通過將其簡化為最大線性排列問題來證明。[ 2] 在該問題中,當所有演員的薪資皆為1時,此問題可以被簡化為最大線性排列問題,因此這一問題不大可能有偽多項式時間 演算法。[ 3]
人才排程問題有如下整數規劃形式:[ 4]
Minimize
∑
i
=
1
m
c
i
(
l
i
−
e
i
+
1
)
{\displaystyle \sum _{i=1}^{m}c_{i}(l_{i}-e_{i}+1)}
subject to
∑
j
=
1
n
x
j
,
k
=
∑
k
=
1
n
x
j
,
k
=
1
,
{\displaystyle \sum _{j=1}^{n}x_{j,k}=\sum _{k=1}^{n}x_{j,k}=1,}
1
≤
j
,
k
≤
n
{\displaystyle 1\leq j,k\leq n}
t
i
,
j
e
i
≤
∑
k
=
1
n
t
i
,
j
k
x
j
,
k
≤
l
i
,
{\displaystyle t_{i,j}e_{i}\leq \sum _{k=1}^{n}t_{i,j}kx_{j,k}\leq l_{i},}
1
≤
i
≤
m
,
1
≤
j
≤
n
{\displaystyle 1\leq i\leq m,1\leq j\leq n}
l
i
,
e
i
≥
1
,
{\displaystyle l_{i},e_{i}\geq 1,}
1
≤
i
≤
m
{\displaystyle 1\leq i\leq m}
x
j
,
k
∈
{
0
,
1
}
,
{\displaystyle x_{j,k}\in \{0,1\},}
1
≤
j
,
k
≤
n
{\displaystyle 1\leq j,k\leq n}
l
i
,
e
i
∈
Z
,
{\displaystyle l_{i},e_{i}\in \mathbb {Z} ,}
1
≤
i
≤
m
{\displaystyle 1\leq i\leq m}
在此模型中,
e
i
{\displaystyle e_{i}}
與
l
i
{\displaystyle l_{i}}
分別表示演員
i
{\displaystyle i}
需要參演的第一天和最後一天,而決策變數
x
j
,
k
{\displaystyle x_{j,k}}
則表示場景
j
{\displaystyle j}
是否被安排到了第
k
{\displaystyle k}
天:
x
j
,
k
=
{
1
if scene
j
is scheduled in day
k
of shooting
0
otherwise
{\displaystyle x_{j,k}={\begin{cases}1&{\text{if scene }}j{\text{ is scheduled in day }}k{\text{ of shooting }}\\0&{\text{otherwise}}\end{cases}}}
^ 1.0 1.1 Cheng, T. C. E.; Diamond, J. E.; Lin, B. M. T. Optimal scheduling in film production to minimize talent hold cost . Journal of Optimization Theory and Applications. 1993-12-01, 79 (3): 479–492 [2022-07-25 ] . S2CID 120319128 . doi:10.1007/BF00940554 . (原始內容存檔 於2023-02-24) (英語) .
^ Garey, M. R.; Johnson, D. S.; Stockmeyer, L. Some simplified NP-complete graph problems. Theoretical Computer Science. 1976-02-01, 1 (3): 237–267. ISSN 0304-3975 . doi:10.1016/0304-3975(76)90059-1 (英語) .
^ Garey, M. R. ; Johnson, D. S. Victor Klee , 編. Computers and Intractability: A Guide to the Theory of NP-Completeness. A Series of Books in the Mathematical Sciences. San Francisco, Calif.: W. H. Freeman and Co. 1979: x+338 . ISBN 0-7167-1045-5 . MR 0519066 .
^ 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).