6.042J/18.062J 10. Partial Orders & Scheduling

2/26/10 1 Albert R Meyer, Feb. 26. 2010 Mathematics for Computer Science MIT 6.042J/18.062J Partial Orders & Scheduling 4F.1 Albert R Meyer, Feb. 26. 2010 18.01 → 6.042 18.01 → 18.02 18.01 → 18.03 6.001 → 6.034 6.042 → 6.046 8.02 → 6.002 18.03, 6.002 → 6.004 6.001, 6.004 → 6.033 6.033 → 6.857 6.046 → 6.840 4F.2 Some Course 6 Prerequisites Albert R Meyer, Feb. 26. 2010 subjects with no prereq’s “d is a Freshman subject” < nothing> → d 4F.4 18.01 6.001 8.02 Albert R Meyer, Feb. 26. 2010 d is minimal: nothing else is smaller minimal elements ∀c ≠ d. NOT(cRd) 4F.5 Albert R Meyer, Feb. 26. 2010 d is minimal: nothing else is smaller Minimal elements d is minimum: smaller than everything else ∀c ≠ d. NOT(c ≤ d) 4F.7 Albert R Meyer, Feb. 26. 2010 18.01 → 6.042 18.01 → 18.02 18.01 → 18.03 6.001 → 6.034 6.042 → 6.046 Constructing a Term Schedule 8.02 → 6.002 18.03, 6.002 → 6.004 6.001, 6.004 → 6.033 6.033 → 6.857 6.046 → 6.840 identify minimal elements 4F.8 2/26/10 2 Albert R Meyer, Feb. 26. 2010 18.01 6.001 8.02 Constructing a Term Schedule start schedule with them 4F.9 Albert R Meyer, Feb. 26. 2010 remove minimal elements Constructing a Term Schedule 18.01 􀀁 6.042 18.01 􀀁 18.02 18.01 􀀁 18.03 6.001 􀀁 6.034 6.042 􀀁 6.046 8.02 􀀁 6.002 18.03, 6.002 􀀁 6.004 6.001, 6.004 􀀁 6.033 6.046 􀀁 6.8404F.10 Albert R Meyer, Feb. 26. 2010 remove minimal elements Constructing a Term Schedule 􀀁 6.042 􀀁 18.02 􀀁 18.03 􀀁 6.034 6.042 􀀁 6.046 􀀁 6.002 18.03, 6.002 􀀁 6.004 6.004 􀀁 6.033 6.033 􀀁 6.857 6.046 􀀁 6.8404F.11 Albert R Meyer, Feb. 26. 2010 Constructing a Term Schedule 􀀁 6.042 􀀁 18.02 􀀁 18.03 􀀁 6.034 6.042 􀀁 6.046 􀀁 6.002 18.03, 6.002 􀀁 6.004 6.004 􀀁 6.033 6.033 􀀁 6.857 6.046 􀀁 6.8404F.12 identify new minimal elements 6.042 6.034 18.02 18.03 6.002 6 004 Albert R Meyer, Feb. 26. 2010 18.02 18.01 18.03 6.001 6.034 8.02 6.002 6.042 Constructing a Term Schedule schedule them next 4F.13 Albert R Meyer, Feb. 26. 2010 6.046 6.004 Constructing a Term Schedule continue in this way… 4F.14 18.02 18.01 18.03 6.001 6.034 8.02 6.002 6.0422/26/10 3 Albert R Meyer, Feb. 26. 2010 complete term schedule 4F.15 18.02 18.01 6.046 6.840 18.03 6.001 6.034 8.02 6.002 6.004 6.033 6.857 6.042 Albert R Meyer, Feb. 26. 2010 an antichain Set of subjects with no prereqs among them: so can be taken in any order. (said to be incomparable) 4F.16 Albert R Meyer, Feb. 26. 2010 some antichains 18.02 18.01 6.046 6.840 18.03 6.001 6.034 8.02 6.002 6.004 6.033 6.857 6.042 many more… 4F.17 Albert R Meyer, Feb. 26. 2010 a chain Set of successive prereqs: must be taken in order. (subjects are comparable) 4F.18 Albert R Meyer, Feb. 26. 2010 some chains 4F.19 18.02 18.01 6.046 6.840 18.03 6.001 6.034 8.02 6.002 6.004 6.033 6.857 6.042 Albert R Meyer, Feb. 26. 2010 maximum length chain 4F.20 18.02 18.01 6.046 6.840 18.03 6.001 6.034 8.02 6.002 6.004 6.033 6.857 6.0422/26/10 4 Albert R Meyer, Feb. 26. 2010 how many terms to graduate? 5 terms are necessary to graduate --because max chain length is 5 and 5 are sufficient --if you can take unlimited subjects per term... Albert R Meyer, Feb. 26. 2010 …sufficient 4F.22 18.02 18.01 6.046 6.840 18.03 6.001 6.034 8.02 6.002 6.004 6.033 6.857 6.042 Albert R Meyer, Feb. 26. 2010 parallel processing time min parallel time max term load: # processors for min time max antichain size 5 in this case min # terms to graduate: = max chain size& 4F.23 Albert R Meyer, Feb. 26. 2010 18.02 reduce the term load 4F.24 18.02 18.01 6.046 6.840 18.03 6.001 6.034 8.02 6.002 6.004 6.033 6.857 6.042 Albert R Meyer, Feb. 26. 2010 18.02 reduce the term load 4F.25 18.01 6.046 6.840 18.03 6.001 6.034 8.02 6.002 6.004 6.033 6.857 6.042 max 4 subjects per term Albert R Meyer, Feb. 26. 2010 6.046 18.01 8.02 6.001 3 Subjects per Term Possible 6.840 18.03 6.002 6.004 6.033 6.042 6.857 4F.26 6.034 18.022/26/10 5 Albert R Meyer, Feb. 26. 2010 a leisurely schedule Graduate taking only 1 subject/term? Sure, 18.01 8.02 6.001 18.02 18.03 6.034 6.002 6.004 6.042 a topological sort 4F.27 6.046 6.840 6.033 6.857 Albert R Meyer, Feb. 26. 2010 For min time: 3-subject term 13 subjects max chain size = 5 so load of some term must be4F.29 13/5 = 3 Albert R Meyer, Feb. 26. 2010 Dilworth’s Lemma Prereq’s among n subjects has •a chain of size > t •or antichain of size for all 1 t n. 4F.30 Albert R Meyer, Feb. 26. 2010 Height/Birthday Partial Order Two students are related to each other iff one is shorter and younger than the other. (s1, a1) (s2, a2) iff (s1 s2) and (a1 a2) (the product p.o.) 4F.31 Albert R Meyer, Feb. 26. 2010 Dilworth Demo older (a -antichain) 4F.32 Albert R Meyer, Feb. 26. 2010 Team Problems Problems 13 4F.33 Image by MIT OpenCourseWare.MIT OpenCourseWare http://ocw.mit.edu 6.042J /18.062J Mathematics for Computer Science Spring 2010 For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.