Scheduling Tasks on One Machine

You have $n$ tasks, and must find an order in which to execute them with minimum cost. Task $i$ takes time $t_i$, and making task $i$ wait for $t$ time units incurs cost $f_i(t)$.

Formally, given $n$ functions $f_i$ and $n$ numbers $t_i$, find a permutation $p$ minimizing

Special Cost Functions

Linear Cost Functions

First, consider the case where all functions are linear, namely $f_i(x)=c_ix+d_i$, where $c_i$ is a nonnegative integer. Clearly, we can add all constant terms in advance, so the functions reduce to the form $f_i(x)=c_ix$.

Consider two permutations $p$ and $p'$, where $p'$ is obtained by swapping the numbers at positions $i$ and $i+1$ in $p$. Then

Therefore, we can sort by repeatedly swapping whenever $c_{p_i}t_{p_{i+1}}-c_{p_{i+1}}t_{p_i}>0$. Written as $\dfrac{c_{p_i}}{t_{p_i}}>\dfrac{c_{p_{i+1}}}{t_{p_{i+1}}}$, this means sorting the permutation in ascending order of $\dfrac{c_i}{t_i}$.

Our approach is to consider the effect of a local perturbation and greedily choose the optimal solution.

Exponential Cost Functions

Consider cost functions of the form $f_i(x)=c_i\mathrm{e}^{ax}$, where $c_i\ge 0,a>0$.

Following the previous approach, consider the change in cost caused by swapping the numbers at positions $i$ and $i+1$. The resulting algorithm is to sort the permutation in ascending order of $\dfrac{1-\mathrm{e}^{at_i}}{c_i}$.

The Same Increasing Function

Suppose all $f_i(x)$ are the same increasing function. Then it is clear that we should sort the permutation in ascending order of $t_i$.

Livshits–Kladov Theorem

The Livshits–Kladov theorem holds if and only if the cost functions fall into one of the following three cases:

• Linear functions: $f_i(t) = c_it + d_i$, where $c_i\ge 0$;
• Exponential functions: $f_i(t) = c_i \mathrm{e}^{a t} + d_i$, where $c_i,a>0$;
• The same increasing function: $f_i(t) = \phi(t)$, where $\phi(t)$ is an increasing function.

The theorem is proved under the assumption that the cost functions are sufficiently smooth (their third derivatives exist). In all three cases, the optimal solution can be found by simple sorting in $O(n\log n)$ time.

This page is mainly translated from the blog post Задача Джонсона с одним станком and its English version Scheduling jobs on one machine. The Russian version is licensed under Public Domain + Leave a Link; the English version is licensed under CC-BY-SA 4.0.