Język wykładowy 
Angielski 
Semestr 
Letni 
Status 
W ofercie 
Opiekun 
Łukasz Jeż

Liczba godzin 
30 (wyk.)
30 (ćw.)

Rodzaj 
I2.T  teoria inf. 
ECTS 
6

Polecany dla I roku 
No 
Egzamin 
Yes 
Opis przedmiotu:
There is a plethora of job scheduling problems, whose common denominator is that there is a given set of jobs (with various parameters) and a number of machines that they have to be scheduled on so that a certain objective function is optimized. The jobs have several parameters, such as processing times (or sizes), release times, weights that capture their importance, and, in some variants, deadlines.
A few examples were studied in the Algorithms and Data Structures course, but these were relatively simple. Most scheduling problems, particularly when more than one machine is available, are computationally hard, so we will typically consider approximation.
Sometimes we will restrict our attention to online algorithms, which seem particularly well suited to real life scheduling problems. In particular, we might study nonclairvoyant scheduling, where on top of not knowing the jobs that will arrive later in time, the scheduler does not know the size (processing time) of each available job until it is processed till completion. We may or may not touch upon stochastic scheduling, where the actual size of a job is a random variable whose distribution is known.
We will survey fundamental scheduling problems. This means that we will consider:
* different objective functions, such as
* maximum (weighted) completion time,
* average/total (weighted) completion time,
* maximum (weighted) flow time,
* average/total (weighted) flow time,
* maximum (weighted) tardiness,
* average/total (weighted) tardiness,
* (weighted) throughput
* maximum lateness / "feasibility"
* total energy consumption
* different machine setups:
* single machine
* identical machines (notice that their number may or may not be part of the input, which may affect computational complexity)
* related machines (i.e., machines of different speeds)
* unrelated machines (think different processor architectures, suitable to particular tasks: in general, each job specifies how much time it would take to complete it on each of the machines
* different notions of preemption:
* in nonpreemptive scheduling, a job that is being processed has to be run until completion
* in preemptive scheduling, the job can be stopped and resumed at any later time (there is also a variant ``with restarts'', only relevant in the online setting, where the renewed processing has to start from scratch); one may still distinguish between
* nonmigratory scheduling, where the job can be resumed only on the one machine it was assigned to before
* migratory scheduling, where the job can be resumed at any of the available machines
The list goes on, and one might impose various constraints on job parameters, so clearly there is a huge number of problems. To get a grip on them, we will also learn the basics of the fourfield scheduling notation, and realize it is actually useful sometimes (see _scheduling zoo_ in the Literature)
**Some important points**
1. In case of interest, we might devote part of the curriculum to major open problems in the field.
2. This would be the very first edition of the course, so expect some glitches and possibly parttime seminar form, especially if there is interest in that.
3. The course can be taught in either English or Polish, though I have a preference for the former  the literature is mostly available in English only; in particular, coming up with Polish terminology (even for aforementioned objective functions) might prove difficult.
### Prerequisites
You should be comfortable with designing algorithms for combinatorial optimization problems, proving their correctness, and analyzing complexity. Some elementary knowledge of calculus, NPhardness, approximation algorithms (incl. linear programming), online algorithms, and probability theory is required.
It is thus advised  but not necessary if you are motivated to learn the basics on your own  that you have completed each of the following courses:
* Discrete Mathematics
* Algorithms and Data Structures
* Formal Languages and Computational Complexity
* Approximation Algorithms
* Online Algorithms
### Literature
The core of our literature will be a number of seminal articles, which I will not list here. I should point out though that:
1. http://schedulingzoo.lip6.fr/ is an excellent search engine to determine the status of a scheduling problem, at least its offline complexity.
2. Some of the standard topics are covered in the textbooks on _online algorithms_ by Borodin and ElYaniv, on _approximation algorithms_ by Davidson and Schmoys, and, to a lesser extent, by Vazirani.
3. There is a number of handbooks of scheduling, which may or may not prove useful  these are typically overwhelming at close to a thousand pages, and the topic selection seems arbitrary