Scheduling: Decreasing Time List Algorithm Example

Example

Find the completion time for the independent tasks of length 5, 8, 4, 9, 3, 3, 4 on two 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: 9, 8, 5, 4, 4, 3, 3.

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

The time to complete this schedule is 19.