生产计划与控制课件：PPC-L10-Scheduling-2.pdfVIP

Lecture 10 Operations Scheduling (2) Ye Cheng Department of Industrial Engineering, Tsinghua University Learning Goal of This Lecture Study scheduling algorithms for multiple jobs and multiple machines Learn principles and algorithms for stochastic scheduling problems Understand practical considerations in industrial circumstances Ye Cheng, Dept. of IE, Tsinghua University PPC Lecture 10 Operatio ns Scheduling (2) 2 Sequencing Algorithms for Multiple Machines  Example Permutation schedule  Total flow time  Mean flow time  Mean idle time Ye Cheng, Dept. of IE, Tsinghua University PPC Lecture 10 Operatio ns Scheduling (2) 3 Scheduling n Jobs on 2 Machines  Each job must be processed in the order machine 1 then machine 2 Optimization criterion: minimize the makespan Theorem: The optimal solution for scheduling n jobs on two machines is always a permutation schedule Ye Cheng, Dept. of IE, Tsinghua University PPC Lecture 10 Operatio ns Scheduling (2) 4 Johnson’s Rule (1/2)  Notation  Machines: A and B  Jobs are labeled i, for 1  i  n  Define processing times  Ai = Processing time of job i on machine A  Bi = Processing time of job i on machine B Rule: Job i precedes job (i + 1) if min(A , B ) min(A , B ) i i +1 i +1