# CMPUT272 Lecture Notes - Lecture 22: Critical Path Method, Linear Extension, Job Scheduler

35 views3 pages
4 Dec 2014
School
Course
Professor
Let R be a linear order on finite set A
What is |R|?
|R| = |A|!
----------------------------------------------
In a linear order, every pair of elements is related
a a
a, b are comparable.
O - O - O - .... - O
# of ordered pairs?
|(1, _)| = |A|
|(2, _)| = |A| - 1
...
Total number of ordered pairs: |R| = |A| + |A|-1 + |
A|-2 + ...
|A| |A|(|A|+1)
{p|p a|b
aRb = (a,b) b 175, 272
175 204
201 313, 304, 474
174, 175, 272, 291, 229, 201, 204, 313, 304, 474
174, 272, 175, 204, 474, 304, 201, 313, 229, 291
Job scheduling problem
To build a car
1) build frame
2) Install engine
3) install wheels
4) install dashboard
5) install electrical
Unlock document

This preview shows page 1 of the document.
Unlock all 3 pages and 3 million more documents.

## Get access

\$8 USD/m\$10 USD/m
Billed \$96 USD annually
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class