Scheduling: Decreasing Time List Algorithm

Find the completion time for the independent tasks of length 8, 11, 17, 14, 16, 9, 2, 1, 18, 5, 3, 7,6, 2, 1 on three processors using the decreasing time list algorithm.

Solution

The decreasing time list algorithm creates a priority list for independent tasks by listing the tasks in order of decreasing time (this schedules long tasks first).

The sorted list becomes: 18, 17, 16, 14, 11, 9, 8, 7, 6, 5, 3, 2, 2, 1, 1.

Here is the resulting schedule (the tasks are labelled by their times when the tasks are independent):

Since the schedule produced a rectangle, we know that this is an optimal schedule. The time it will take to complete the tasks on three processors is 40.

For your information, here is the resulting schedule if we have four processors available:

The time it will take with four processors to complete the job is 31.