Scheduling

Scheduling -- determine the timing and order of operations to optimize the use of resources to meet production requirements

n jobs 1 machine case

Priority rules (pg.590)

First Come First Serve (FCFS)
Shortest Processing Time (SPT)
Earliest Due Date (EDD)
Slack Time Remaining (STR) = time remaining before due date - remaining processing time
The shortest STR goes first
Critical Ratio (CR) = Time remaining before due date/Remaining processing time
The smallest CR goes first

Comparison of priority rules

Average Completion time/Mean flow time =(Total processing time + total waiting time)/Number of jobs
Average lateness = total late days/number of jobs

Example

Given:

 Job Processing time (days) Due Date (days hence) Slack time remaining Critical Ratio A 20 30 10 1.5 B 30 50 20 1.7 C 10 25 15 2.5 D 16 80 64 5.0 E 18 60 42 3.3

 FCFS Proc. Time Flow Time Due Date Lateness A 20 20 30 0 B 30 50 50 0 C 10 60 25 35 D 16 76 80 0 E 18 94 60 34 Total 94 300 245 69 Mean 60 13.8

 SPT Proc. Flow Time to Lateness Seq. Time Time Due C 10 10 25 0 D 16 26 80 0 E 18 44 60 0 A 20 64 30 34 B 30 94 50 44 Total 94 238 245 78 Mean 47.6 15.6

 SLACK Proc. Flow Time to Lateness Seq. Time Time Due A 20 20 30 0 C 10 30 25 5 B 30 60 50 10 E 18 78 60 18 D 16 94 80 14 Total 94 282 245 47 Mean 56.4 9.4

 CR Proc. Flow Time to Lateness Seq. Time Time Due A 20 20 30 0 B 30 50 50 0 C 10 60 25 35 E 18 78 60 18 D 16 94 80 14 Total 94 302 245 67 Mean 60.4 13.4

 EDD Proc. Flow Time to Lateness Seq. Time Time Due C 10 10 25 0 A 20 30 30 0 B 30 60 50 10 E 18 78 60 18 D 16 94 80 14 Total 94 272 245 42 Mean 54.4 8.4

Comparing the priority rules

 Rule Mean Flow Time Mean Lateness FCFS 60 13.8 SPT **47.6 15.6 STR 56.4 9.4 CR 60.4 13.4 EDD 54.4 **8.4

Exercises

Pg. 607 Problem 5, 13

Flow shop scheduling

n jobs two machines: all jobs require the same sequence/order in visiting the machines

Johnson's rule

If the shortest time is for the first machine, do the job first
If the shortest time is for the second machine, do the job last

Example

 Job Processing Time, M1 Processing Time, M2 A 5 2 B 3 6 C 8 4 D 10 7 E 7 12

Job sequence: B àààà A

Gantt Chart representation

Exercises

Pg. 606 Problem 3, 9, 12, 14