Scheduling theory

Summer semester 2021/2022 at the University of Wrocław. Link to the System Zapisów (sign up system) is here.

Lecture 1: Introduction to scheduling, scheduling notation. Polynomial-time algorithm for maximum throughput scheduling with unit jobs. Graham's algorithm for list scheduling and its (2-1/m)-approximation of the optimal makespan. Shortest remaining processing time applied to minimizing the completion times under preemption and release dates. Smith's rule for weighted completion time minimization without release dates. Lecture 1 handout.

Lecture 2: A bare minimum of definitions from complexity theory: NP-completeness, approximation algorithm. SRPT for preemptive sum of completion times on a single machine leads to a 2-approximation for non-preemptive sum of completion times. EDF is an optimal rule for minimizing max lateness on a single machine. Lawler's Least-Cost-Last algorithm for minimizing f_max on one machine with precedence constraints. Lecture 2 handout.

Lecture 3: Basic algorithms for the regime of multiple machines. LPT as a 4/3-approximation algorithm for minimizing the makespan on identical parallel machines. Definition of an approximation scheme (PTAS) and of an FPTAS. An approximation scheme for Pm||C_max. Algorithm Level for computing the optimal makespan for uniformly related machines with preemption. Lecture 3 handout.

Lecture 4: Dynamic programming approaches in scheduling. A pseudo-polynomial algorithm for 1||∑w_j U_j (minimizing the number of late jobs). An optimal O(n^7 m^5)-algorithm for minimizing the number of gaps for unit jobs with identical parallel machines.

Materials: Deeparnab Charkabarty's lecture notes for the first part, my notes of the dynamic program for the second part.

Lecture 5: Introduction to linear programming. Basic concepts, how to use it in approximation algorithm design. Some very basic examples. We also practiced formulating linear programs. Lecture 5 handout.

Lecture 6: LP introduction 2. Duality. A 3-approximation algorithm for Weighted sum of completion times with release dates using a smart LP formulation that requires a separation oracle. Lecture 6 handout.

Lecture 7: Two applications of LP rounding in scheduling: Minimizing makespan on unrelated machines via LP rounding (Lenstra, Shmoys, Tardos algorithm) and a simple randomized rounding scheme for throughput maximization (due to Im, Li, Moseley). Lecture 7 handout.

Lecture 8: Introduction to online optimization. Cow path and ski rental -- classical online problems. List scheduling on related machines. Lecture 8 handout.

Lecture 9: Online throughput maximization with equal-length jobs: introduction, 2-competitiveness in the deterministic case, a lower bound. Randomized online computation. Oblivious adversarial model. Lower bound of 3/4 for the randomized model via Yao's principle. Start of analysis of the barely-random 3/5-competitive algorithm of Chrobak, Jawor, Sgall, Tichy. Lecture 9 handout. First homework sheet released!

Lecture 10: Completing the proof of the barely-random algorithm RandLock. Lecture 10 handout, Lecture 10 notes.

Lecture 11: Online weighted completion time, scheduling by alpha-points in the non-preemptive case. Lecture 11 handout.

Lecture 12: The best-known online algorithm for list scheduling (minimizing makespan on identical machines). Lecture 12 handout.

Lecture 13: Semi-online objectives in scheduling; basic algorithm for online bin stretching. Lecture 13 handout. Second homework sheet released!

Lecture 14: Flow-time objectives in online scheduling, amortized local competitiveness (potential method). Source material: Shi Li, Benjamin Moseley, Kirk Pruhs: A Tutorial on Amortized Local Competitiveness in Online Scheduling.

Syllabus

Scheduling theory investigates the assignment of tasks to resources with the intent of minimizing some cost. A classical example is assigning jobs of various lengths to machines, so that the load of the machines is as balanced as possible, for example by minimizing the load of the busiest machine. Naturally, scheduling has a myriad of applications both inside and outside of computing, including logistics, operation management, worker allocation as well as scheduling CPU-bound tasks and scheduling virtual machines in a cloud environment.

This course focuses on scheduling theory as a branch of theoretical computer science, and our main goal is to design optimal algorithms – or, if not optimal, then at least provably efficient ones.

Throughout the course, we shall introduce the main algorithmic tools used for in the area of scheduling theory, and present select major results in the area which use these tools. In particular, we will focus on optimal polynomial-time algorithms for scheduling problems, approximation algorithms, and online algorithms.

Sample topics:

• Introduction to scheduling theory, overview of the area, Graham notation.

• List scheduling, online list scheduling. List scheduling on machines with different speeds.

• Dynamic programming and its applications in scheduling.

• Preemptive list scheduling minimizing the sum of weighted completion times.

• Scheduling on unrelated parallel machines.

• Online throughput scheduling of unit and equal-size jobs.

• Semi-online scheduling: known optimum makespan, known sum of processing times.

The course is aimed at Master-level students of computer science, but advanced Bachelor-level students with interest in algorithm design are also welcome. Knowledge of basic algorithms and data structures is required. Basic familiarity with the theory of online computation and the theory of linear optimization will be useful at later stages of the course, but is not mandatory.

The exercise sessions will consist of problem solving practice in class, and grades for the exercise sessions will be determined by two larger homework sheets throughout the semester. An oral exam on the topics of the lecture will determine the final grade.

The course will be taught completely in English.