Modulcode:	infSPAC-01a
Englische Bezeichnung:	Scheduling Problems: Algorithms and Complexity
Modulverantwortliche(r):	Prof. Dr. Klaus Jansen
Turnus:	unregelmäßig (WS22/23)
Präsenzzeiten:	2V 2Ü
ECTS:	6
Workload:	30 Std. Vorlesung, 30 Std. Präsenzübung, 150 Std. Selbststudium
Dauer:	ein Semester
Modulkategorien:	BSc-Inf-WP (BSc Inf (21)) MSc-Inf-Theo (MSc Inf (21)) MSc-Inf-WP (MSc Inf (21)) 2F-MEd-Inf-WP (MEd-Hdl Inf (21)) 2F-MA-Inf-WP (2F-MA Inf (21)) MSc-WInf-WP-Inf (MSc WInf (21))
Lehrsprache:	Englisch
Voraussetzungen:

Kurzfassung:

Scheduling involves the timely allocation of tasks to scarce resources with the objective to minimize some cost function. Such problems appear in various applications, e.g., in production planning, logistics, project management, or operating computing systems. This basic lecture will cover: a classification of scheduling models, complexity of scheduling problems, and the design and analysis of exact and approximation algorithms for single and parallel machine scheduling.

Lernziele:

The students can

model scheduling problems, design algorithms and prove complexity results, and analyze scheduling problems.

Lehrinhalte:

Introduction 3 field notation, EDD schedules for lateness, basic complexity results for average weighted number of late jobs, and scheduling on parallel machines.

Smith rule for average weighted completion times, hardness for average weighted completion times with release dates. hierarchy with different objective functions, algorithm by Moore and Hodgson and Cheriyan et al. for number of late jobs. algorithm for weighted number of late jobs with unit-times via matroids.

algorithms for maximum delivery time with release times for jobs: hardness, Jackson's rule, list scheduling, 2-approximation, polynomial time approximation scheme (PTAS), and efficient polynomial time approximation scheme (EPTAS).

hardness for average weighted completion time with release dates, algorithms for average weighted completion times: SRPT for preemptive variant, 2-approximation, algorithms via EDD rule for on-time jobs and DP method via knapsack,FPTAS.

algorithms for average completion times (with release dates): online 2-approximation, e/(e-1) randomized algorithm via alpha points, PTAS.

Weitere Voraussetzungen:

Introduction to Algorithms, Mathematics A and B, or equivalent courses.

Prüfungsleistung:

Final exam at the end of the semester.

In order to be accepted for the exam you will have to show by the given deadlines your supervisor your successful individual work on all theoretical exercise series (except two).

Depending on the number of students, the exam will be either oral or written. As an alternative to the exam, we also offer students to work on a research task instead. This involves working on some topic of current research, writing a report and presenting the results to the other students.

Lehr- und Lernmethoden:

Verwendbarkeit:

Literatur:

Jan Karel Lenstra and David B. Shmoys: Elements of Scheduling, arXiv:2001.06005.

Leslie Hall: Approximation Algorithms for Scheduling, Chapter 1, in: D. Hochbaum. Approximation algorithms for NP-hard problems, PWS Publishing Company.

Michael Pinedo: Scheduling Theory, Algorithms and Systems, Prentice Hall.

Florian Jaehn and Erwin Pesch: Ablaufplanung Einführung in Scheduling, Springer.

Verweise:

Kommentar: