Scheduling: List Processing Algorithm

Use the list processing algorithm to schedule these tasks on two processors using the following priority lists:

• T1,T3,T7,T2,T4,T5,T6
• T1,T3,T2,T4,T5,T6,T7

Solution

Here is the list processing algorithm:

• Assign the first available task to the first available processor.
• When a processor becomes available, we set it to work on the first task in the priority list which is ready. Ready means all tasks which needed to be completed before we started this task are done.

For the priority list T1,T3,T7,T2,T4,T5,T6 we get the following schedule:

Note that for this schedule, we could not start T6 on processor 2 once T4 was completed since T6 required T5 to be complete.

For the priority list T1,T3,T2,T4,T5,T6,T7 we get the following schedule:

Note that for this schedule, we could not start T6 on processor 2 once T5 was completed since T6 required T7 to be complete.

The second priority list produced a more optimal solution (the job was completed faster).