Solving Scheduling Problem - Probability & Statistics Forum

  • Thread starter Jimmy Snyder
  • Start date
  • Tags
    Scheduling
In summary, the conversation was about determining the probability of two projects, A and B, being completed at a specific time after they begin. The probability of project A being completed at time t is a linear function between t1 and t2, while the probability of project B being completed at time t is also a linear function between t3 and t4. Project B begins after project A is complete. The probability of both projects being completed at time t is given by a convolution of the two distribution functions, with limits of integration between t1 and t2 and a constant factor of (t2-t1). However, there is some uncertainty about the correct form of the integral and further help is needed.
  • #1
Jimmy Snyder
1,127
20
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:

[tex]
\[ 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. \][/tex]

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

The probability that project b will be complete at time t after it begins is given as:
[tex]
\[ 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. \][/tex]


Project b will begin the moment project a is complete. Given t, what is the probability [itex]p_{ab}(t)[/itex] that both projects will be complete at time t. Obviously,
[tex]
\[ 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. \][/tex].

What is [itex]p_{ab}(t)[/itex] for [itex]t_1 + t_3 \leq t \leq t_2 + t_4[/itex]?
 
Physics news on Phys.org
  • #2
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).
 
  • #3
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

[tex]p_{ab}(t) = \int_{t_1}^{t_2}\frac{p_b(t-s)ds}{t_2-t_1}[/tex]
 
  • #4
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.
 
  • #5
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:

[tex]p_{ab}(t) = \int p_a(s) \times p_b(t-s)ds[/tex]

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:
  • #6
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.
 

1. What is a scheduling problem?

A scheduling problem is a mathematical or computational problem that involves finding the most efficient way to allocate resources or schedule tasks within a given timeframe. It can involve factors such as time constraints, resource availability, and optimization of certain objectives.

2. How can probability and statistics be used to solve scheduling problems?

Probability and statistics can be used to analyze and predict the likelihood of different events occurring within a scheduling problem. This can help in making informed decisions about which tasks to prioritize and how to allocate resources effectively.

3. What are some common techniques for solving scheduling problems?

Some common techniques for solving scheduling problems include linear programming, dynamic programming, and heuristics. Linear programming involves optimizing a linear objective function subject to constraints, while dynamic programming involves breaking down a problem into smaller subproblems. Heuristics use a set of rules or guidelines to make decisions in a problem that may not have an optimal solution.

4. How do scheduling problems impact real-world situations?

Scheduling problems can have a significant impact on real-world situations, particularly in industries where time and resource management are crucial, such as manufacturing, transportation, and healthcare. Efficient scheduling can lead to cost savings, increased productivity, and improved customer satisfaction.

5. What are some challenges in solving scheduling problems?

Some challenges in solving scheduling problems may include dealing with a large number of variables and constraints, finding an optimal solution within a reasonable amount of time, and accounting for uncertainties and changing conditions. Additionally, the complexity of scheduling problems can make it difficult to find a solution that satisfies all objectives and constraints.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
564
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
727
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
  • Differential Equations
Replies
4
Views
1K
  • Differential Equations
Replies
1
Views
716
  • Introductory Physics Homework Help
2
Replies
40
Views
2K
  • Quantum Physics
Replies
8
Views
695
  • Special and General Relativity
4
Replies
123
Views
5K
  • Introductory Physics Homework Help
Replies
8
Views
1K
Back
Top