Problem Statement

Given number of scenes with required actor in the scene where each actors is paid per day. We want to minimize the total production cost (Hentenryck, 2002)

GIF from GIPHY https://giphy.com/gifs/spongebob-season-3-spongebob-squarepants-l1KtWF6aBGvYx5XRm

Variables

Let

• $x_{id} \in \set{0,1}$. If $x_{i,d}=1$ the actor $i$ is assigned on day $d$ . Otherwise $0$
• $y_{s,d}\in \set{0,1}$. If $y_{s,d}=1$ the scene $s$ is assigned on day $d$. Otherwise $0$
• $s$ be the list of scenes that contains list of actors required to be in the scene.
• $d \in \mathbb N$ are days
• $c_i\in \mathbb R$ be the cost of hiring an actor $i$ in each day.
• Let $M \in \mathbb Z$ be the max number of days
• Let $N \in \mathbb Z$ be the total number of scenes

Assumption & Constraints

• In one day there can only be max 4 Scenes recorded for each $d$ day, $\forall d\in days$

$$ \sum_{s\in scenes}^{N} y_{s,d} \leq 4 $$

• All scenes must be recorded, $\forall s\in Scenes$

  $$ \sum_{d \in days}^{M} y_{s,d}=1 $$

• Each scene have a required actor, $\forall s \in Scenes$, $\forall d \in days$, $\forall a \in actors$, if $a \in s$ then

  $$ y_{s,d} \implies x_{a,d} $$

Objective Function

We want to minimize paying the actor for each days.

$$ \min \sum_{d\in days} \sum {i \in actors}x{i,d}c_i $$