Sunday, February 1, 2009

An Example to Use Critical Ratio Method to Schedule

A machine center in a job shop for a local fabrication company has five unprocessed jobs remaining at a particular point in time. The jobs are labeled 1,2,3,4 and 5 in the order that they entered the shop. The respective processing times and due dates are given in the table below
Job number Processing Time Due Date
1 11 61
2 29 45
3 31 31
4 1 33
5 2 32
After each job has been processed, we compute
(Due date-Current time)/Processing time
known as the critical ratio and schedule the next job in order to minimize the value of the critical ratio. The idea behind critical ratio scheduling is to provide a balance between SPT(shortest processing time), which only considers processing time, and EDD(earliest due time), which only considers due dates. The ratio will grow smaller as the current time approaches the due date, and more priority will be given to those jobs with longer processing times. One disadvantage of the method is that the critical ratios need to be recalculated each time a job is scheduled.
It is possible that the numerator will be negative for some or all of the remaining jobs. When that occurs it means that the job is late, and we will assume that late jobs are automatically scheduled next. If there is more than one late job, then the late jobs are scheduled in SPT sequence.
First we compute the critical ratios starting at time t=0
Current time: t=0
Job Processing Time Due Date Critical Ratio
1 11 61 61/11(5.545)
2 29 45 45/29(1.552)
3 31 31 31/31(1.000)
4 1 33 33/1(33.000)
5 2 32 32/2(16.000)
The minimum value corresponds to job 3, so job 3 is performed first. As job 3 requires 31 units of time to process, we must update all of the critical ratios in order to determine the next job to process. We move the clock to time t=31 and recomputed the critical ratios.
Current time: t=31
Job Processing Time (Due Date-Current Time) Critical Ratio
1 11 30 30/11(2.727)
2 29 14 14/29(0.483)
4 1 2 2/1(2.000)
5 2 1 1/2(0.500)
The minimum is 0.483, which corresponds to job 2. Hence, job 2 is scheduled next. Since job 2 has a processing time of 29, we update the clock to time t=31+29=60
Current time: t=60
Job Processing Time (Due Date-Current Time) Critical Ratio
1 11 1 1/11(0.0909)
4 1 -27 -27/1<0
5 2 -28 -28/2<0
Jobs 4 and 5 are now late so they are given priority and scheduled next. Since they are scheduled in SPT order, they are done in the sequence job 4, then job 5. Finally, job 1 is scheduled last.
Summary of the Results for Critical Ratio Scheduling
Job number Processing Time Completion Time Tardiness
3 31 31 0
2 29 60 15
4 1 61 28
5 2 63 31
1 11 74 13
Total 289 87
Mean flow time=289/5=57.8
Average tardiness=87/5=17.4
Number of tardy jobs=4

1 comment:

  1. Hey! i need to code this, and with little number of jobs, it works fine, but with 20 jobs, it doesn't work, anyone knows how to code it properly??

    ReplyDelete