# Scheduling: The List Processing Algorithm Part 1

– 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
MEANING THAT ALL PREREQUISITE TASKS HAVE BEEN COMPLETED. STEP 2, ASSIGN EACH AVAILABLE
PERHAPS BY PUTTING A SINGLE LINE THROUGH THE TASK. STEP 3, MOVE FORWARD IN TIME
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
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
1, 2, 3 AND 4, BECAUSE THERE ARE NO
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,
AS COMPLETE WITH AN X. NOTICE THAT NOW TASK 6
IS NOT READY YET, BECAUSE IT’S STILL WAITING
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,
AS COMPLETE, JUST HERE, HERE. AND NOW, NOTICE TASK 7 IS READY. TASK 7 IS THE HIGHEST PRIORITY
11 + 4=15, AND NOW TASK 7 IS IN PROGRESS. NOTICE AFTER 13 HOURS,
SO NOW IT’S COMPLETE.  NOTICE HOW
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,
TO PROCESSOR 2.  TASK 8 TAKES 5 HOURS,
SO 15 + 5=20. TASK 8 IS NOW IN PROGRESS. AFTER 20 HOURS,
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,
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,