From this blog, we will talk about gready algorithm and local search in detail. And this blog will focus on the problem “scheduling jobs with deadlines on a single machine”.
Statement of Problem
- Given $n$ jobs and a machine able to process one job at a time
- Each job is associated with the following parameters:
- Process time: $p_j$
- Release date: $r_j$
- Due date: $d_j$
- If we complete processing job $j$ at time $C_j$ the lateness is: $L_j = C_j - d_j$
- Objective: minimize the maximum lateness: $L_{\text{max}} = \max_{j=1,\ldots,n} L_j$.
-
Only decide ${L_{max} \leq 0}$ is a NP hard Problem!!!
-
$\rho$-approximate algorithm: if $OPT = 0$ algorithm must find solution with objective $\rho \cdot 0 = 0$, implies $P=NP$. Hence, there doesn’t exist $\rho$-approximate algorithm unless $P=NP$.
- Hence, we have to consider the special case: assume all due dates $d_j$ are negative, implies optimal objective is positive.
Greedy Algorithm and analysis
Greedy algorithm: At any moment when the machine is free start some job among all available jobs.
Theorem: The greedy algorithm is a 2-approximation for the scheduling problem.
Proof.
-
Consider some optimal schedule and let maximum lateness: $L^*{\text{max}}$ and $C^*{\text{max}} = \max_j C^*_j$
-
As due dates $d_j$ are negative and $C^*_j$ are positive: \(L^*_{\text{max}} = \max_j(C^*_j - d_j) \geq \max_j C^*_j = C^*_{\text{max}}\)
-
Consider a schedule produced by greedy algorithm and let $L_{\text{max}}$ be maximum lateness and $C_{\text{max}} = \max_j C_j$.
- As algorithm is greedy and the machine never sit idle if a job is waiting (don’t have gap). That means $C_{\text{max}} \leq C^*_{\text{max}}$ (We process all the jobs on a single machine, the total process time is fixed, greedy algorithm doesn’t generate gap, which equals to total process time. So, ${C_\text{max} \leq C^*_{\text{max}}}$).
- Hence, we have
Hence, we get greedy algorithm is a 2-approximation for the scheduling problem. $\square$