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)