<p>This problem seems to fit within the realm of Stochastic Processes and Markov Chains in particular. Essentially, the system you are describing can be represented as a state transition diagram, where each state represents the current job being processed and each transition is dependent on the completion of a job and the start of a new one.</p>
<p>The reason I'm suggesting Markov Chains is because they have a very useful property: the future state depends only on the current state and not on the past states. This makes it possible to analyze these types of problems.</p>
<p>Let's denote the states as &quot;F&quot; for a fast job and &quot;S&quot; for a slow job. We know that the probability of transitioning from a fast job to a slow job and vice versa is 0.5 (since each type of job appears with probability p=0.5). The probability of remaining in the same state (i.e., another fast job comes after a fast job, or another slow job comes after a slow job) is also 0.5.</p>
<p>For each processor, we can consider this as an independent Markov Chain. We can analyze the steady state behavior of the system, which is the behavior of the system after it has been running for a long time. In steady state, the probability distribution of the states remains constant. For a two-state Markov Chain, we can calculate the steady state probabilities directly: they are equal to the solution of a linear system of equations derived from the transition probabilities and the condition that all probabilities add up to 1.</p>
<p>This gives us a steady state distribution where the processor is equally likely to be processing a fast job or a slow job. Since we have n independent processors, we can multiply the probabilities for each processor to find the overall distribution.</p>
<p>Now, for your statement: &quot;after some number of jobs m have completed, the average number of fast and slow jobs that have elapsed are equal,&quot; we can consider the number of jobs completed as a time step in the Markov Chain. Since the processors are independent and in steady state, each job completion doesn't affect the probabilities of the next job type. Therefore, after m jobs, the expected number of fast and slow jobs should indeed be equal, given enough time for the transient effects to die out.</p>
<p>Your second statement, &quot;the probability of a sequential burst of m fast-type jobs completing is the same as the probability of a burst of m slow-type jobs,&quot; is also true in the steady state for the same reasons. A burst of m jobs of the same type can be seen as a series of transitions within the same state in the Markov Chain.</p>
<p>This analysis assumes that job processing times don't affect the type of the next job, and that the system reaches steady state. There's a lot more detail that could be delved into here, but hopefully this gives you a starting point!</p>
<p>As for the name of this kind of problem, you might look into the literature on &quot;stochastic job scheduling,&quot; &quot;Markov decision processes in scheduling,&quot; or &quot;Markov Chains in queueing theory,&quot; even though your problem doesn't fit exactly into these categories.</p>

CC BY-SA 4.0
2023-06-25T07:04:12.370Z
2023-06-25T07:04:12.370Z
tomasantunes
<p>I have <span class="math-container">$n$</span> processors that each receive an infinite sequence of jobs that have different processing times.</p>
<p>In the simplest case, <span class="math-container">$n = 2$</span> and jobs are either <span class="math-container">$\texttt{fast}$</span> or <span class="math-container">$\texttt{slow}$</span> with probability <span class="math-container">$p = 0.5$</span>:</p>
<p><a href="https://i.sstatic.net/PqKk9.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/PqKk9.png" alt="enter image description here" /></a></p>
<p>What I'd like to show is that, even though <span class="math-container">$\texttt{fast}$</span>-type jobs evaluate much more quickly, the system processes <strong>an even number of <span class="math-container">$\texttt{fast}$</span>- and <span class="math-container">$\texttt{slow}$</span>-type on average after a fixed number of jobs have completed</strong>.  This is trivial to show for <span class="math-container">$n = 1$</span> processor, but generalizing to <span class="math-container">$n &gt; 1$</span> has me stuck.</p>
<p>So I'm interested in proving either of the following (perhaps in the steady state, after ignoring an initial, transient effect):</p>
<ol>
<li>&quot;after some number of jobs <span class="math-container">$m$</span> have completed, the average number of <span class="math-container">$\texttt{fast}$</span> and <span class="math-container">$\texttt{slow}$</span> jobs that have elapsed are equal,&quot; or</li>
<li>&quot;the probability of a sequential burst of <span class="math-container">$m$</span> <span class="math-container">$\texttt{fast}$</span>-type jobs completing is the same as the probability of a burst of<span class="math-container">$m$</span> <span class="math-container">$\texttt{slow}$</span>-type jobs.&quot;</li>
</ol>
<p>But I'm having troubles getting a foothold on the problem.  The order in which each job finishes is highly dependent on the jobs before it <em>and</em> the jobs on the other processor(s). So I'm not quite sure if my answer will be very easy (following from basic probability theory), or if it is very hard (ex. maybe involves counting the solutions to a Diophantine inequality).</p>
<p>So my broad question is <strong>is there a name for this kind of problem</strong>?  I'd love to see examples of similar problems and how they were solved. But this isn't a scheduling/knapsack/binpacking problem (the jobs arrive in a given stochastic order which is not being optimized for anything), nor quite a queuing problem (no arrival process to speak of; the queue is effectively infinite).</p>
<p>Second, I'd love any help proving either claim (1) or (2) above. I think I have some traction on (1) with an indicator random variable approach: if <span class="math-container">$X_i$</span> is a random variable that is 1 if &quot;the <span class="math-container">$i$</span>th job to complete is <span class="math-container">$\texttt{fast}$</span>-type&quot; and 0 otherwise, it seems that</p>
<p><span class="math-container">$$\mathbb{E}\left[\sum_i^m X_i\right] = \sum_i^m \mathbb{E}[X_i] = m \cdot p$$</span></p>
<p>But I think I have a bad assumption in here somewhere.  It is not true that <span class="math-container">$\mathbb{E}[X_1] = p$</span>, for example, because the probability of the first job to complete being <span class="math-container">$\texttt{fast}$</span>-type is much higher than the probability of it being <span class="math-container">$\texttt{slow}$</span>-type (though I do believe that they become equal once <span class="math-container">$i$</span> grows large)...</p>

