Multiple choices for a single case in the recursive formula of a Dynamic Programming algorithm

Question

I am developing a Dynamic Programming algorithm for a problem in scheduling. In the recursive formula, I have three cases: (1) $t_{i-1} = int$ (2) $t_{i-1} = app \quad \& \quad r(j) \leq p $ and (3) $t_{i-1} = app \quad \& \quad r(j) > p$. However, for two of them I can go to two directions.

The formula is shown in the following, that is simplified to avoid misleading. In fact, cases 1 and 2 are the same, but can go into two directions ''app'' and ''int''. The same is for cases 3 and 4. But case 5 has only one option that is ''app''. I think the current format of the formula is missing something since the condition for cases 1 and 2, and for cases 3 and 4, is the same. What is the correct form of interpreting this formula?

\begin{equation} z_i = \begin{cases} z_{i-1} + p + (app) & \text{if $t_{i-1} = int$}\\ z_{i-1} + p+ (int) & \text{if $t_{i-1} = int$}\\ z_{i-1} + 2p + (app) & \text{if $t_{i-1} = app$} \quad \& \quad r(j) \leqslant p\\ z_{i-1} + 2p + (int) & \text{if $t_{i-1} = app$} \quad \& \quad r(j) \leqslant p\\ z_{i-1} + r(j) + (app) &\text{if $t_{i-1} = app$} \quad \& \quad r(j) > p \\ \end{cases} \end{equation}

Added: One thing that comes to my mind is to write it with two $\min$ functions. Since from the three conditions with $(app)$ (i.e. conditions 1, 3 and 5) one with lower objective function will be remained, and the same for the two with $(int)$ option (i.e. conditions 2 and 4). How about writing with two $\min$ functions with distinct condition for each?! For example: \begin{equation} z_i = \begin{cases} \min\begin{cases} z_{i-1} + p + (app) & \text{if $t_{i-1} = int$} \\ z_{i-1} + 2p + (app) & \text{if $t_{i-1} = app$} \quad \& \quad r(j) \leqslant p \\ z_{i-1} + r(j) + (app) &\text{if $t_{i-1} = app$} \quad \& \quad r(j) > p\end{cases} \\ \min\begin{cases}z_{i-1} + p+ (int) & \text{if $t_{i-1} = int$} \\ z_{i-1} + 2p + (int) & \text{if $t_{i-1} = app$} \quad \& \quad r(j) \leqslant p \end{cases}\\ \end{cases} \end{equation}

Answer 1

I think it's cleanest if you think about formulating your DP something like this:

$$z_i = \min_{a\in A(t_{i-1})} \{f_i(a)\},$$

where

• $A(t_{i-1})$ is the set of available actions you can take, given the value of $t_{i-1}$, that is:

$$A(t_{i-1}) = \begin{cases} \{C_{i-1}, C_{i-1}-2\}, & \text{if } t_{i-1}=int, \\ \{C_{i-1}\}, & \text{if } t_{i-1}=app,\end{cases}$$ or something like that.

• $f_i(a)$ is the cost/reward function value if you take action $a$ for job $i$. You haven't said what your objective function is, and I don't know what $p$ or $r(j)$ are, but presumably those can be incorporated into $f_i(a)$.

I'm sure I'm getting some of the notation and concepts wrong, but in general I suggest that you distinguish between the state ($t_{i-1}$), the actions ($C_{i-1}-2$, etc.), and the costs/rewards ($f_i(a)$).