- WELCOME TO A LESSON ON THE DECREASING TIME ALGORITHM.
IN THIS LESSON WE WILL APPLY THE DECREASING TIME ALGORITHM
TO DETERMINE A PRIORITY LIST AND THEN CREATE A SCHEDULE
USING THE LIST PROCESSING ALGORITHM.
IN OUR PREVIOUS EXAMPLES WE WERE GIVEN THE PRIORITY LIST,
BUT NOW WE'LL LOOK AT A METHOD OF CREATING A PRIORITY LIST
THAT CAN BE THEN USED TO CREATE A SCHEDULE.
THE DECREASING TIME ALGORITHM TAKES THE APPROACH OF TRYING
TO GET THE VERY LONG TASKS COMPLETED AS SOON AS POSSIBLE
BY PUTTING THEM FIRST ON THE PRIORITY LIST.
SO TO APPLY THE DECREASING TIME ALGORITHM WE CREATE
THE PRIORITY LIST BY LISTING THE TASKS IN ORDER
FROM LONGEST COMPLETION TIME TO SHORTEST COMPLETION TIME.
LET'S TAKE A LOOK AT AN EXAMPLE.
WE WANT TO USE THE DECREASING TIME ALGORITHM TO CREATE
A PRIORITY LIST FOR THE DIAGRAPH BELOW.
NOTICE HOW WE HAVE A TOTAL OF NINE TASKS,
AND THE TIME REQUIREMENT FOR EACH TASK IS IN PARENTHESIS.
LET'S GO AHEAD AND ASSUME THEY'RE HOURS.
NOTICE, TASK 2 TAKES THE LONGEST AT 12 HOURS.
AND THEREFORE, TASK 2 IS FIRST ON THE PRIORITY LIST.
AND THIS IS FOLLOWED BY TASK 5 THAT TAKES 11 HOURS, SO TASK 5
IS LISTED SECOND ON THE PRIORITY LIST.
NOTICE NEXT, BOTH TASK 3 AND TASK 6 TAKE 10 HOURS.
WHENEVER THE COMPLETION TIMES ARE THE SAME WHEN APPLYING
THE DECREASING TIME ALGORITHM, WE'D NORMALLY LIST THE TASK
WITH THE LOWEST NUMBER FIRST.
SO WE'LL LIST TASK 3 FIRST AND THEN TASK 6.
NEXT, WE HAVE TASK 7 AT 5 HOURS, FOLLOWED BY TASK 1 AT 4 HOURS.
SO TASK 5, TASK 1, SO NOW WE'RE DOWN TO 4 HOURS.
THAT LEAVES TASK 8 AT 3 HOURS.
AND NOTICE THE LAST TWO TASKS BOTH TAKE 2 HOURS, TASK 4
AND TASK 9.
AND AGAIN, IT'S TYPICAL TO LIST THE TASK
WITH THE LOWEST NUMBER FIRST, SO WE'LL LIST TASK 4
FOLLOWED BY TASK 9.
NOW TO ENTER THIS INTO OUR HOMEWORK, WE'LL JUST ENTER
2, 5, 3, 6, 5, 1, 8, 4, 9.
THIS IS THE DECREASING TIME ALGORITHM WHICH CAN BE USED
TO CREATE A PRIORITY LIST.
NOW LETS TAKE A LOOK AT A SECOND EXAMPLE.
HERE WE WANT TO USE THE DECREASING TIME ALGORITHM
TO CREATE A PRIORITY LIST FROM THE DIAGRAPH BELOW
JUST LIKE WE JUST DID, AND THEN USE THE LIST
PROCESSING ALGORITHM TO CREATE A SCHEDULE.
SO IF WE RANK THESE TASKS BASED UPON THE COMPLETION TIME,
WITH THE HIGHEST COMPLETION TIMES FIRST, IT WOULD GIVE US
THIS PRIORITY LIST.
AND YOU MAY WANT TO PAUSE THE VIDEO TO CHECK THIS.
THESE ARE LISTED FROM THE HIGHEST COMPLETION TIME
TO THE LOWEST COMPLETION TIME.
AND NOW TO APPLY THE LIST PROCESSING ALGORITHM
WE'LL CIRCLE THE READY TASK, WHICH ARE THE TASKS
THAT DON'T HAVE ANY PREREQUISITE TASKS,
WHICH WOULD BE TASK 1, 2, 3, AND 4.
WE'LL ALSO CIRCLE THEM ON THE PRIORITY LIST.
HERE'S TASK 4, 3, 1, AND 2.
NOW WE WANT TO CREATE A SCHEDULE WITH TWO PROCESSORS
SO WE'LL CALL THIS PROCESSOR 1, AND WE'LL CALL THIS PROCESSOR 2.
THE HIGHEST PRIORITY READY TASK IS NOW ASSIGNED TO PROCESSOR 1,
WHICH IS TASK 4, WHICH TAKES 10 HOURS.
SO TASK 4 IS ASSIGNED TO PROCESSOR 1,
AND NOW TASK 4 IS IN PROGRESS, WHICH WE'LL IDENTIFY
WITH A SINGLE LINE THROUGH TASK 4.
THE NEXT HIGHEST PRIORITY READY TASK IS TASK 3,
WHICH IS NOW ASSIGNED TO PROCESSOR 2.
TASK 3 TAKES 9 HOURS, NOW TASK 3 IS IN PROGRESS.
NOTICE AFTER 9 HOURS TASK 3 IS COMPLETE, SO WE'LL PUT AN X
THROUGH TASK 3 SHOWING IT'S COMPLETE.
NOTICE ONCE TASK 3 IS COMPLETE, TASK 7 NOW BECOMES READY.
AND TASK 7 IS THE HIGHEST PRIORITY READY TASK
AND THEREFORE, IT'S ASSIGNED TO PROCESSOR 2.
TASK 7 TAKES 11 HOURS.
9 + 11 = 20.
TASK 7 IS NOW IN PROGRESS.
AFTER 10 HOURS TASK 4 IS COMPLETE, SO TASK 4
IS NOW COMPLETE.
NOTICE THERE ARE NO NEW READY TASKS AND THEREFORE,
THE NEXT READY TASK IS TASK 1, WHICH IS NOW ASSIGNED
TO PROCESSOR 1.
TASK 1 TAKES 8 HOURS, SO 10 + 8 = 18.
TASK 1 IS NOW IN PROGRESS.
AFTER 18 HOURS TASK 1 IS COMPLETE.
NOTICE THERE ARE NO NEW READY TASKS BECAUSE TASK 5
REQUIRES BOTH TASK 1 AND 2 TO BE COMPLETE.
THEREFORE, THE NEXT READY TASK IS TASK 2, WHICH IS NOW ASSIGNED
TO PROCESSOR 1.
TASK 2 TAKES 2 HOURS, SO 18 + 2 = 20.
TASK 2 IS IN PROGRESS.
NOTICE AT 20 HOURS TASK 2 AND TASK 7 ARE COMPLETE.
SO TASK 2 IS COMPLETE AND TASK 7.
LET'S IDENTIFY THE NEW READY TASKS.
NOTICE, NOW TASK 5 IS READY AND SO IS TASK 6.
SO TASK 6AND TASK 5 ARE NOW READY.
THE HIGHEST PRIORITY READY TASK IS ASSIGNED TO PROCESSOR 1,
WHICH IS TASK 6.
TASK 6 TAKES 12 HOURS, SO 20 + 12 = 32.
TASK 6 IS NOW IN PROGRESS AND NOW TASK 5 IS ASSIGNED
TO PROCESSOR 2.
TASK 5 TAKES 7 HOURS, 20 + 7 = 27.
TASK 5 IS NOW IN PROGRESS.
AFTER 27 HOURS TASK 5 BECOMES COMPLETE.
NOW THAT TASK 5 IS COMPLETE, NOTICE TASK 9 IS NOW READY.
TASK 9 IS THE HIGHEST PRIORITY READY TASK AND THEREFORE,
IT'S ASSIGNED TO PROCESSOR 2.
TASK 9 TAKES 5 HOURS, SO HERE WE'RE AT 27.
27 + 5 = 32.
THIS WAS TASK 9, TASK 9 IS IN PROGRESS.
NOTICE AT 32 HOURS BOTH TASK 6 AND TASK 9
ARE COMPLETED.
SO TASK 6 IS COMPLETED AND SO IS TASK 9.
NOTICE NOW TASK 8 IS READY.
THEREFORE, TASK 8 IS ASSIGNED TO PROCESSOR 1.
TASK 8 TAKES 6 HOURS.
32 + 6 = 38.
TASK 8 IS IN PROGRESS.
NOTICE ONCE TASK 8 IS ASSIGNED THERE ARE NO READY TASKS
AND THEREFORE, PROCESSOR 2 CANNOT BE ASSIGNED A TASK
AFTER 2 HOURS.
IT ISN'T UNTIL TASK 8 IS COMPLETE, AFTER 38 HOURS,
WE HAVE ANOTHER READY TASK.
SO AT TIME 38 HOURS TASK 8 IS COMPLETE,
WHICH NOW MAKES TASK 10 READY.
PROCESSOR 1 IS THE FIRST AVAILABLE PROCESSOR
AND THEREFORE, TASK 10 IS ASSIGNED TO PROCESSER 1.
TASK 10 TAKES 3 HOURS, 38 + 3 = 41 HOURS.
AND NOW ALL TASKS HAVE BEEN ASSIGNED
AND THE SCHEDULE IS COMPLETE.
AGAIN, NOTICE AFTER 41 HOURS TASK 10 BECOMES COMPLETE.
AND THEREFORE, THE PROJECT IS NOW COMPLETE.
NOTICE HOW PROCESSOR 2 REMAINED IDLE FOR THE LAST 9 HOURS,
FROM 32 HOURS TO 41 HOURS.
AND HERE'S THE SAME SCHEDULE IN COLOR IF IT MAKES
IT EASIER TO READ.
AGAIN, THIS IS IDLE TIME.
THIS IS PROCESSOR 1 AND THIS PROCESSER 2.
NOW YOU MIGHT BE ASKING, DOES THE DECREASING
TIME ALGORITHM GIVE US A GOOD SCHEDULE?
TO GET SOME IDEA HOW GOOD OR BAD A SCHEDULE IS WE CAN COMPUTE
THE CRITICAL TIME, WHICH IS THE MINIMUM TIME
TO COMPLETE THE JOB.
TO FIND THIS, WE LOOK FOR THE SEQUENCE OF TASKS
WITH THE HIGHEST TOTAL COMPLETION TIME.
SO FOR EXAMPLE, IF WE FOLLOW THIS SEQUENCE HERE TASK 1,
5, 9 TO THE END.
THE TOTAL TIME WOULD BE 8 + 7 + 5 = 20 HOURS.
THE CRITICAL TIME WOULD BE THE PATH
WITH THE LONGEST TOTAL COMPLETION TIME.
SO WE COULD ALSO TAKE THIS PATH HERE, TASK 1, 5, 10
TO THE END, WHICH WOULD BE 8 + 7 + 3 = 18 HOURS
OR WE COULD TAKE THIS PATH, TASK 2, 5, 10 TO THE END.
THAT WOULD BE 2 + 7 + 3 = 12 HOURS OR TASK 2, TASK 6,
TASK 8, TASK 10 TO THE END, WHICH IS 2 + 12 + 6 + 3
= 23 HOURS OR TASK 3, TASK 7, TASK 8, TASK 10 TO THE END,
WHICH WOULD BE 9 + 11 + 6 + 3 = 29 HOURS.
THE LAST SEQUENCE WOULD BE JUST TASK 4,
WHICH IS ONLY 10 HOURS.
SO THE CRITICAL TIME IS 29 HOURS.
IF WE COMPARE THIS TO THE SCHEDULE OF 41 HOURS,
THIS MIGHT INDICATE THAT THERE IS A BETTER SCHEDULE.
AGAIN, NOTICE HOW PROCESSOR 2 WAS IDLE FOR 9 HOURS
IN THIS SCHEDULE.
I HOPE YOU FOUND THIS HELPFUL.