- WELCOME TO A LESSON ON THE LIST PROCESSING
ALGORITHM FOR SCHEDULING.
IN THE INTRODUCTION LESSON, WE LOOKED
AT COMPLETED SCHEDULES.
SMALL SCHEDULES CAN BE EQUATED USING GUESS AND CHECK,
BUT WOULD NOT WORK WELL WITH DOZENS OR HUNDREDS OF TASKS.
TO CREATE A MORE PROCEDURAL APPROACH, WE MIGHT BEGIN
WITH A PRIORITY LIST.
ONCE WE HAVE OUR PRIORITY LIST, WE CAN BEGIN SCHEDULING
USING THE PRIORITY LIST AND THE LIST PROCESSING
ALGORITHM WHERE OUR PRIORITY LIST IS A LIST OF TASKS
GIVEN IN ORDER IN WHICH WE DESIRE THEM TO BE COMPLETED.
THE LIST PROCESSING ALGORITHM TURNS OUR PRIORITY LIST
INTO A SCHEDULE.
AND HERE ARE THE STEPS FOR THE LIST PROCESSING ALGORITHM.
STEP 1, ON THE DIAGRAM OR PRIORITY LIST,
CIRCLE ALL TASKS THAT ARE READY, MEANING THAT ALL PREREQUISITE
TASKS HAVE BEEN COMPLETED.
STEP 2, ASSIGN EACH AVAILABLE PROCESSOR IN ORDER
THE FIRST READY TASK.
MARK THE TASK AS IN PROGRESS, PERHAPS BY PUTTING A SINGLE LINE
THROUGH THE TASK.
STEP 3, MOVE FORWARD IN TIME UNTIL A TASK IS COMPLETED.
MARK THE TASK AS COMPLETE, PERHAPS BY CROSSING
OUT THE TASK.
IF ANY NEW TASKS BECOME READY, MARK THEM AS SUCH.
STEP 4, REPEAT UNTIL ALL TASKS HAVE BEEN SCHEDULED.
SO HERE WE'RE GIVEN A PRIORITY LIST AND ASKED
TO MAKE A SCHEDULE USING 2 PROCESSORS.
SO WE'LL CALL THIS FIRST ROW PROCESSOR 1 AND THE SECOND ROW
PROCESSOR 2.
WE BEGIN BY CIRCLING THE READY TASK.
LOOKING AT THE DIAGRAPH, NOTICE HOW WE HAVE THE TASKS
AND IN PARENTHESES WE'LL LET THE TIME IT TAKES TO COMPLETE
THE TASK BE HOURS.
SO WE BEGIN BY CIRCLING THE READY TASKS
WHICH WOULD BE TASKS 1, 2, 3 AND 4,
BECAUSE THERE ARE NO PREREQUISITE TASKS
FOR THESE TASKS, SO WE'LL MARK THEM AS READY.
LET'S ALSO MARK THEM READY ON OUR PRIORITY LIST.
SO HERE'S TASKS 2, 3, 1 AND 4.
NOTICE TASKS 2 AND 3 HAVE THE HIGHEST PRIORITY.
THEY'LL BE THE FIRST 2 TASKS ASSIGNED TO PROCESSOR 1
AND PROCESSOR 2.
SO WE'LL BEGIN BY ASSIGNING TASK 2 TO PROCESSOR 1.
NOTICE TASK 2 TAKES 6 HOURS.
SO NOW TASK 2 IS IN PROGRESS, SO WE'LL PUT A LINE
THROUGH TASK 2.
AND NOW, WE'LL ASSIGN TASK 3 TO PROCESSOR 2.
NOTICE TASK 3 TAKES 11 HOURS.
AND NOW, WE'LL MARK TASK 3 AS IN PROGRESS.
NOTICE AFTER 6 HOURS, TASK 2 IS COMPLETE.
SO WE'LL MARK TASK 2 AS COMPLETE WITH AN X.
NOTICE THAT NOW TASK 6 BECOMES AVAILABLE OR READY,
BECAUSE TASK 2 IS COMPLETE.
BUT NOTICE HOW TASK 5 IS NOT READY YET,
BECAUSE IT'S STILL WAITING FOR TASK 1 TO BE COMPLETE.
SO WE'LL MARK TASK 6 AS NOW READY.
AND SINCE IT HAS THE HIGHEST PRIORITY ON THE LIST,
WE'LL NOW ASSIGN TASK 6 TO PROCESSOR 1.
TASK 6 TAKES 7 HOURS, 6 + 7 = 13 HERE, SO TASK 6
IS NOW IN PROGRESS.
NOTICE AFTER 11 HOURS, TASK 3 IS COMPLETE,
SO WE'LL MARK TASK 3 AS COMPLETE, JUST HERE, HERE.
AND NOW, NOTICE TASK 7 IS READY.
TASK 7 IS THE HIGHEST PRIORITY READY TASK WHICH IS NOW ASSIGNED
TO PROCESSOR 2.
NOTICE TASK 7 TAKES 4 HOURS, 11 + 4 = 15, AND NOW TASK 7
IS IN PROGRESS.
NOTICE AFTER 13 HOURS, TASK 6 IS COMPLETE.
HERE'S TASK 6, SO NOW IT'S COMPLETE.
NOTICE HOW THIS MAKES TASK 8 READY.
THE HIGHEST PRIORITY READY TASK IS NOW TASK 1 WHICH WE'LL ASSIGN
TO PROCESSOR 1.
NOTICE TASK 1 TAKES 12 HOURS.
SO WE HAVE 13 + 12 = 25, AND TASK 1 IS IN PROGRESS.
AFTER 15 HOURS, TASK 7 IS COMPLETE.
HERE'S TASK 7.
THE HIGHEST PRIORITY OF READY TASK IS TASK 8
WHICH WILL NOW BE ASSIGNED TO PROCESSOR 2.
TASK 8 TAKES 5 HOURS, SO 15 + 5 = 20.
TASK 8 IS NOW IN PROGRESS.
AFTER 20 HOURS, TASK 8 IS COMPLETE.
MARK TASK 8 AS COMPLETE.
NOTICE TASK 10 IS NOT READY.
IT'S WAITING FOR TASK 5.
THE ONLY READY TASK IS TASK 4 WHICH WILL NOW BE ASSIGNED
TO PROCESSOR 2.
TASK 4 TAKES 10 HOURS.
SO HERE WE'RE AT 20 + 10 = 30.
SO NOW THAT TASK 4 IS ASSIGNED TO PROCESSOR 2,
TASK 4 IS IN PROGRESS.
AFTER 25 HOURS, TASK 1 IS COMPLETE.
IF WE MARK TASK 1 AS COMPLETE, NOTICE HOW TASK 5
NOW BECOMES READY, THEREFORE TASK 5
IS ASSIGNED TO PROCESSOR 1.
TASK 5 TAKES 2 HOURS, 25 + 2 = 27.
TASK 5 IS IN PROGRESS.
NOTICE AT 27 HOURS, TASK 5 IS COMPLETE,
SO TASK 5 IS NOW COMPLETE.
NOTICE HOW THIS MAKES TASKS 9 AND 10 BOTH READY.
NOW, TASK 10 IS ASSIGNED TO PROCESSOR 1.
TASK 10 TAKES 8 HOURS, SO 27 + 8 = 35.
TASK 10 IS IN PROGRESS.
AT 30 HOURS, TASK 4 IS COMPLETE LEAVING TASK 9 TO BE ASSIGNED
TO PROCESSOR 2.
TASK 9 TAKES 9 HOURS, SO 30 + 9 TAKES US
TO THE END HERE OF 39 HOURS.
TASK 9 IS NOW IN PROGRESS.
NOTICE ALL THE TASKS HAVE BEEN ASSIGNED.
AT 35 HOURS, TASK 10 BECOMES COMPLETE,
AND AT 39 HOURS, TASK 9 BECOMES COMPLETE AND THE PROJECT
IS ALSO COMPLETE.
AND HERE'S THE SAME SCHEDULE IN COLOR.
WE'LL TAKE A LOOK AT A SECOND EXAMPLE
IN PART 2 WHERE WE ALSO CREATE THE DIAGRAPH.
I HOPE YOU FOUND THIS HELPFUL.