タレントのスケジュール管理

タレントスケジューリングは、コンピュータサイエンスとオペレーションズリサーチの分野における複雑な最適化課題であり、特に組み合わせ最適化に分類されます。たとえば、複数の映画を制作する場合を考えてみましょう。各映画は複数のシーンで構成され、1人以上の俳優の参加が必要です。重要なのは、1日に撮影できるシーンは1つだけであり、俳優への報酬は日割りで計算されるということです。この問題における重要な制約は、俳優は連続した日に雇用されなければならないということです。たとえば、俳優は、2日目にも雇用されない限り、1日目と3日目の撮影のために契約することはできません。さらに、雇用期間全体を通して、プロデューサーは、俳優が撮影に積極的に参加していない日であっても、俳優に報酬を支払う義務があります。タレントスケジューリングの主な目的は、シーンの撮影順序を最適化することによって、俳優への総給与支出を最小限に抑えることです。^{[ 1 ]}

映画撮影を考えてみましょう。${\displaystyle n}$撮影日数と合計${\displaystyle m}$俳優。次に、日数マトリックス（DODM）を使用します。${\displaystyle T^{0}\in \{0,1\}_{m\times n}}$さまざまな撮影日の要件を表すために。${\displaystyle (i,j)}$エントリー提供者：

${\displaystyle t_{m\times n}^{0}={\begin{cases}1,&{\mbox{シーン j でアクター i が必要な場合}}\\0,&{\mbox{それ以外の場合}}\end{cases}}}$

次に、報酬ベクトルを定義します。${\displaystyle {\mathfrak {R}}^{m}}$で${\displaystyle i}$番目の要素は、${\displaystyle c_{i}}$つまり、1日あたりの賃金率${\displaystyle i}$番目の俳優。v を、n 列の任意の順列とします。$\displaystyle T^{0}}$、 我々は持っています：

${\displaystyle \sigma$ :\{1,2,...,n\}\rightarrow \{1,2,...,n\}}

$\displaystyle \sigma _{n}}$は n 日間の撮影の順列集合です。次に、次のように定義します。${\displaystyle T(\sigma )}$マトリックスになる$\displaystyle T^{0}}$列が順列化され、${\displaystyle \sigma }$、 我々は持っています：

$t_{i,j}(\sigma )=t_{i,\sigma (j)}^{0}}$のために${\displaystyle i\in \{1,2,...,n\},j\in \{1,2,...,n\}}$

次に、${\displaystyle l_{i}(\sigma )}$そして${\displaystyle e_{i}(\sigma )}$スケジュールの最初と最後の日をそれぞれ表す${\displaystyle S}$行為者を必要とするものによって決定される${\displaystyle i}$それで俳優を見つけることができる${\displaystyle i}$採用される予定${\displaystyle l_{i}(\sigma )-e_{i}(\sigma )+1}$日々。しかし、この日々では、$\displaystyle r_{i}=\sum _{j=1}^{n}t_{ij}^{0}}$日数が必要とされているということは、${\displaystyle h_{i}(S)}$日数は不要です。私たちは次のものを持っています。

${\displaystyle h_{i}(S)=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}}$

不要な日数の総コストは以下のとおりです。

${\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}]}$

${\displaystyle K(\sigma )}$は最小化すべき目的関数となる。^{[ 1 ]}

タレントスケジューリング問題は、最適線形配置（OLA）問題に還元することでNP困難であることが証明できます。^{[ 2 ]}各俳優が2日間だけ必要で、すべての俳優の給料が1であるという制約を設けた場合でも、OLA問題に多項式時間で還元できます。したがって、この問題には擬似多項式アルゴリズムが存在する可能性は低いと考えられます。^{[ 3 ]}

整数計画モデルは次のように表されます。^{[ 4 ]}

このモデルでは、${\displaystyle e_{i}}$タレントにとって最も早い撮影日を意味する${\displaystyle i}$、${\displaystyle l_{i}}$タレントにとって最新の撮影日${\displaystyle i}$、${\displaystyle x_{j,k}}$プロジェクトのスケジュール、つまり

${\displaystyle x_{j,k}={\begin{cases}1&{\text{シーン }}j{\text{ が撮影日 }}k{\text{ に予定されている場合 }}\\0&{\text{それ以外の場合 }}\end{cases}}}$