Production Planning Control Operations Scheduling Dr.Na genG Prof.Zhibin JIANG Department of Industrial Engineering Management Shanghai Jiao Tong University
Production Planning & Control Dr. Na GENG Prof. Zhibin JIANG Department of Industrial Engineering & Management Shanghai Jiao Tong University Operations Scheduling
Operations Scheduling Contents Introduction Job Shop Scheduling Terminology ·Sequencing Rules Sequencing Theory for a Single Machine Sequencing Theory for Multiple Machines Stochastic Scheduling:Static Analysis Assembly Line Balancing Summary 国上泽充鱼大皇
Operations Scheduling Contents • Introduction • Job Shop Scheduling Terminology • Sequencing Rules • Sequencing Theory for a Single Machine • Sequencing Theory for Multiple Machines • Stochastic Scheduling: Static Analysis • Assembly Line Balancing • Summary
图 Stochastic Scheduling:Static Analysis The issue dealt with is the uncertainty of the processing times. Single Machine Suppose that n jobs are to be processed through a single machine. Assume that the job times,t1,12,...,are random variables with known distribution functions. The objective is to minimize the expected average weighted flow time, MimE(（∑-1u,E) Where u;are the weights and F,is the random flow time of job i. 圈上泽充道大酱
Stochastic Scheduling: Static Analysis The issue dealt with is the uncertainty of the processing times. • Single Machine Suppose that n jobs are to be processed through a single machine. Assume that the job times, t1, t2,…, tn, are random variables with known distribution functions. The objective is to minimize the expected average weighted flow time, ܧ ݊݅ܯ ଵ ∑ ୀଵ ܨݑ Where ui are the weights and Fi is the random flow time of job i
Stochastic Scheduling:Static Analysis The issue dealt with is the uncertainty of the processing times. Single Machine Rothkopf (1966)has shown that the optimal solution is to sequence the jobs so that job i precedes job i+1,if E(t)E(t+1) ui 认i+1 If u,=1,then this rule equals with SPT. Banerjee (1965)shows that if the objective is to minimize the maximum over all jobs of the probability that a job is late,then the optimal schedule is to order the jobs according to EDD (or earliest expected due date). 国上泽充鱼大皇
Stochastic Scheduling: Static Analysis The issue dealt with is the uncertainty of the processing times. • Single Machine Rothkopf (1966) has shown that the optimal solution is to sequence the jobs so that job i precedes job i+1, if ܧ ݐ ݑ ൏ ܧ ାଵݐ ାଵݑ If ui=1, then this rule equals with SPT. Banerjee (1965) shows that if the objective is to minimize the maximum over all jobs of the probability that a job is late, then the optimal schedule is to order the jobs according to EDD (or earliest expected due date)
Stochastic Scheduling:Static Analysis The issue dealt with is the uncertainty of the processing times. Multiple Machine An assumption that is usually made for the multiple-machine problem is that the distribution of job times is exponential. This assumption is important and necessary because the memoryless property. The problem:n jobs are to be processed through two identical parallel machines.Each job needs to be processed only once on either machine. The objective is to minimize the expected time that elapses from time zero until the last job has completed processing (expected makespan). @上帝充鱼大￥
Stochastic Scheduling: Static Analysis The issue dealt with is the uncertainty of the processing times. • Multiple Machine An assumption that is usually made for the multiple-machine problem is that the distribution of job times is exponential. This assumption is important and necessary because the memoryless property. The problem: n jobs are to be processed through two identical parallel machines. Each job needs to be processed only once on either machine. The objective is to minimize the expected time that elapses from time zero until the last job has completed processing (expected makespan)
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)
Stochastic Scheduling:Static Analysis The issue dealt with is the uncertainty of the processing times. ·Multiple Machine Machine 1 Machine 2 To Tn Tn-1=ZR=oti,Tn-1=Tn -I Therefore,2Tn =oti+I √Min Tn=∑oti+MinI Because I is minimized when the processing time of last job is minimized,we schedule the jobs in order of decreasing expected processing time. 圈上泽充道大酱
Stochastic Scheduling: Static Analysis The issue dealt with is the uncertainty of the processing times. • Multiple Machine ܶ ܶିଵ ൌ ∑ ݐ ୀ , ܶିଵ ൌ ܶ െ ܫ Therefore, 2ܶ ൌ ∑ ܫ ୀ ݐ Min Tn = ∑ ݐ ୀ +Min I Because I is minimized when the processing time of last job is minimized, we schedule the jobs in order of decreasing expected processing time
Stochastic Scheduling:Static Analysis Johnson's Rule:Job i precedes job i+1 if min(Ai,Bi+1)<min(Ai+1,Bi) Scheduling n jobs on two machines in a flow shop setting,that is, where each job must be processed through machine A first,then through machine B. Suppose that 41,423...,4 and B1,B23...,B are exponential random variables with respective rates a,a2,....a and b,b2,. We now wish to minimize the expected value of the makespan. 圈上泽充道大酱
Stochastic Scheduling: Static Analysis The issue dealt with is the uncertainty of the processing times. • The Two-Machine Flow Shop Case Scheduling n jobs on two machines in a flow shop setting, that is, where each job must be processed through machine A first, then through machine B. Suppose that A1, A 2,…, A n and B1, B 2,…, B n are exponential random variables with respective rates a1, a 2,…, a n and b1, b 2,…, b n. We now wish to minimize the expected value of the makespan. Johnson’s Rule: Job i precedes job i+1 if min(Ai, Bi+1)<min(Ai+1,Bi)
Stochastic Scheduling:Static Analysis Johnson's Rule:Job i precedes job i+1 if min(Ai,Bi+1)<min(Ai+1,Bi) The minimum of two exponential random variables has a rate equal to the sum of the rates. Fmin(z）=P{min(A,B)≤z =1-P{min(A,B)≥z =1-P{A≥Z,B≥Z =1-{1-P{A≤z}{1-P{B≤z =1-{1-F4(z)}{1-FB(z)} =1-{1-(1-e-a2)}{1-(1-e-b2)} =1-e-(a+b)z when z≥0 国上泽充鱼大皇
Stochastic Scheduling: Static Analysis The issue dealt with is the uncertainty of the processing times. • The Two-Machine Flow Shop Case The minimum of two exponential random variables has a rate equal to the sum of the rates. ݖ ܤ ,ܣ ݊݅݉ ܲൌ ݖ ܨ ݖ ܤ ,ܣ ݊݅݉ ܲൌ1െ ݖ ܤ ,ݖ ܣ ܲൌ1െ ݖܤ ܲ1െ ݖܣ ܲ1െ ൌ1െ ൌ 1 െ 1െܨ ܨ1െ ݖ ݖ ൌ 1െ 1 െ 1െ݁ି௭ 1 െ 1െ݁ି௭ ൌ1െ݁ ି ା ௭ when z0 Johnson’s Rule: Job i precedes job i+1 if min(Ai, Bi+1)<min(Ai+1,Bi)
