236605 is a graduate course given at the Technion's Computer Science Department. The topics studied vary from year to year. The Y2K Spring Semester course presents scheduling algorithms.
Prerequisites: computability theory (236343).
The course will discuss the design and analysis of algorithms for scheduling problems. The emphasis is on algorithms whose performance can be analysed rigorously. The lectures are organized to highlight algorithmic methods and their application to a wide variety of scheduling problems.
Teaching Staff:
Lecturers:
Prof. Allan Borodin and
Dr. Yuval Rabani
Teaching assistant: Mr. Moni Shahar
Prof. Borodin is visiting us from the University of Toronto. He will teach about one third of the classes. His lectures will be in English.
Meets on: Thursdays, 14:30-17:30, Taub 4.
Course requirements: The final grade will be based on evaluation of homework assignments solutions (70%), and scribe notes (30%). You will get further instructions on both. We require students to read and understand, by mid-semester, the linear programming notes that we will hand out in class. These can also be downloaded, see below.
Lecture 1: Introduction. Motivation, examples, notation,
optimization, P vs. NP, approximability, on-line vs. off-line,
course outline.
Handouts:
administrivia,
assignment 1.
Recommended reading: KSW 1, 2.1.1-2.
Lecture 2: Greedy algorithms, EDD, SPRT, Johnson's rule,
least-cost-last, McNaughton's rule, Graham's LS rule.
Lecture
notes
(.tex,
figures:
lmax.tex,
ls.tex).
Recommended reading: KSW 2.1.3, 2.2, 2.3.1-2.
Lecture 3: LS for P|prec,r_j|C_max, Graham's LPT rule,
greedy and on-line algorithms, interval scheduling.
Lecture
notes
(.tex,
figures:
fig1.eps,
opt_lpt.eps,
another_greedy.eps).
Recommended reading: KSW 2.3.3-4.
Lecture 4: On-line algorithms for P||C_max, Q||C_max, and R||C_max,
on-line lower bounds, randomness.
Lecture
notes
(.tex).
Handouts:
assignment 2.
Recommended reading: BE 12.
Lecture 5: Polynomial time approximation schemes and dynamic
programming, 1|r_j|L_max.
Lecture
notes
(.tex).
Recommended reading: KSW 6.3.
Lecture 6: Polynomial time approximation schemes for
KNAPSACK, 1||sum w_j U_j, and P||C_max.
Lecture
notes
(.tex).
Recommended reading: Sahni (1975), Ibarra & Kim (1975),
KSW 6.1-2, Hochbaum & Shmoys (1987).
Lecture 7: Polynomial time approximation schemes for
P||sum M_i^2 and P||sum w_j C_j.
Lecture
notes
(.tex).
Handouts:
assignment 3.
recommended reading: Alon-Azar-Woeginger-Yadid (1998),
Skutella & Woeginger (1999).
Lecture 8: P||sum w_j C_j (continued), R||sum C_j.
Lecture
notes
(.tex,
figure:
l8fig1.eps).
recommended reading: Skutella & Woeginger (1999),
KSW 4.1.1.
Lecture 9: Using graph algorithms (matching, flows):
special cases of R||C_max, P|p_j=d_j-r_j|sum w_j Ubar_j,
O|pmtn|C_max; hardness results for R||C_max.
Lecture
notes
(.tex,
figures:
l9fig1.eps,
l9fig2.eps,
l9fig3.eps).
recommended reading: KSW 4.1, Arkin & Silverberg (1987)
Lenstra-Shmoys-Tardos (1990).
Lecture 10: R|pmtn|C_max, R||C_max
Lecture
notes
(.tex).
(unavailable yet)
recommended reading: KSW 4.2, Lawler & Labetoulle (1978),
Lenstra-Shmoys-Tardos (1990).
Lecture 11: 1|prec|sum w_j C_j, etc.
Lecture
notes
(.tex).
recommended reading: KSW 5.3, Hall-Schulz-Shmoys-Wein (1997).
Lecture 12: Primal-dual algorithms.
Lecture
notes
(.tex).
(unavailable yet)
Handouts:
assignment 4.
recommended reading: .
Lecture 13: Convex programming: R||sum w_j C_j.
Lecture
notes
(.tex).
recommended reading: Skutella (1999).
Linear programming notes
(postscript file, in Hebrew).
Scribe notes .sty header
file
Scheduling Algorithms,
a survey paper by Karger, Stein, and Wein.
Complexity Results for Scheduling Problems,
a site classifying the complexity of scheduling problems
by Brucker and Knust.
Polynomial time approximation algorithms
for machine scheduling: Ten open problems,
by Schuurman and Woeginger.
On-Line
Scheduling, a survey paper by Sgall.
Online Computation and Competitive Analysis, by Borodin and
El-Yaniv, Cambridge University Press, 1998.
Journal
of Scheduling, John Wiley & Sons, Inc.