CSCA67H3 Lecture : Week 1 - Scheduling.docx
4 Dec 2013
School
Department
Course
Professor
6
CSCA67H3 Full Course Notes
Verified Note
6 documents
Document Summary
Schedule the jobs so that the number of jobs scheduled is maximized and jobs do not overlap. J: the set of jobs ji: the ith job si: the start time of the ith job fi: the finish time of the ith job. Ordering: sort the jobs by increasing finish time. j3, j6, j1, j7, j4, j2, j5. Scheduling: schedule each job if there are no conflicts. j3, j7, j5. Proof if the algorithm is best - proof by contradiction: Show that our algorithm"s solution is as good as b by making b equivalent to our solution. Let s be the schedule our algorithm creates. S = (s1, s2, s3, , sn) B = (b1, b2, b3, , bm) (elements in s and b have all been arranged in order of increasing finish time) Because b is a better solution so it should be able to schedule more jobs than b.
