Idea of Deterministic Rounding

Model the problem as an Integer Programming formulation.
Relax the model to a Linear Programs.
Solve the LP in polynomial-time to obtain a fractional solution.
Round the fractional solution to an integer one.

Minimum Completion Time Scheduling on a Single Machine

Problem Setting

Given:

a set of $n$ jobs
a processing time $p_j\in\mathbb Z_{>0}$ and a release time $r_j\in\mathbb Z_{\geq0}$ for each job $j\in[n]$.
one machine

Assumptions:

Completion time of a job $j$ is $C_j$: time when $j$ complete its processing
The machine can schedule at most one job at a time
If a machine begins to process a job, it must process it until its completion (no preemption)

Goal: Schedule all the jobs minimizing the sum of completion times $$ \sum_{j=1}^nC_j. $$

Relaxation to Preemptive Scheduling

We relax the problem to its preemptive version

We can interrupt the execution of one job
We remove the constraint "If a machine begins to process a job, it must process it until its completion"

The preemptive version is not $\mathsf{NP}$-hard. We can solve it by the Shortest Remaining Processing Time (SRPT) in polynomial time

At any point in time, process an available and uncompleted job with shortest remaining processing time
SRPT finds an optimal preemptive schedule in time $O(n\log n)$ (by exchange argument)

Let $OPT$ be the optimal value of the non-preemptive problem, $C_j^P$ be the completion time of a job $j$ in an optimal solution for the preemptive problem (given by SRPT), obviously, $$ \sum_{j=1}^nC_jP\leq OPT. $$

Rounding the Preemptive Problem

Compute an optimal preemptive schedule with job completion times $C_j^P$ by SRPT

Sort jobs in a way that $C_1^P<C_2^P<\cdots<C_n^P$ // Schedule all jobs as early as possible in this order in a non-preemptive way.

$C_1^N=r_1+p_1$

Schedule job $1$ from $r_1$ to $C_1^N$

For each $j=2\to n$ do

$C_j^N=\max\{C_{j-1}^N,r_j\}+p_j$
Schedule job $j$ from $\max\{C_{j-1}^N,r_j\}$ to $C_j^N$

Lemma: For each job $j\in[n],C_j^N\leq 2C_j^P$.

Three lower bounds:

$C_j^P\geq\max_{k\in[j]}r_k$

$C_j^P\geq\sum_{k\in[j]}p_k$

$C_j^N\geq\max_{k\in[j]}r_k$

In the non-preemptive schedule, the machine can be idle only if the next job to be processed has not been released yet.

Then, it cannot be idle in the interval between $\max_{k\in[j]}r_k$ and $C_j^N$. Therefore, $$ C_j^N-\max_{k\in[j]}\leq\sum_{k\in[j]}p_k\Rightarrow C_j^{N\leq\max_{k\in[j]}r_k+\sum_{k\in[j]}p_k\leq2C_j}P. $$ Q.E.D.

Theorem: The rounding algorithm is a $2$-approximation algorithm for the minimum completion time scheduling on a single machine.

To sum up inequalities over $j$.

Minimum Weighted Completion Time Scheduling on a Single Machine

Problem Setting

Given:

a set of $n$ jobs
a processing time $p_j\in\mathbb Z_{>0}$ and a release time $r_j\in\mathbb Z_{\geq0}$ for each job $j\in[n]$
a weight $w_j$ for each job $j$
one machine

Assumptions:

Completion time of a job $j$ is $C_j$
The machine can schedule at most one job at a time
No preemption.

Goal: Schedule all the jobs minimizing the sum of completion time $$ \sum_{j\in[n]}w_jC_j. $$

Problem Analysis

The weighted version of the preemptive problem is $\mathsf{NP}$-hard.

We cannot use the relaxation in unweighted version.

In the correctness proof of approximation algorithm for the unweighted version, we used only three inequalities.

We give a LP relaxation with variables $C_j$ satisfying the three inequalities with in a constant factor.

Linear Programming Relaxation

Variables $C_j$ is the completion time for job $j\in[n]$.

Objective function: $\sum_{j\in[n]}w_jC_j$

Constraints:

$C_j\geq r_j+p_j$: a job cannot complete before it is released and processed
For each set $S\subseteq[n]$, consider the sum $\sum_{j\in S}p_jC_j$. It is minimized if each job in $S$ is released at time $0$ and completes before the jobs not in $S$.
Assume that this two conditions hold, then for $j\in S$, $C_j$ is equal to $p_j$ plus all the jobs that precede it.
In the product $p_jC_j$, $p_j\times$ it self and all the jobs that precede it,

\[ \sum_{j\in S}p_jC_j=\sum_{j,k\in S:j\leq k}p_jp_k=\frac{1}{2}(\sum_{j\in S}p_j)^2+\frac{1}{2}\sum_{j\in S}p_j^2\geq\frac{1}{2}(\sum_{j\in S}p_j)^2. \]

Let $p(S)=\sum_{j\in S}p_j$, $$ \sum_{j\in S}p_jC_j\geq\frac{1}{2}p(S)^2. $$ The LP format: $$ \min\sum_{j=1}^nw_jC_j $$ s.t. $$ C_j\geq r_j+p_j\forall j\in [n]\land\sum_{j\in S}p_jC_j\geq\frac{1}{2}p(S)^2\forall S\subseteq[n] $$ It is a relaxation because any solution for the original problem is feasible for this formulation.

Note that there are an exponential number of constraint of the second type. We can solve it in polynomial time.

Rounding Algorithm

Compute an optimal solution to the LP relaxation $C^*$

Sort jobs in a way that $C_1^*<C_2^*<\cdots<C_n^*$ // Schedule all jobs as early as possible in this order in a non-preemptive way.

$C_1^N=r_1+p_1$, schedule job $1$ from $r_1$ to $C_1^N$

for each $j=2\to n$ do

$C_j^N=\max\{C_{j-1}^N,r_j\}+p_j$
Schedule job $j$ from $\max\{C_{j-1}^N,r_j\}$ to $C_j^N$

Theorem: The rounding algorithm is a $3$-approximation algorithm for the minimum weighted completion time scheduling on a single machine.

We show that $C_j^N\leq3C_j^*$ for each $j\in[n]$. Then, we have that $\sum_{j=1}^nw_jC_j^N\leq3\sum_{j=1}^nw_jC_j^*\leq3OPT$.

Let $r_\ell=\max_{k\in[j]}r_k$. As before, there cannot be idle times between $r_\ell$ and $C_j^N$, therefore $C_j^N-r_\ell\leq\sum_{k\in[j]}p_k$

By the ordering $C_j^*\geq\cdots\geq C_1^*:C_j^*\geq r_\ell$

By the LP constraint $C_\ell\geq r_\ell+p_\ell:C_\ell^*\geq r_\ell$

Therefore $C_j^*\geq r_\ell$

Claim: $C_j^*\geq\frac{1}{2}p([j])$, therefore, $$ C_j^N\leq r_\ell+p([j])\leq C_j^*+2C_j=3C_j^. $$ Q.E.D.

Claim: $C_j^*\geq\frac{1}{2}p([j])$

Let $S=[j]$. By the constraints we know that $$ \sum_{k\in S}p_kC_k^{*\geq\frac{1}{2}p(S)}2. $$ By ordering $C_j^*\geq\cdots\geq C_1^*$ and then $$ C_j^\sum_{k\in S}p_k=C_j^p(S)\geq\sum_{k\in S}p_kC_k^*. $$ Combining the two inequalities, we get the claim.

The LP used in the previous algorithm has an exponential number of constraints.

Separation Oracle

A separation oracle takes as input a solution $x$ to a linear program

either outputs that the solution is feasible
or if points out a violated constraints

Given a polynomial-time separation oracle, the ellipsoid method solves a linear program in a time that is polynomial in the number of variables and in the number of bits needed to encode a constraint.