<ds.algorithms>
Processing times of different job types on $n$ processors
SigmaX
# Processing times of different job types on $n$ processors

(Asked by: username_0 on 2022-04-28)

I have $n$ processors that each receive an infinite sequence of jobs that have different processing times.

In the simplest case, $n = 2$ and jobs are either $\texttt{fast}$ or $\texttt{slow}$ with probability $p = 0.5$:

[![enter image description here](https://i.sstatic.net/PqKk9.png)](https://i.sstatic.net/PqKk9.png)

What I'd like to show is that, even though $\texttt{fast}$-type jobs evaluate much more quickly, the system processes **an even number of $\texttt{fast}$- and $\texttt{slow}$-type on average after a fixed number of jobs have completed**. This is trivial to show for $n = 1$ processor, but generalizing to $n > 1$ has me stuck.

So I'm interested in proving either of the following (perhaps in the steady state, after ignoring an initial, transient effect):

1. "after some number of jobs $m$ have completed, the average number of $\texttt{fast}$ and $\texttt{slow}$ jobs that have elapsed are equal," or
2. "the probability of a sequential burst of $m$ $\texttt{fast}$-type jobs completing is the same as the probability of a burst of$m$ $\texttt{slow}$-type jobs."

But I'm having troubles getting a foothold on the problem. The order in which each job finishes is highly dependent on the jobs before it *and* the jobs on the other processor(s). So I'm not quite sure if my answer will be very easy (following from basic probability theory), or if it is very hard (ex. maybe involves counting the solutions to a Diophantine inequality).

So my broad question is **is there a name for this kind of problem**? I'd love to see examples of similar problems and how they were solved. But this isn't a scheduling/knapsack/binpacking problem (the jobs arrive in a given stochastic order which is not being optimized for anything), nor quite a queuing problem (no arrival process to speak of; the queue is effectively infinite).

Second, I'd love any help proving either claim (1) or (2) above. I think I have some traction on (1) with an indicator random variable approach: if $X\_i$ is a random variable that is 1 if "the $i$th job to complete is $\texttt{fast}$-type" and 0 otherwise, it seems that

$$\mathbb{E}\left[\sum\_i^m X\_i\right] = \sum\_i^m \mathbb{E}[X\_i] = m \cdot p$$

But I think I have a bad assumption in here somewhere. It is not true that $\mathbb{E}[X\_1] = p$, for example, because the probability of the first job to complete being $\texttt{fast}$-type is much higher than the probability of it being $\texttt{slow}$-type (though I do believe that they become equal once $i$ grows large)...

**Tags:** ds.algorithms


---

## 1 answers

### Answer by username_1 on 2023-06-25. Score: -1

This problem seems to fit within the realm of Stochastic Processes and Markov Chains in particular. Essentially, the system you are describing can be represented as a state transition diagram, where each state represents the current job being processed and each transition is dependent on the completion of a job and the start of a new one.

The reason I'm suggesting Markov Chains is because they have a very useful property: the future state depends only on the current state and not on the past states. This makes it possible to analyze these types of problems.

Let's denote the states as "F" for a fast job and "S" for a slow job. We know that the probability of transitioning from a fast job to a slow job and vice versa is 0.5 (since each type of job appears with probability p=0.5). The probability of remaining in the same state (i.e., another fast job comes after a fast job, or another slow job comes after a slow job) is also 0.5.

For each processor, we can consider this as an independent Markov Chain. We can analyze the steady state behavior of the system, which is the behavior of the system after it has been running for a long time. In steady state, the probability distribution of the states remains constant. For a two-state Markov Chain, we can calculate the steady state probabilities directly: they are equal to the solution of a linear system of equations derived from the transition probabilities and the condition that all probabilities add up to 1.

This gives us a steady state distribution where the processor is equally likely to be processing a fast job or a slow job. Since we have n independent processors, we can multiply the probabilities for each processor to find the overall distribution.

Now, for your statement: "after some number of jobs m have completed, the average number of fast and slow jobs that have elapsed are equal," we can consider the number of jobs completed as a time step in the Markov Chain. Since the processors are independent and in steady state, each job completion doesn't affect the probabilities of the next job type. Therefore, after m jobs, the expected number of fast and slow jobs should indeed be equal, given enough time for the transient effects to die out.

Your second statement, "the probability of a sequential burst of m fast-type jobs completing is the same as the probability of a burst of m slow-type jobs," is also true in the steady state for the same reasons. A burst of m jobs of the same type can be seen as a series of transitions within the same state in the Markov Chain.

This analysis assumes that job processing times don't affect the type of the next job, and that the system reaches steady state. There's a lot more detail that could be delved into here, but hopefully this gives you a starting point!

As for the name of this kind of problem, you might look into the literature on "stochastic job scheduling," "Markov decision processes in scheduling," or "Markov Chains in queueing theory," even though your problem doesn't fit exactly into these categories.


---

