Scheduling problem

Jimmy Snyder

I posted this in the probability and statistics forum, but I didn't get a nibble. Anyone here care to make a suggestion?

The probability that project a will be complete at time t after it begins is given as:

$$$p_a(t) = \left\{ \begin{array}{ll} 0 & \mbox{if t \leq t_1} \\ \frac {(t - t_1)}{t_2-t_1} & \mbox{if t_1 \leq t \leq t_2} \\ 1 & \mbox{if t_2 \leq t} \right.$$$

In other words, the project requires at least $t_1$ to complete and will take no more than $t_2$. The probability of completion at any time between $t_1$ and $t_2$ is a linear function of t.

The probability that project b will be complete at time t after it begins is given as:
$$$p_b(t) = \left\{ \begin{array}{ll} 0 & \mbox{if t \leq t_3} \\ \frac {(t - t_3)}{t_4-t_3} & \mbox{if t_3 \leq t \leq t_4} \\ 1 & \mbox{if t_4 \leq t} \right.$$$

Project b will begin the moment project a is complete. Given t, what is the probability $p_{ab}(t)$ that both projects will be complete at time t. Obviously,
$$$p_{ab}(t) = \left\{ \begin{array}{ll} 0 & \mbox{if t \leq t_1 + t_3} \\ 1 & \mbox{if t_2 + t_4 \leq t} \right.$$$.

What is $p_{ab}(t)$ for $t_1 + t_3 \leq t \leq t_2 + t_4$?

mathman

This is a standard problem of finding the distribution function for the sum of 2 random variables. The solution is obtained by convoluting the distribution functions - in a Stieljes integral form.

In your case, pab(t)=(int(t1,t2)pb(t-s)ds)/(t2-t1).

Jimmy Snyder

mathman said:
This is a standard problem of finding the distribution function for the sum of 2 random variables. The solution is obtained by convoluting the distribution functions - in a Stieljes integral form.

In your case, pab(t)=(int(t1,t2)pb(t-s)ds)/(t2-t1).
Thanks mathman for taking this up. Do you mean

$$p_{ab}(t) = \int_{t_1}^{t_2}\frac{p_b(t-s)ds}{t_2-t_1}$$

mathman

Yes. I am sorry that I still haven't gotten the hang of using Latex.

I suggest you take the time to derive it yourself - you'll understand it better.

Jimmy Snyder

mathman said:
I suggest you take the time to derive it yourself - you'll understand it better.
I really don't know how to derive it. I don't think the equation that I wrote and you agreed to is correct. For one thing, it is not a convolution. Like you, I too expect that the answer might be a convolution, perhaps something like this:

$$p_{ab}(t) = \int p_a(s) \times p_b(t-s)ds$$

But I am not sure if it is correct. Also, I don't know what the limits of integration should be nor what constant factor might be necessary (although if I knew everything else, I could figure that out).

I also have reason to believe that the answer might not be a convolution after all. It seems to me possible that such an integral double counts some of the probability. I came to have that feeling after looking at some finite sums that look like the integral. In short, I still don't really know the answer and I need help.

By the way mathman, I learned the little tex I know by using the quote button on other people's posts. When you do that you can see both the raw tex and the final result.

Last edited:

mathman

In the integral, the term is not pa(s)ds. It is dpa(s), which can be expressed using the derivative,
p'a(s)ds.

If you had used the density functions (derivative of distributions), then the form you used would be correct to get the density function of the sum.

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving