Skip to content

Scheduling Jobs on a Single Machine

You have \(n\) tasks, and you need to find an order to execute them with minimal cost. The \(i\)-th task takes time \(t_i\), and waiting for time \(t\) for the \(i\)-th task incurs a cost of \(f_i(t)\).

Formally, given \(n\) functions \(f_i\) and \(n\) numbers \(t_i\), find a permutation \(p\) that minimizes

\[ F(p)=\sum_{i=1}^nf_{p_i}\left(\sum_{j=1}^{i-1}t_{p_j}\right) \]

Special Cost Functions

Linear Cost Functions

First, consider the case where all functions are linear, i.e., \(f_i(x)=c_ix+d_i\), where \(c_i\) is a non-negative integer. Obviously, we can sum the 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 \(i\)-th and \((i+1)\)-th elements of \(p\). Then

\[ \begin{aligned} F(p')-F(p)&=c_{p'_i}\sum_{j=1}^{i-1}t_{p'_j}+c_{p'_{i+1}}\sum_{j=1}^{i}t_{p'_j} -\left(c_{p_i}\sum_{j=1}^{i-1}t_{p_j}+c_{p_{i+1}}\sum_{j=1}^{i}t_{p_j}\right)\\ &=c_{p_i}t_{p_{i+1}}-c_{p_{i+1}}t_{p_i} \end{aligned} \]

Thus, we can use the strategy of swapping if \(c_{p_i}t_{p_{i+1}}-c_{p_{i+1}}t_{p_i}>0\). Writing it as \(\dfrac{c_{p_i}}{t_{p_i}}>\dfrac{c_{p_{i+1}}}{t_{p_{i+1}}}\), it can be understood as sorting the permutation in ascending order of \(\dfrac{c_i}{t_i}\).

To handle this problem, our idea is to consider the changes after perturbation and greedily select 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\).

We follow the previous idea and consider the cost change caused by swapping the \(i\)-th and \((i+1)\)-th elements. The resulting algorithm sorts the permutation in ascending order of \(\dfrac{1-\mathrm{e}^{at_i}}{c_i}\).

Identical Monotonic Functions

Consider the case where all \(f_i(x)\) are the same monotonic function. Then obviously, we 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\);
  • Identical monotonic functions: \(f_i(t) = \phi(t)\), where \(\phi(t)\) is a monotonic function.

The theorem is proven under the assumption that the cost functions are sufficiently smooth (have third-order derivatives). In these three cases, the optimal solution to the problem can be obtained by simple sorting in \(O(n\log n)\) time.

This page is mainly translated from the blog post Задача Джонсона с одним станком and its English translation 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.

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用