There are three jobs that need to be processed, with the processing time of job i being exponential with rate μi . There are two processors available, so processing on two of the jobs can immediately start, with processing on the final job to start when one of the initial ones is finished.

(a) Let Ti denote the time at which the processing of job i is completed.

If the objective is to minimize E[T1 + T2 + T3], which jobs should be initially processed if μ1

(b) Let M, called the makespan, be the time until all three jobs have been processed. With S equal to the time that there is only a single processor working, show that

For the rest of this problem, suppose that μ1 = μ2 = μ, μ3 = λ. Also, let P(μ) be the probability that the last job to finish is either job 1 or job 2, and let P(λ) = 1 − P(μ) be the probability that the last job to finish is job 3.

(c) Express E[S] in terms of P(μ) and P(λ).
Let Pi,j (μ) be the value of P(μ) when i and j are the jobs that are initially started.

(d) Show that P1,2(μ) ≤ P1,3(μ).

(e) If μ>λ show that E[M] is minimized when job 3 is one of the jobs that is initially started.

(f) If μ

Transcribed Image Text:

3 2E[M]=E[S]+1/Mi i=1