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 non-preemptive 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
* non-migratory 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 four-field 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 part-time 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, NP-hardness, 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 El-Yaniv, 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
