The following is directly taken from pages 358-360 of The Nature of Computation by Moore and Mertens and I think addresses your problem directly.
Imagine that you run a computer center with $p$ identical machines, or a parallel computer with $p$ processors, for some constant $p$. You are given $n$ jobs with running times $t_1,t_2,...,t_n$. Your task is to find a schedule - a function $f:\{1,...,n\}\rightarrow\{1,...,p\}$ that assigns the $j$th job to the $f(j)$th machine.
The load on the $j$th machine is the total time it takes to run the jobs assigned to it,
$$
L_j = \sum_{i:f(i)=j} t_i\,.
$$
Since the machines run in parallel, the time it takes us to finish all the jobs is the maximum load on any machine,
$$
M=\max_{i\leq j\leq p} L_j\,.
$$
We call this time the makespan, and your goal is to minimize it. This gives the following problem:
Makespan
Input: A set of $n$ running times $t_i\geq0,\,i=1,...,n$
Output: A function $f: \{1,...,n\}\rightarrow\{1,...,p\}$ that minimizes the makespan
$$M = \max_{1 \leq j \leq p} \sum_{i:f(i)=j}t_i$$
Exercise 9.3 Reduce Integer Partitioning to the case of Makespan where $p=2$.
There is, however, a simple algorithm that comes with a quality guarantee. The idea is to divide tasks into two groups, "large" and "small", and schedule the large tasks first. Let $T_{\text{tot}}=\sum_{j=1}^n t_j$ be the total running time of all the tasks. We choose some constant $\eta > 0$, say $\eta = 1/10$. We call the $j$th task large if its running time is at least a fraction $\eta$ of the total, $t_j \geq \eta\,T_{\text{tot}}$, and small if $t_j < \eta\,T_{\text{tot}}$.
The algorithm then proceeds in two phases:
- Find a schedule that minimizes the makespan of the large tasks, using exhaustive search.
- Distribute the small tasks by giving each one to the machine with the smallest load so far, regardless of that tasks's running time.
How long does this algorithm take? Since there are at most $1/\eta$ large tasks, there are $p^{1/\eta}$ ways to schedule them. Since $p$ and $\eta$ are constants, this gives a constant number of possible schedules to explore in phase 1, and we can check all of them in polynomial time using exhaustive search. Phase 2 clearly runs in polynomial time as well.
Now let $M$ denote the makespan of the schedule produced by this algorithm. How does it compare to $M_{\text{opt}}$? Let $M_{\text{large}}$ denote the maximum load of a machine after phase 1, i.e., the minimum makespan of the large tasks. Since adding the small tasks can only increase the makespan, we have $M_{\text{large}} \leq M_{\text{opt}}$. If the algorithm manages to fit all the small tasks in phase 2 without increasing the makespan, putting them on machines with load less than $M_{\text{large}}$, then $M = M_{\text{large}}$. But since $M_{\text{opt}} \leq M$, in this case $M = M_{\text{opt}}$ and the algorithm performs perfectly.
So, we will focus on the harder case where the makespan increases in phase 2, so that $M > M_{\text{large}}$ and our schedule for the small tasks might not be optimal. Let $L_j$ denote the load of machine $j$ after phase 2. Without loss of generality, we can assume that $L_1 \geq L_2 \geq ... \geq L_p$. Since $L_1 = M > M_{\text{large}}$, we know that at least one small task was added to machine 1.
Let $t$ be the running time of the last such task. Since our strategy greedily assigns small tasks to the machines with the smallest load, the load of machine 1 must have been less than or equal to the others just before this task was added. This means that, for all $2 \leq j \leq p$,
$$
M-t \leq L_j \leq M\,.
$$
Since $t<\eta\,T_{\text{tot}}$, we also have
$$
T_{\text{tot}} = M + \sum_{j=2}^p L_j \geq pM-(p-1)t\geq pM-\eta(p-1)T_{\text{tot}}\,.
$$
Rearranging this gives an upper bound on M,
$$
M \leq \frac{T_{\text{tot}}}{p}(1+\eta(p-1))\,.
$$
On the other hand, the best schedule we could hope for would be perfectly balanced, keeping all the machines busy all the time. Thus the optimum makespan is bounded below by
$$
M_{\text{opt}}\geq\frac{T_{\text{tot}}}{p}\,.
$$
Combining this lower bound on $M_{\text{opt}}$ with the upper bound we have on $M$ gives an approximation ratio
$$
\rho \leq \frac{M}{M_{\text{opt}}} \leq 1+\eta(p-1)\,.
$$
By setting $\eta = \epsilon/(p-1)$, we can approximate $M_{\text{opt}}$ within a factor of $\rho = 1+\epsilon$ for arbitrarily small $\epsilon > 0$. In fact, we can define an algorithm that takes both the problem instance and $\epsilon$ as inputs, and returns a $(1+\epsilon)$-approximation. For each fixed $\epsilon$, this algorithm runs in polynomial time. Such an algorithm is called a polynomial-time approximation scheme or PTAS.
On the face of it, a PTAS seems to be sufficient for all practical purposes. It allows us to find solutions within 1%, 0.1%, 0.01% ... of the optimum, each in polynomial time. However, improving the quality of the approximation comes at a cost, since the running time increases as $\epsilon$ decreases. Our PTAS for Makespan, for example, has to explore $p^{1/\eta} = p^{(p-1)/\epsilon}$ possible schedules in phase 1, so its running time grows exponentially as a function of $1/\epsilon$. Even for $p=2$ and $\epsilon = 0.01$, this number is $2^{100}$ - hardly a constant that we can ignore.
We would prefer an algorithm whose running time is polynomial both in $n$ and in $1/\epsilon$. Such an algorithm is called a fully polynomial-time approximation scheme, or FPTAS for short. There is, in fact, an FPTAS for Makespan, which we will not describe here.
The end of chapter notes further recommend the "outstanding" book Approximation Algorithms by Vazirani, from which this algorithm is apparently taken.
