Scheduling:  The List Processing Algorithm Part 1

Scheduling: The List Processing Algorithm Part 1

Articles, Blog , , , , , , , , , , , , , , , , , , 7 Comments


– 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.  

7 thoughts on “Scheduling: The List Processing Algorithm Part 1

Leave a Reply

Your email address will not be published. Required fields are marked *