Advanced Algorithms UE 8

by Maarten Behn
Group 5

Exercise 8.1 (Single-Machine scheduling with Release Dates) (7 Points)

Consider the preemptive single-machine scheduling problem $1|r_j,pmtn|\sum Cj$ , in which a set of jobs,
each with a processing time $p_j\ge 0$ and a release date $r_j\ge 0$ must be scheduled preemptively on a single machine with the objective to minimize the total completion time.
Show that the Shortest Remaining Processing Time (SRPT) rule is optimal.
SRPT schedules at any moment in time the job with the shortest remaining processing time.

Helper definition

Let $l_i(t)$ the processing time that is left at time $t$ for Job $i$.

Proof

Take a optimal solution $S^{\ast }$ that does not follow SRPT.
Let $t$ be the earliest time where $S^{\ast }$ deviates from SRPT.
At time $t$ let:

• $J_i$ the job that SRPT would process (shortest remaining processing time among released jobs)
• $J_j$ the job that is being processed in $S^{\ast }$, where $J_j\ne J_i$
• $r_i,r_j\le t$
• $l_i(t)\le l_j(t)$

Construct a new schedule $S^{\prime }$ by modifying $S^{\ast }$ as follows:

• Let $\delta \ge 0$ be a small time span.
• Pause $J_j$ and process $J_i$ in $[t,t+\delta ]$ then continue with $J_j$.
  $\delta$ is small enough that no other job is released during $[t,t+\delta ]$, and that neither $J_i$ nor $J_j$ finishes in that time.

Let $C_i^{\ast }$ be the completion time of $J_i$ in $S^{\ast }$
Let $C_j^{\ast }$ be the completion time of $J_j$ in $S^{\ast }$
then
$C_i^{\prime }=C_i^{\ast }-\delta$
$C_j^{\prime }=C_j^{\ast }+\delta$

$\Delta =(C_i^{\prime }+C_j^{\prime })-(C_i^{\ast }+C_j^{\ast })=(-\delta +\delta )=0$

Thus, the total completion time remains unchanged.
However, we have made the schedule more SRPT-like without making the objective worse.

By repeating this local exchange at every deviation from SRPT we can transform $S^{\ast }$ into a schedule that exactly follows SRPT, without increasing $\sum C_j$​ at any point.
Therefore, SRPT must also be optimal.

Exercise 8.2 (Makespan Scheduling via LP) (7 Points)

We have seen in class that the scheduling problems $P|pmtn|C_{max}$ and $P|pmtn,r_j|C_{max}$ can be solved optimally in polynomial time.
Recall that in these problems, we are given a set of jobs $J$, each with processing time $p_j\ge 0$ and possibly a release date $r_j\ge 0$,
and $m$ identical parallel machines to execute these jobs.
The task is to find a feasible schedule, possibly using preemption, such that the makespan is minimized.

Show how to solve the problem with release dates using linear programming (LP).

Hint: Formulate the subproblem of assigning a feasible amount of jobs’ processing to time intervals via an LP, given that you knew the optimal makespan.

LP for $P|pmtn,r_j|C_{max}$

Let $T\ge 0$ be the processing time of a minimal makespan.
Let $T_p$ be a time span such that

• $\exists k\in \mathbb{N}T=T_p\cdot k$ ($T$ can be split into $k$ time spans $T_p$)
• $\forall j\in \{1,...,n\}\exists l_j\in \mathbb{N}{r}_j=T_p\cdot l_j$ (And every release time sits at the start of one of these time spans)
  Let $t=0,...,k-1$ (The index of the time span of length $T_p$)

Variables

$x_{j,t}\in [0,1]$ the amount a job $j$ is processed in time span $t$

Goal

Find a valid distribution of $x_{j,t}$

Constraints

Every Job gets processed fully:
$\sum _{t=l_j}^n{x}_{j,t}=p_j\forall j\in \{1,...,n\}$At a $t$ no more that $m$ time spans of jobs get processed:

$\sum _{j=1}^n{x}_{j,t}\le m\forall t\in \{0,...,k-1\}$
A job is only processed after its release:
$x_{j,t}=0\forall j\in \{1,...,n\}\forall t\le l_j$
No negative:
$x_{j,t}\ge 0\forall j\in \{1,...,n\}\forall t\in \{0,...,k-1\}$

Find minimal makespan

Perform a binary search for $T$ in the interval of $ma{x}_{\forall j\in \{1,...,n\}}(r_j)\le T\le \sum _{j=1}^n\frac{p_j}{m}$
The smallest valid $T$ is the optimal solution.

$P|pmtn|C_{max}$

There is reduction of $P|pmtn|C_{max}$ to $P|pmtn,r_j|C_{max}$ by setting all $r_j=0$.
Therefore the optimal solution in $P|pmtn,r_j|C_{max}$ is also optimal for $P|pmtn|C_{max}$

Exercise 8.3 (Assignment Problem) (6 Points)

In class we have reduced the unrelated-machine scheduling problem $R||C_{\max }$ to the problem of finding a perfect matching of minimum cost.
Model the scheduling problem as a integer linear program.
Argue that your formulation is correct.

Variables:

$x_{ij}\in \{0,1\}$ (is job $j$ is assigned to machine $i$)
$C_{\max }\in \mathbb{R}$ (objective to minimize)

Optimization function

$min(C_{\max })$

Constraints

Each job is assigned to exactly one machine
$\sum _{i=1}^m{x}_{ij}=1\forall j\in \{1,...,n\}$
Load on each machine cannot exceed the $C_{\max }$:
$\sum _{j=1}^n{p}_{ij}\cdot x_{ij}\le C_{\max }\forall i\in \{1,...,m\}$
Binary constraints:
$x_{ij}\in \{0,1\}\forall i\in \{1,...,m\}\forall j\in \{1,...,n\}$

Correctness Argument

Each job is assigned to exactly one machine (Constraint 1)
→ Feasibility
Each machine’s total assigned job processing time does not exceed $C_{\max }$ (Constraint 2)
→ Machine load respected
The LP minimizes ⁡$C_{\max }$​, which is goal in the scheduling problem.