From this blog, we will talk about “rounding data” strategy and dynamic programing applied in approximation algorithm in detail. And this blog will focus on the problem “scheduling jobs on identical parallel macines”.
Polynomial time approximation Scheme (PTAS)
Definition: A polynomial time approximation scheme (PTAS) is a family of algorithms ${ A_{\epsilon} }$, where there is an algorithm for each ${ \epsilon \geq 0}$, such that ${ A_{\epsilon} }$ is a ${(1+\epsilon) }$-approximation algorithm (for minimization problems) or a ${(1-\epsilon) }$-approximation algorithm (for maximization problems)
We should noticed that
-
Running time depends on ${ \epsilon }$, for fixing ${ \epsilon }$, the runing time is a polynomial function of ${ n }$.
-
PTAS is stronger than other approximation, because there is no lower bound on the approximation ratio.
Problem Definition and whole idea
Definition of problem
Given ${ n }$ jobs and ${ m }$ machines each able to process one job at a time.
Each job is associated with a process time ${ p_j }$. All jobs are available at time ${ 0 }$.
We need to assign all the ${ n }$ jobs to ${ m }$ machines. Denote the time that job ${ j }$ is completed as ${ C_j }$.
The objective is minimize the makespan ${ C_{max} = \max_j C_j }$.
Big picture of idea
-
First we will split the jobs into two kinds – long jobs and short jobs. We will show if we can schedule these long jobs with ${ (1+\epsilon) }$-approximation, then the result is still ${ (1+\epsilon) }$-approximation after scheduling these short jobs.
-
So we move to how to scheduling long jobs with ${ (1+\epsilon) }$-approximation. We can give a series time ${ T }$ and find an algorithm to check if we can finish all the jobs in given time ${ T }$. We select a series of ${ T }$ like ${ 1, (1+\epsilon), (1+\epsilon)^2, \cdots, (1+\epsilon)^n }$, and we find the minimum ${ T^* }$ such that we can complete all the jobs, that will guarantee ${ (1+\epsilon) }$-approximation.
-
Now we need to find an algorithm to check if we can finish all the jobs in given time ${ T }$. We will take the rounding strategy. We will round process time of each job ${ j }$ as ${ \lfloor \frac{p_j}{\mu} \rfloor}$, so each process time is a multiple of ${ \mu }$, it’s more easy to apply Dynamic Programming. And we also prove that if we can schedule these rounding jobs with ${ (1+\epsilon) }$-approximation, then the scheduling plan is still ${ (1+\epsilon) }$-approximation for original jobs.
-
Then, we will design the Dynamic Programming algorithm for rounding jobs and prove it can be done in polynomial time.
Long and short jobs
We can choose some ${ T^* }$ such that ${ T^* \leq OPT }$. We define a job as long job if ${ p_j \geq \epsilon T^* }$, otherwise it is a short job.
Suppose we have an algorithm that can schedule long jobs within ${ (1+\epsilon)OPT }$. We can get following PTAS
-
Step 1: Use “oracle” to schedule long jobs.
-
Step 2: Add the short jobs one by one, each time placing the job on the least loaded machine.
aproximation analysis
Lemma 1：The PTAS gives a sechedule of length ${ C_{max} = (1+\epsilon)OPT }$.
Proof. Let ${ \ell }$ be the job that finishes last in the schedule
-
Case 1: Job ${ \ell }$ is a long job. Then, the makespan doesn’t change after adding short jobs. So, ${ C_{max} = (1+\epsilon)OPT }$.
-
Case 2: Job ${ \ell }$ is a long job. Let ${ S_{\ell} }$ be the start time of job ${ \ell }$. Because, all machines have load at least ${ S_{\ell} }$ (By step2, we place the job on the least loaded machine). Hence, ${ S_{\ell} }$ must be not greater than average process time, that is ${ S_{\ell} \leq \sum_{j \neq \ell} p_j /m \leq \sum_{j} p_j /m }$. And we know the optimal makespan can not be less than average process time. Denote ${ P = \sum_{j} p_j }$, we get
Thus, we get
We prove lemma 1. ${ \square }$
Runing time analysis
It’s clear Step 2 can be done in polynomial time. We will show, by selecting appropriate ${ T^* }$ and assuming ${ m }$ is constant, we can finish Step 1 in polynomial time.
Lemma 2: If ${ T^* = \frac{P}{m}}$, then an optimal schedule of the long jobs can be found in ${ O(m^{m/\epsilon}) }$ time.
Proof. We noticed that the number of long jobs is no more than ${ \frac{P}{\epsilon T^*} = P / \left(\epsilon \frac{P}{m}\right) = \frac{m}{\epsilon} }$. Each long job have ${ m }$ choices, so we can try all posible schedule in ${ O(m^{m/\epsilon}) }$ time. ${ \square }$
Relaxed decision procedure
In the next part, we will give an algorithm ${ \mathcal{B}_{\epsilon} }$, that takes a time ${ T }$ as input. And algorithm ${ \mathcal{B}_{\epsilon} }$ either prove that no schedule of length ${ T }$, or else find a schedule of length ${ (1+\epsilon)T }$. Suppose we have the above algorithm, we will show how we can employ ${ \mathcal{B}_{\epsilon} }$ to solve the original problem.
Bisection Search
Here, we ask all the process times are integer. First we give the lower and upper bound of ${ OPT }$.
Note ${ L_0, U_0 }$ gets from pervious blog (${ OPT }$ makespan must be not less than max process time and average time on ${ m }$ machines. The upper bound can be get by considering the last complete job, which less and equal to average time plus max process time.) Through out the bisection search, we maintain two invariants (1) lower bound ${ L \leq OPT }$, and (2) compute a schedule with makespan at most ${ (1+\epsilon)U }$.
In each iteration, the current interval is ${ [L,U] }$, we set ${ T=\lfloor (L+U)/2\rfloor }$, and run ${ \mathcal{B}_{\epsilon} }$.
-
If ${ \mathcal{B}_{\epsilon} }$ produces a schedule, then update ${ U \leftarrow T }$
-
Otherwise, ${ L \leftarrow T + 1 }$.
The ${ \mathcal{B}_{\epsilon} }$ terminates untill ${ L =U }$.
It’s clear to check in each iteration, two variants are keeping correct. And we know the difference between ${ L_0 }$ and ${ U_0 }$ is at most ${\max_{j=1,\cdots,n}p_j }$, denoted as ${ P_m }$. So ${ \mathcal{B}_{\epsilon} }$ stops in ${ O(\ln P_m) }$ steps.
And, we know ${ L = U \leq OPT}$, and ${ \mathcal{B}_{\epsilon} }$ output schedule with makespan ${ (1+\epsilon)U = (1+\epsilon)L \leq OPT }$.
Rounding long jobs
Now we will give the algorithm ${ \mathcal{B}_{\epsilon} }$. First, we need to round the data and apply Dynamic Programming to solve the rounded data. In this section, we will show how to round and prove the approximation.
Let ${ \mu = \epsilon^2 T }$; Round the process time of each long job ${ j}$ as ${ p_j’ = \lfloor \frac{p_j}{\mu} \rfloor \mu }$
Lemma 3: If ${ T \geq OPT }$, and Dynamic Programming can give a schedule on rounded jobs in target time ${ T }$. ${ \mathcal{B}_{\epsilon} }$ will give an ${ (1+\epsilon)T }$ schedule.
Proof. For each job ${ j }$, the difference of ${ p_j }$ and ${ p_j’ }$ bounded by
When Dynamic Programming gives schedule on rounded jobs, we directly use the schedule for original jobs. Because we only consider long job here, so we have ${ p_j \geq \epsilon T }$ by definition. And the makespan at most ${ T }$ for each machine, so there at most ${ \frac{T }{p_j} \leq \frac{T}{\epsilon T} = \frac{1}{\epsilon} }$ jobs.
Hence, we increase the process time per machine at most ${\frac{1}{\epsilon} \cdot \epsilon^2 T = \epsilon T}$, that means the total length of schedule of original jobs is ${ (1+\epsilon)T }$ approximation. ${ \square }$
Dynamic Programming of rounded long jobs
Then all the process times of rounded jobs are multiple of ${ \mu }$ and let the largest be ${ r \mu }$.
We sat a job is of type ${ i }$ if its rounded time is ${ i \mu }$.
We define a vector ${ (n_1,n_2,\cdots,n_r) }$ represents a set of jobs where each ${ n_i }$ is the number of jobs of type ${ i }$.
Let ${ \mathcal{C} }$ denote the set of all possible vectors for which the total rounded processing time is at most ${ T }$, i.e., the set of jobs represented by vector in ${ \mathcal{C} }$ can be completed in ${ T }$ in one machine.
Denoted the vector of rounded instance is ${ (\hat{n_1},\hat{n_2},\cdots,\hat{n_r}) }$.
We define the subproblem of DP as ${ F_k(n_1,n_2,\cdots,n_r) }$, that returns True or False, meaning if we can schedule instance ${ (n_1,n_2,\cdots,n_r) }$ on ${ k }$ machine in time ${ T }$.
The state transition equation is: ${ F_k(n_1,n_2,\cdots,n_r) = \text{TRUE} }$ if and only if
-
${ (n_1,n_2,\cdots,n_r) \in \mathcal{C} }$ or
-
There exists ${ (s_1,s_2,\cdots,s_r) \in \mathcal{C} }$, such that ${ F_k(n_1-s_1,n_2-s_2,\cdots,n_r-s_r) = \text{TRUE} }$
And finnaly we need to compute ${ F_m(\hat{n_1},\hat{n_2},\cdots,\hat{n_r}) }$. Additionally, retrieve the corresponding schedule in the DP, we can return the schedule for all long rounded jobs.
Run-time in Polynomial
We need to prove the total running time is in polynomial time by showing the number of iterations in DP is in polynomial time and each iteration consumes in polynomial time. The key points are proving ${ \vert \mathcal{C} \vert }$ and ${ r }$
Claim 1: ${ r }$ is a constant
Proof. Let ${ p_m = \max_j p_j }$. As ${ P_m \leq OPT \leq T }$. So the largest rounded processing time is ${ \Bigl\lfloor \frac{p_m}{\mu} \Bigr\rfloor \mu \leq \Bigl\lfloor \frac{T}{\mu} \Bigr\rfloor \mu }$. So ${r= \Bigl\lfloor \frac{T}{\mu} \Bigr\rfloor \leq \frac{T}{\mu} = \frac{T}{\epsilon^2 T} = \frac{1}{\epsilon^2} }$ is a constant. ${ \square }$
Claim 2: The number of rounded jobs per machine is a constant.
Proof. From previous discussion, we already prove that there is at most ${ \frac{T }{p_j} \leq \frac{T}{\epsilon T} = \frac{1}{\epsilon} }$ jobs. ${ \square }$
Claim 3: ${ \vert \mathcal{C} \vert }$ is a constant.
Proof. One machine can only have ${ \frac{1}{\epsilon} }$ jobs, so ${ \forall (n_1,n_2,\cdots,n_r) \in \mathcal{C} }$, ${ n_1,n_2,\cdots,n_r \leq \frac{1}{\epsilon} }$, and ${ r }$ is constant. So, ${ \vert \mathcal{C} \vert }$ is a constant. ${ \square }$
Claim 4: Number of iterations in DP is polynomial.
Proof. One machine can only have ${ \frac{1}{\epsilon} }$ jobs, so the total long jobs can not greater that ${ \frac{m}{\epsilon} }$. Hence, ${ \hat{n_i} \leq \frac{m}{\epsilon} }$. So Number of iterations in DP is at most ${ m \left(\frac{m}{\epsilon}\right)^r \leq m \left(\frac{m}{\epsilon}\right)^{1 /\epsilon^2} }$. ${ \square }$
So, it’s clear that total running time of DP is in polynomial time.