0
$\begingroup$

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.

To explain more, suppose I have job $𝑖−1$ scheduled. Then, if $𝑡_{𝑖−1}=𝑖𝑛𝑡$, I can schedule the next job (job $𝑖$) with two conditions: (1): start it immediately after job $𝑖−1$ is finished, i.e. at point $𝐶_{𝑖−1}$ or (2): start it two time slots earlier than job $𝑖−1$ is finished, i.e. at $𝐶_{𝑖−1}−2$. Both directions should be checked in the DP.

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}

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}

$\endgroup$
1
$\begingroup$

If you want to have two values for each stage, one for $t_{i - 1} = app$ and one for $t_{i - 1} = int$, which are derived from three or two cases respectivelly then you will need to store two dynamic programming values for each stage. Let's name these values for the $i$-th stage $z_{app, i}$ and $z_{int, i}$ respectively. $z_{app, i}$ is the minimum additive value of your objective function for stages up to the $i$-th one if you used (app) in the $i$-th stage, while $z_{int, i}$ has a similar definition. Now let's see what the format of the dp recursion will look like:

$ z_{app, i} = min \begin{cases} z_{int, i - 1} + p + (app), & \text{if } t_{i - 1} = int\\ z_{app, i - 1} + 2p + (app), & \text{if } t_{i - 1} = app \wedge r(j) \leq p\\ z_{app, i - 1} + r(j) + (app), & \text{if } t_{i - 1} = app \wedge r(j) > p \end{cases} $

$ z_{int, i} = min \begin{cases} z_{int, i - 1} + p + (int), & \text{if } t_{i - 1} = int\\ z_{app, i - 1} + 2p + (int), & \text{if } t_{i - 1} = app \wedge r(j) \leq p \end{cases} $

Note that that $t_{i - 1} = int$ dictates the use of $z_{int, i - 1}$ which is the optimal value of the previous stage when (int) was used. The case when $t_{i - 1} = app$ is faced similarly by using $z_{app, i - 1}$. We have represented the optimal values of each stage using mutual recursion. Equivalently you can use the following recursion:

$ z_{app, i} = (app) + min \begin{cases} z_{int, i - 1} + p, & \text{if } t_{i - 1} = int\\ z_{app, i - 1} + 2p, & \text{if } t_{i - 1} = app \wedge r(j) \leq p\\ z_{app, i - 1} + r(j), & \text{if } t_{i - 1} = app \wedge r(j) > p \end{cases} $

$ z_{int, i} = (int) + min \begin{cases} z_{int, i - 1} + p, & \text{if } t_{i - 1} = int\\ z_{app, i - 1} + 2p, & \text{if } t_{i - 1} = app \wedge r(j) \leq p \end{cases} $

This way the dynamic programming calculations will speed up by a constant factor.

$\endgroup$
  • $\begingroup$ The problem is that we can not compare a solution with (app) to one with (int). Actually, the minimum can be computed over those that are all in (app), and those that are all in (int) form. Despite they have different conditions. I mean, the two items in $ \min \{ z_{i - 1} + p + (app), z_{i - 1} + p + (int) \}, & \text{if } t_{i - 1} = int $ are not comparable. $\endgroup$ – Mostafa May 1 at 11:27
  • $\begingroup$ @Mostafa Do you mean that there are two cases: 1) You will always use (int), 2) You will always use (app)? So you want to solve each of these two cases separately and choose the best of the two? $\endgroup$ – George Vidalakis May 1 at 12:02
  • $\begingroup$ Actually no. I should check them and follow both directions at each step. I mean, I check the two options of (int), and the three options of (app), and then the minimum from each one is selected to be stored for next stage. I mean, at the end of the stage, I have a minimum for (int) and a minimum for (app). $\endgroup$ – Mostafa May 1 at 12:40
  • $\begingroup$ @Mostafa So what is the problem with the solution you suggest in your example? $\endgroup$ – George Vidalakis May 1 at 12:46
  • $\begingroup$ In the first equation in my question, I have the same condition on lines 1 and 2, but two different cases. Similarly, I have the same condition on lines 3 and 4, but two different cases. My question is how to present the equation correctly. $\endgroup$ – Mostafa May 1 at 12:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.