Scheduling Problems

Scheduling in Linux

• $m$ machines: $\{M_1,...,M_m\}$ or $\{1,...,m\}$
• $n$ jobs: $\{J_1,...,J_n\}$ or $1,...,n$
• A job $j$ has processing time $p_{ij}$ when processing on machine $i$.

Non-preemptive jobs

the processing of a job must not be interrupted

Link to original

Preemptive jobs

The processing of a job may be interrupted and resumed later even on a different machine

Link to original

makespan

Link to original

sum of completion times

Link to original

Three field notation

Link to original

Min-Sum Scheduling
Unrelated Maschines
Minimizing the Makespan