Stochastic Scheduling:Static Analysis The issue dealt with is the uncertainty of the processing times. Multiple Machine Assume that the n jobs have processing times t1,t2,...,t which are exponential random variables with rates u,42,...,u This means t that the expected time required to complete job i, E(t)=/ui In parallel processing,the jobs need to be processed on only one machine,and any job can be processed on either machine. Assume that at time t=0,machine 1 is occupied with a prior job, job 0,and its remaining processing time is to. The remaining jobs are processed as follows:Let [1],[2],...,[n] be a permutation of the n jobs 圈上泽充道大酱
Stochastic Scheduling: Static Analysis The issue dealt with is the uncertainty of the processing times. • Multiple Machine Assume that the n jobs have processing times t1, t2, …, tn, which are exponential random variables with rates μ1, μ 2,…, μ n. This means that the expected time required to complete job i, E ( ti)=1/μi . In parallel processing, the jobs need to be processed on only one machine, and any job can be processed on either machine. Assume that at time t=0, machine 1 is occupied with a prior job, job 0, and its remaining processing time is t 0. The remaining jobs are processed as follows: Let [1], [2],…, [n] be a permutation of the n jobs
Stochastic Scheduling:Static Analysis The issue dealt with is the uncertainty of the processing times. Multiple Machine Let To≤TI≤T2≤..≤Tn,be the completion times of successive jobs.The makespan is the time of completion of the last job, which is T The expected value of the makespan is minimized by using the longest-expected-processing-time-first rule. The optimality of scheduling the jobs in decreasing order of their expected size rather than in increasing order (SPT rule)is more likely a result of parallel processing than of randomness of the job times) 圈上泽充道大酱
Stochastic Scheduling: Static Analysis The issue dealt with is the uncertainty of the processing times. • Multiple Machine Let T0 ≤ T1≤ T2 ≤ … ≤ Tn, be the completion times of successive jobs. The makespan is the time of completion of the last job, which is Tn. The expected value of the makespan is minimized by using the longest-expected-processing-time-first rule. The optimality of scheduling the jobs in decreasing order of their expected size rather than in increasing order (SPT rule) is more likely a result of parallel processing than of randomness of the job times)