An Efficient Polynomial Time Approximation Scheme for Minimizing the Total Weighted Completion Time on Uniformly Related Machines

Next, we elaborate on the known approximation schemes for related problems. Skutella and Woeginger [33] observed that for identical machines the ${\mathrm{\ell }}_2$ norm minimization of the vector of machine loads is equivalent to minimizing the total weighted completion time, if the jobs have equal densities. This equivalence means that an optimal solution to one problem is an optimal solution to the other as the values of the two objective functions differ by an additive constant (which is common to all feasible solutions). Using this approach, they showed that if the ratio between the maximum density and the minimum density of jobs is upper bounded by a constant, then one can adapt the ideas of Alon et al. [3, 4] and obtain an EPTAS for this restricted setting.

The scheme [33] for the problem on identical machines follows the next ideas. First, round all the job sizes and job weights (up or down) to integer powers of $1+\epsilon$. Next, apply randomized geometric partitioning of the jobs based on their (rounded) density, solve each sub-instance consisting of all jobs of one partition using the scheme (which is similar to the one of [3, 4]), and schedule the partial solutions for every machine sorted by non-decreasing job densities. This last step of combining the solutions for the different parts in the partition was more delicate in [33], but as noted in [1], the last step could be made much simpler. Afrati et al. [1] also noted that this approach can be extended to obtain an approximation scheme (a PTAS) for the problem without release dates in other machine environments (see the last remark in [1]). Chekuri and Khanna [8] extended the techniques of [1] to the setting of uniformly related machines (with release dates). The methods of [1, 8] fail completely when one tries to obtain an EPTAS for these problems with or without release dates (even for identical machines).

An EPTAS for the total weighted completion time on uniformly related machines was not known prior to our work, and it was only known for the much simpler case of identical machines. We design such an EPTAS here, using a number of methods explained in the next section. In an accompanying article (see the second part of [12]), we design an EPTAS for total weighted completion time on uniformly related machines with release dates. The current EPTAS is designed for the important special case without release dates, and while this EPTAS requires new ideas, this scheme is significantly simpler than the one of the general case. Before presenting the detailed description of the scheme and its analysis, we present an overview of the scheme. A forthcoming full version will contain additional details and omitted proofs.

Obviously, since any job can start running at any time, an optimal solution (or schedule) never introduces idle time, and moreover, every machine runs its assigned jobs in an optimal order, that is, the jobs are sorted by Smith’s ratios. As any tie-breaking policy leads to the same objective function value, we use a specific tie-breaking policy in this section. More specifically, we will always break ties in favor of running larger jobs first, and in the case of equal size jobs (of the same weight), jobs of smaller indices are scheduled earlier. We call this ordering the natural ordering. Thus, we can define a solution or a schedule as a partition of the jobs to $m$ subsets, one subset for each machine, and the order for each machine will always be the natural one. In some cases, we will compute the total weighted completion time of another permutation (not of the natural ordering). This will be done for the sake of analysis when this calculation is easier for cases where we are interested in an upper bound on the objective value and this upper bound is sufficient.

For an input $X$ and a solution $B$, we let $B(X)$ denote the output and the objective value of $B$ for the input $X$. Recall that for a job $j$, the density of $j$ is the ratio between its weight and its size. Thus, running the jobs sorted according to the natural ordering is equivalent to first sorting them by non-increasing density, and for each density, the jobs are sorted by non-increasing size, breaking ties (among equal size jobs) in favor of scheduling jobs of smaller indices earlier.

For a fixed schedule, the work of machine $i$ is the total size of jobs assigned to it, and its load is its completion time, that is, the work divided by the speed (as we only consider schedules without any idle time). Let the original input instance be denoted by $A$, where job $j$ has size $a_j>0$ and weight ${\omega }_j>0$, and machine $i$ has speed $v_i>0$.

Let $C_j$ denote the completion time of $j$ under a given schedule, that is, the total size of jobs that run before $j$ on the same machine (including $j$), divided by the speed of this machine. We let ${\mathrm{\Gamma }}_j$ be defined as ${\omega }_j(C_j-\frac{a_j}{2v_i})$, where $C_j-\frac{a_j}{2v_i}$ is the time when half of job $j$ is completed (known as the mean busy time of job $j$ [17]). We call these values $\mathrm{\Gamma }$-values, and obviously, the cost of a solution is at least the sum of $\mathrm{\Gamma }$-values. Moreover, for identical machines, the difference between the cost of a solution and the sum of the $\mathrm{\Gamma }$-values is independent of the solution (see also [33]) whereas for uniformly related machines, this difference depends on the speeds as we establish in the following lemma.

Given the original instance $A$, where job $j$ has size $a_j$ and weight ${\omega }_j$, and machine $i$ has speed $v_i$, we create a (rounded) instance $A^{\prime }$ as follows. Let be an accuracy factor, that is a function of $\epsilon$ (where ), and such that $\frac{1}{\delta }$ is an integer. The sets of jobs and machines in $A^{\prime }$ are the same as in $A$. Let $s_i={(1+\delta )}^{\lfloor {\log }_{1+\delta }{v}_i\rfloor }$ be the speed of machine $i$ in instance $A^{\prime }$. Let $w_j={(1+\delta )}^{\lceil {\log }_{1+\delta }{\omega }_j\rceil }$, and $p_j={(1+\delta )}^{\lceil {\log }_{1+\delta }{a}_j\rceil }$ be the weight and size (respectively) of job $j$ in instance $A^{\prime }$. That is, we round up the weights and the sizes of jobs while we round down the speeds of the machines. We will sometimes use ${\mathrm{\Theta }}_j={\log }_{1+\delta }\frac{w_j}{p_j}$, which is always an integer due to the rounding.

Next, we bound the increase of the approximation ratio due to this step. Our goal is to conclude that we can safely consider $A^{\prime }$ instead of $A$. Let $𝒪$ and ${𝒪}^{\prime }$ denote optimal solutions for $A$ and $A^{\prime }$ respectively. Let $SOL$ denote a given solution for both instances, where a solution consists of a partition of the set of jobs to the machines. The ordering for each machine may be different for the two inputs since the natural ordering is used. Using the new notation, for a given schedule, the completion time of $j$ is still denoted by $C_j$, and its weighted completion time is $w_j\cdot C_j$.

By the last proposition, we only consider the instance $A^{\prime }$, and use the obtained schedule as an output for $A$. Thus, it suffices to present an EPTAS for the rounded instance $A^{\prime }$.

Given the input $A^{\prime }$, if $j$ is executed on machine $i$, then ${\mathrm{\Gamma }}_j=w_j(C_j-\frac{p_j}{2s_i})$ where $C_j-\frac{p_j}{2s_i}$ is the time when half of the job is completed. We say that for a given schedule, a block of jobs is a set of jobs of equal density that are assigned to one machine to run consecutively on that machine (there may be additional jobs of the same density, each assigned to run later or earlier than these jobs). The next well-known lemma shows that the sum of $\mathrm{\Gamma }$-values for a block of jobs is a function of their total size, their common density, and the starting time of the block, and it is independent of the other properties of these jobs (but it depends on the speed of the machine). We prove the lemma for completeness similarly to the proof of Lemma 1.

Based on the value of $\delta$ we define a new parameter $\xi$ for the shifting step. Its value is a constant (as a function of $\delta$). Let $\xi =\lceil \mathrm{\ell }\cdot {\log }_{1+\delta }\frac{1}{\delta }\rceil =\lceil {\log }_{1+\delta }{(\frac{1}{\delta })}^{\mathrm{\ell }}\rceil$ for a fixed integer $3\le \mathrm{\ell }\le 5$. Thus, . Next, we use the integrality of $\frac{1}{{\delta }^2}$ and of $\mathrm{\ell }$. We have ${(1+\delta )}^{\frac{\mathrm{\ell }}{{\delta }^2}}>{(1+\delta \cdot \frac{1}{{\delta }^2})}^{\mathrm{\ell }}>{(\frac{1}{\delta })}^{\mathrm{\ell }}$, and we have . However, ${(\frac{9}{8})}^{\xi }\ge {(1+\delta )}^{\xi }\ge \frac{1}{{\delta }^{\mathrm{\ell }}}\ge 8^3$, so $\xi \ge 53$.

We form a partition of integers based on the value of $\xi$, such that every subset has $\xi$ consecutive integers. For an integer $c\in \mathbb{Z}$, let ${\mathrm{\Omega }}_c=\{c\cdot \xi +1,\mathrm{\dots },(c+1)\cdot \xi \}$. The next step will be to partition the collections of integers in a cyclic way. There will be $\frac{1}{{\delta }^{\mathrm{\ell }+1}}$ possible collections. Let $0\le \zeta \le \frac{1}{{\delta }^{\mathrm{\ell }+1}}-1$ be an integer. The collection for the value of $\zeta$ will consist of indices of sets for which the index modulo $\frac{1}{{\delta }^{\mathrm{\ell }+1}}$ is equal to $\zeta$. We will be interested in densities that are powers of $1+\delta$ that belong to ${\mathrm{\Omega }}_c$ where it holds that $(cmod\frac{1}{{\delta }^{\mathrm{\ell }+1}})=\zeta$, and the densities for jobs with densities that belong to such a set will be increased by a constant multiplicative factor.

We define the instance $A_{\zeta }$ by modifying the weights of some jobs in $A^{\prime }$. For a job $j$, if for some (not necessarily positive) integer $v$, ${\mathrm{\Theta }}_j\in {\mathrm{\Omega }}_{v/{\delta }^{\mathrm{\ell }+1}+\zeta }$ (recall that the density of $j$ is an integer power of $1+\delta$ and ${\mathrm{\Theta }}_j={\log }_{1+\delta }\frac{w_j}{p_j}$), then $w_j^{\zeta }=w_j\cdot {(1+\delta )}^{\xi }$, and otherwise $w_j^{\zeta }=w_j$. We let ${\mathrm{\Theta }}_j^{\zeta }={\log }_{1+\delta }\frac{w_j^{\zeta }}{p_j}$ which means that in the first case ${\mathrm{\Theta }}_j^{\zeta }=\xi \cdot {\mathrm{\Theta }}_j$ and in the second case ${\mathrm{\Theta }}_j^{\zeta }={\mathrm{\Theta }}_j$. In the first case, ${\mathrm{\Theta }}_j^{\zeta }\in {\mathrm{\Omega }}_{v/{\delta }^{\mathrm{\ell }+1}+\zeta +1}$ (where , so it was moved to a different density collection out of the $\frac{1}{{\delta }^{\mathrm{\ell }+1}}$ collections). Furthermore, weights (and densities) are increased by a multiplicative factor of at most ${(1+\delta )}^{\xi }\le \frac{1+\delta }{{\delta }^{\mathrm{\ell }}}$. For any $\zeta$, let ${𝒪}^{\zeta }$ be an optimal solution for $A_{\zeta }$. As the set of jobs and machines is the same in $A$, $A^{\prime }$, and $A_{\zeta }$, the sets of feasible solutions for the three instances are the same.

Next, we bound the increase of the cost due to the transformation from $A^{\prime }$ to $A_{\zeta }$. As a result of increasing weights for jobs with densities in a fixed density collection, no job $j\in A_{\zeta }$ has a density such that ${\mathrm{\Theta }}_j^{\zeta }={\log }_{1+\delta }\frac{w_j^{\zeta }}{p_j}\in {\mathrm{\Omega }}_{v^{\prime }/{\delta }^{\mathrm{\ell }+1}+\zeta }$ for any integer $v^{\prime }$. Any value ${(1+\delta )}^{\beta }$ where $\beta \in {\mathrm{\Omega }}_{v/{\delta }^{\mathrm{\ell }+1}+\zeta }$ for an integer $v$ is called a forbidden density for $\zeta$, and other values ${(1+\delta )}^{{\beta }^{\prime }}$ for integer values of ${\beta }^{\prime }$ are called allowed density for $\zeta$. The next lemma compares costs for ${𝒪}^{\prime }(A^{\prime })$ (which was defined to be an optimal solution for $A^{\prime }$) and ${𝒪}^{\zeta }$ for specific values of $\zeta$ (for the corresponding input $A_{\zeta }$). This will allow us to guess a suitable value of $\zeta$ (by enumeration) and approximate ${𝒪}^{\zeta }$ rather than ${𝒪}^{\prime }$.

Down below we present an algorithm that receives an input where the ratio between the maximum density of any job and the minimum density of any job is constant (as a function of $\delta$), and outputs a solution of cost at most $1+\delta$ times the cost of an optimal solution for this input. The ratio between densities will be at most ${(1+\delta )}^y$, where $y=\frac{\xi }{{\delta }^{\mathrm{\ell }+1}}-\xi -1$, The motivation for the value of $y$ is that every density collection has $\xi$ different densities, and since there are $\frac{1}{{\delta }^{\mathrm{\ell }+1}}$ options for $\zeta$, there are $\frac{1}{{\delta }^{\mathrm{\ell }+1}}-1$ options of $\zeta$ for which the density collections were not removed. Sequences of possible densities without gaps introduced by considering $A_{\zeta }$ for a fixed value of $\zeta$ will contain $\xi \cdot (\frac{1}{{\delta }^{\mathrm{\ell }+1}}-1)=y+1$ densities which are integer powers of $1+\delta$, such that the largest one will be larger than the smallest one by a multiplicative factor of at most ${(1+\delta )}^y$.

We next use this algorithm as a black box. For every value of $\zeta$, we apply the following process and create a schedule for the input $A_{\zeta }$. Afterwards, we choose a solution of minimum cost among the $\frac{1}{{\delta }^{\mathrm{\ell }+1}}$ resulting solutions.

Let $0\le \zeta \le \frac{1}{{\delta }^{\mathrm{\ell }+1}}-1$. Decompose the allowed densities for $\zeta$ into collections of consecutive densities that are separated by intervals of forbidden densities for $\zeta$. Since densities were rounded, two densities are consecutive if the large one is larger by a factor of exactly $1+\delta$ from the smaller one. By our construction, this results in subsets of allowed densities with very different densities, such that each subset has allowed densities in an interval of the form $[{(1+\delta )}^{-y}\rho ,\rho ]$, where $\rho ={(1+\delta )}^{(v/{\delta }^{\mathrm{\ell }+1}+\zeta )\xi }$ for some integer $v$ (this is the last density in the density collection just before ${\mathrm{\Omega }}_{v/{\delta }^{\mathrm{\ell }+1}+\zeta }$), $y$ is as defined above ($y=\frac{\xi }{{\delta }^{\mathrm{\ell }+1}}-\xi -1$), and additionally there is a gap between the allowed densities of one set and another set (because there are no jobs with densities in ${\mathrm{\Omega }}_{v/{\delta }^{\mathrm{\ell }+1}+\zeta }$ in $A_{\zeta }$). More precisely, if $I$ and $I^{\prime }$ are two such subsets and the allowed densities for $I$ are smaller than those of $I^{\prime }$, then the largest allowed density for $I$ is smaller by a multiplicative factor of ${(1+\delta )}^{\xi +1}\ge \frac{1+\delta }{{\delta }^{\mathrm{\ell }}}$ than the smallest allowed density of $I^{\prime }$.

A sub-instance is defined to be a non-empty subset of the jobs corresponding to an interval of allowed densities together with the complete set of machines. Let $q$ denote the number of such (sub-)instances (where $q\le n$). Let the instances be denoted by $I_1,\mathrm{\dots },I_q$, such that the maximum allowed density in $I_p$ is ${\rho }_p$, and for $p>1$, ${\rho }_p>{\rho }_{p-1}$, and in fact ${\rho }_p\ge {(1+\delta )}^{\frac{\xi }{{\delta }^{\mathrm{\ell }+1}}}\cdot {\rho }_{p-1}\ge {(\frac{1}{{\delta }^{\mathrm{\ell }}})}^{\frac{1}{{\delta }^{\mathrm{\ell }+1}}}\cdot {\rho }_{p-1}$.

Given a set of solutions $SO{L}_p$, for $1\le p\le q$ (where $SO{L}_p$ is a solution for $I_p$), define a combined solution $SOL$, where the jobs assigned to machine $i$ in $SOL$ are all jobs assigned to this machine in all the solutions. Obviously, in $SOL$ the jobs are scheduled sorted by non-increasing indices of their sets $I_p$.

We will prove that the effect of concatenating solutions is not harmful even though earlier solutions delay the processing of later solutions. This will hold due to the gap between densities of jobs of different instances.

In what follows we design a $(1+\delta )$-approximation algorithm for the bounded ratio problem, that gives a $(1+\delta )(1+8\delta )$-approximation algorithm for $A_{\zeta }$. Since , for an appropriate choice of $\zeta$, we get an $(1+22\delta )$-approximation algorithm for $A^{\prime }$, and a $(1+48\delta )$-approximation algorithm for $A$. Thus, letting $\delta =\frac{\epsilon }{48}$ will give a $(1+\epsilon )$-approximation algorithm for the general problem. The algorithm for the bounded ratio problem is applied at most $n$ times for each choice of $\zeta$, i.e., at most $\frac{n}{{\delta }^6}$ times in total. The reason is that we split every input $A_{\zeta }$ into parts with similar densities, and the number of parts cannot exceed the number of jobs.

Let $I$ be a bounded instance such that all densities are in $[1,\rho =\rho (\delta )={(1+\delta )}^y]$, where $y$ is a function of $\delta$ ($y$ and $\xi$ are as defined in the previous section). We will use not only the property that the number of distinct densities is a constant but also the constant maximum ratio between densities. By scaling (and possibly increasing the interval of densities), any valid input of the bounded ratio problem can be transformed into this form. We have the following properties. First, we have $y=\frac{\xi }{{\delta }^{\mathrm{\ell }+1}}-\xi -1\ge \frac{\xi }{{\delta }^{\mathrm{\ell }}}>400$ (since $\frac{1}{{\delta }^{\mathrm{\ell }+1}}-\frac{1}{{\delta }^{\mathrm{\ell }}}-1=\frac{1-\delta -{\delta }^{\mathrm{\ell }+1}}{{\delta }^{\mathrm{\ell }+1}}>1>\frac{1}{\xi }$ as by $\mathrm{\ell }\ge 3$ and $\delta \le \frac{1}{8}$, and since $\xi \ge 53$). Second, since $\mathrm{\ell }\le 5$ and $\xi \le \frac{1}{{\delta }^3}$ and due to integrality, $y+3\le \frac{1}{{\delta }^9}$. Third, we also have (using the properties of $\xi$) that ${(1+\delta )}^y\ge {(1+\delta )}^{\frac{\xi }{{\delta }^{\mathrm{\ell }}}}\ge {\left(\frac{1}{{\delta }^{\mathrm{\ell }}}\right)}^{\frac{1}{{\delta }^{\mathrm{\ell }}}}\ge {(\frac{1}{{\delta }^3})}^{\frac{1}{{\delta }^3}}>\frac{1}{{\delta }^{1500}}$, and ${(1+\delta )}^y\le {(1+\delta )}^{\xi /{\delta }^{\mathrm{\ell }+1}}\le {(\frac{1}{{\delta }^{\mathrm{\ell }+1}})}^{\frac{1}{{\delta }^{\mathrm{\ell }+1}}}\le {(\frac{1}{\delta })}^{6/{\delta }^6}\le {(\frac{1}{\delta })}^{1/{\delta }^7-12}$, and last, we conclude that $y+1\le {\delta }^2{(1+\delta )}^y$ since $y+1\le \frac{1}{{\delta }^9}$ while ${(1+\delta )}^y\ge \frac{1}{{\delta }^{1500}}$.

Since the density of every job is in $[1,{(1+\delta )}^y]$, every job $j\in I$ has $p_j={(1+\delta )}^k$, $w_j={(1+\delta )}^{k^{\prime }}$, for some integers $k,k^{\prime }$ such that $0\le k^{\prime }-k\le y$. Let $\gamma =\frac{{\delta }^{12}}{{(1+\delta )}^y}$. We have $\gamma \ge {\delta }^{1/{\delta }^7}$ and $\gamma \le {\delta }^{1512}$. Let $ℐ$ denote the set of values $i$ such that there is at least one job of size ${(1+\delta )}^i$. Clearly, $|ℐ|\le n$. Let $n_{r,i}$ denote the number of jobs of size ${(1+\delta )}^i$ and density ${(1+\delta )}^r$. By scaling the machine speeds (that are integer powers of $1+\delta$) and possibly reordering the machines, let the speeds of machines be $s_1\ge s_2\mathrm{\cdots }\ge s_m$, where without loss of generality, $s_1=1$, and for $i\ge 2$, $s_i={(1+\delta )}^{k_i}$, for some non-positive integer $k_i\le 0$. It is possible that there is more than one machine of speed $1$, and we consider all such machines in the next paragraph.

Recall that the work of a machine is the total size of jobs assigned to it. We would like to assume that job sizes are scaled such that the work of the most loaded machine (the most loaded machine in terms of work without taking speeds into account) of speed $1$ is in $[1/(1+\delta ),1)$ (while since we have jobs of varying densities, the work of slower machines may be arbitrary). We will now show that this is possible. For a job $j$, and $1\le b\le \frac{n}{\delta }$, let $D_{j,b}$ be the interval $[{(1+\delta )}^{b-1}{p}_j,{(1+\delta )}^b{p}_j)$ (we have that ${(1+\delta )}^{\frac{n}{\delta }}\ge n+1$ holds by a direct calculation since $\frac{n}{\delta }$ is integral).

Without loss of generality we consider solutions where at least one machine of speed $1$ has at least one job. This holds since otherwise it is possible to move an arbitrary job to such a machine and get a solution of a smaller cost.

For every choice of a pair $j,b$ ($\frac{n^2}{\delta }$ choices in total), we scale (i.e., divide) job sizes by ${(1+\delta )}^b{p}_j$ (which is an integer power of $1+\delta$), and apply the algorithm described later in this section (this algorithm enforces the existence of a fastest machine with a suitable load, where it is possible that there is no such solution for some choices). By the claim, given an optimal solution $OPT$, for at least one choice of $j,b$ the assumption regarding the work of the most loaded machine of speed $1$ (that the work is at least ${(1+\delta )}^{-1}$ and below $1$) holds as a result of the scaling. We will pick the best solution, whose objective function value cannot be larger than that of the solution obtained for the correct choice of $j,b$. In what follows we analyze the properties of the correct choice of $j,b$ for a given optimal solution $OPT$ after the scaling. Moreover, the job sizes are according to the scaling.

Let $U$ be a threshold on job sizes separating jobs seen as relatively large and jobs seen as relatively small. Let $\widehat{I}$ be the subset of jobs assigned to machine $i$ in some solution. The $U$-cost of machine $i$ in this solution is defined as the total weighted completion time of jobs whose sizes are at least $U$, plus the $\mathrm{\Gamma }$-values of jobs whose sizes are below $U$. The cost for machine $i$ is therefore its $U$-cost plus . Obviously, the $U$-cost never exceeds the cost, for any value of $U$. Additionally, similarly to the cost, the $U$-cost for a fixed value of $U$ is monotone in the sense that removing a job from the machine decreases its $U$-cost, and thus, if we consider a block of jobs of a common density each of which shorter than $U$, decreasing the total size of jobs in a block also decreases the $U$-cost.

We use the following two functions of $\delta$: $f(\delta )$ and $g(\delta )$, both integral, non-decreasing, and negative. A machine $i$ is called slow if its speed is at most ${(1+\delta )}^{f(\delta )}$ (and otherwise we say that it is not slow or that it is fast). We say that a machine is lightly loaded if its work does not exceed ${(1+\delta )}^{g(\delta )}$ (and otherwise it is heavily loaded). Let

Consider a fixed optimal solution $OPT$ (for the input considered in this section which consists of a subset of jobs, and given the scaling of machine speeds and job sizes).

Next, we define machine configurations. A configuration is a vector that defines most properties for the schedule of one machine. This consists of a set of jobs assigned to it in terms of the types of jobs, that is, a job is specified by its size and weight but not by its identity, and jobs that are relatively small are defined by their approximate total sizes and densities. The set of all configurations will be denoted by $𝒞$. For a configuration $C\in 𝒞$, the first component is an integer $j_1(C)\in \mathbb{Z}$, such that the total work of the machine is in $({(1+\delta )}^{j_1(C)-2},{(1+\delta )}^{j_1(C)}]$. The second component is a non-positive integer $j_2(C)$ such that the speed of the machine is ${(1+\delta )}^{j_2(C)}$. The third component is an integer $j_3(C)\in \mathbb{Z}$, such that $j_3(C)=j_1(C)-j_2(C)$, and therefore the completion time (or load) of the machine is in $({(1+\delta )}^{j_3(C)-2},{(1+\delta )}^{j_3(C)}]$.

Recall that $\gamma =\frac{{\delta }^{12}}{{(1+\delta )}^y}$. For integers $r,i$ such that $0\le r\le y$, $i\le j_1(C)$, and $\gamma {(1+\delta )}^{j_1(C)-1}\le {(1+\delta )}^i\le {(1+\delta )}^{j_1(C)}$ (i.e., $j_1(C)-1+\lceil {\log }_{1+\delta }\gamma \rceil \le i\le j_1(C)$), there is an integer component $n_{r,i}(C)\ge 0$ stating how many jobs of size ${(1+\delta )}^i$ and density ${(1+\delta )}^r$ are assigned to this machine. These jobs are called large (large for configuration $C$, or large for a machine that has configuration $C$). We let $n_{r,i}(C)=0$ for other (smaller or larger) values of $i$ (these are constants that are not a part of the configuration). There are additional components for other jobs assigned to a machine whose configuration is $C$. These jobs (which are not taken into account in the components of the form $n_{r,i}(C)$) must have smaller values of $i$, as jobs with larger values of $i$ (jobs of sizes above ${(1+\delta )}^{j_1(C)}$) cannot be assigned to a machine that has configuration $C$. This is so since they are too large, given the upper bound on the work of the machine. These remaining jobs are called small jobs for $C$, or small jobs for a machine whose schedule is according to configuration $C$. For every $r$, there is an integer component $t_r(C)\ge 0$ such that the total size of small jobs (of sizes in $(0,\gamma {(1+\delta )}^{j_1(C)-1})$) of density ${(1+\delta )}^r$ assigned to a machine with configuration $C$ is in $((t_r(C)-1)\cdot \gamma {(1+\delta )}^{j_1(C)-1},t_r(C)\cdot \gamma {(1+\delta )}^{j_1(C)-1}]$. We have $t_r(C)=0$ if and only if there are no such jobs for a machine with this configuration.

Recall that $ℐ$ is the set of indices $i$ such that there is at least one job of size ${(1+\delta )}^i$. A configuration $C$ is valid if the total size of jobs is sufficiently close to its required work, and its load does not exceed $\frac{2}{\delta }$. Formally, letting $ℐ(C)=\{i\in ℐ:j_1(C)-1+\lceil {\log }_{1+\delta }\gamma \rceil \le i\le j_1(C)\}$ it is required that ${\sum }_{0\le r\le y,i\in ℐ(C)}{(1+\delta )}^i\cdot n_{r,i}(C)+{\sum }_{r=0}^y{t}_r(C)\cdot \gamma {(1+\delta )}^{j_1(C)-1}\in ({(1+\delta )}^{j_1(C)-2},{(1+\delta )}^{j_1(C)+1}]$. The reason for the increased exponent of the right endpoint is that for every density the total size of small jobs may be smaller by an additive term of $\gamma {(1+\delta )}^{j_1(C)-1}$ compared to its upper bound, and since , it suffices to increase the right endpoint by a multiplicative factor of $1+\delta$. We also let ${ℐ}^{\prime }(C)=\{i\in ℐ:i\le j_1(C)-2+\lceil {\log }_{1+\delta }\gamma \rceil \}$, and require . In the remainder of this section, given $C$, we will use the threshold $U(C)=\gamma {(1+\delta )}^{j_1(C)-1}$ for computing the $U$-cost of a machine with configuration $C$ (this is the value $U$ of the configuration $C$).

The number of components is therefore at most $3+(y+1)\cdot (\lceil {\log }_{1+\delta }\frac{1}{\gamma }\rceil +2)+(y+1)\le 3+(y+1)({\log }_{1+\delta }\frac{1}{\gamma }+3)$. Since ${\log }_{1+\delta }\frac{1}{\gamma }=y+{\log }_{1+\delta }\frac{1}{{\delta }^{12}}\le y+\frac{1}{{\delta }^{13}}$, and $y+1\le \frac{1}{{\delta }^9}$, we have . We will use the following bounds.

Let $J=\{{\sigma }_1,{\sigma }_2,\mathrm{\dots },{\sigma }_{\kappa }\}$ be the set of all $\kappa$ different speeds of machines (where $1\le \kappa \le m$) such that $1={\sigma }_1>{\sigma }_2>\mathrm{\cdots }>{\sigma }_{\kappa }$, and let $N_i\ge 1$ be the number of machines of speed ${\sigma }_i$.

Consider the following mathematical program $𝒫$. The goal of $𝒫$ is to determine a partial schedule via machine configurations. For every configuration $C$, $X_C$ is a decision variable stating how many machines have this configuration. Obviously, the number of used configurations whose second component is ${\sigma }_i$ cannot exceed $N_i$ (it is not required to use all machines, but it is required to assign all jobs). For every triple of density, size, and a configuration (density ${(1+\delta )}^r$, size ${(1+\delta )}^i$, and configuration $C$), there is a decision variable $Y_{r,i,C}$ corresponding to the number of jobs of this size and density that are assigned to machines whose configurations are $C$ as small jobs for this configuration. The variable $Y_{r,i,C}$ may be positive only if a job of size ${(1+\delta )}^i$ is small for configuration $C$, i.e., $i\le j_1(C)-2+\lceil {\log }_{1+\delta }\gamma \rceil$, and in all other cases we set $Y_{r,i,C}=0$ to be a constant rather than a variable. Each such variable is used for all copies of $C$ together since jobs assigned as small jobs within the copies of the configuration may be of different sizes. Based on these decision variables we define a set of constraints and solve the resulting mixed-integer linear program $𝒫$.

A configuration $C$ has a cost denoted by $cost(C)$ associated with it, which is the $U$-cost for the threshold $U(C)=\gamma {(1+\delta )}^{j_1(C)-1}$. Recall that for the purpose of calculating the $U$-cost of a machine, a list of its large jobs is needed. However, for its jobs of size below $U$ (i.e., small jobs), the exact list of such small jobs is not needed. The only needed property of the subset of small jobs (for configuration $C$) of each one of the densities is their total size. This allows us to assign very different jobs that are small to machines with the same configuration, as long as these jobs are indeed small for the configuration and have the same density.

For large jobs, the exact identities of jobs are not needed as well, but a list of densities and sizes is needed. Thus, the $U$-cost for configuration $C$ is calculated assuming that the machine has exactly $n_{r,i}(C)$ jobs of size ${(1+\delta )}^i$ and weight ${(1+\delta )}^{i+r}$ (i.e., density ${(1+\delta )}^r$) assigned to it, and the total size of small jobs (of sizes in $(0,\gamma {(1+\delta )}^{j_1(C)-1})$) with densities equal to ${(1+\delta )}^r$ is exactly $t_r(C)\cdot \gamma {(1+\delta )}^{j_1(C)-1}$. The objective of $𝒫$ is to minimize the sum of costs of configurations plus the missing parts of the costs of jobs that are assigned as small. For that, for a job of size ${(1+\delta )}^i$ and density ${(1+\delta )}^r$ that is assigned to a machine of speed $s$ as a small job for its configuration, an additive term of $\frac{{(1+\delta )}^{r+2i}}{2s}$ is incurred (this is the difference between the actual cost for this job, and its $\mathrm{\Gamma }$-value, which is the part of the cost already included in the $U$-cost). This last term only depends on the speed of the machine that runs the job rather than the specific machine. Thus, for each $r$ and $i$ we add

to the cost of configurations to get the total cost of the schedule, where ${\sum }_{C\in 𝒞}{Y}_{r,i,C}$ is the number of jobs of size ${(1+\delta )}^i$ and density ${(1+\delta )}^r$ that are assigned as small jobs for their configurations.

Later, we will use the last mathematical program to direct our algorithm. Before we continue we explain the intuition behind its constraints. We stress that the formal proof does not use this intuition, so it is given to assist the reader. Condition (1) ensures that the number of used machines for each speed does not exceed the existing number of such machines. Condition (2) states that every job is assigned (either it is a large job or a small job). Condition (3) considers jobs of density ${(1+\delta )}^r$ that are assigned as small to machines scheduled according to configuration $C$, and verifies that sufficient space is allocated for them if the space for them is slightly extended (this extended space may be used as we show later). Condition (4) ensures that indeed there is a machine of the maximum speed that has a work that is close to $1$, that is, above $\frac{1}{{(1+\delta )}^2}$ and at most $1+\delta$ (the condition that the work is in $[1/(1+\delta ),1)$ is slightly relaxed).

Observe that we distinguish between large and small jobs for a machine based on the configuration and not solely by its speed. This feature is needed since our problem does not allow the use of the dual-approximation method (because the objective is not based on machine loads).

We define the set of heavy configurations ${𝒞}_H$ as ${𝒞}_H=\{C\in 𝒞:j_1(C)>g(\delta )\}$, (note that the definition of a heavy configuration or a heavily loaded machine depends only on the work, and it is independent of the speed) and the complement set of light configurations is ${𝒞}_L=𝒞\setminus {𝒞}_H$. By Lemma 7 it is sufficient to consider light configurations for slow machines. Therefore, we delete heavy configurations for slow machines and do not consider them (which is justified later in the comparison between the cost of an optimal schedule and the optimal solution of $𝒫$).

We see $𝒫$ as a mixed-integer linear program and thus we define next the set of variables that are forced to be integral and the set of variables that are allowed to be fractional. All variables $Y_{r,i,C}$ may be fractional. The variables of (light) configurations corresponding to slow machines and variables of light configurations of fast machines may be fractional, whereas the variables of heavy configurations corresponding to fast machines must be integral. The number of variables is polynomial, and the number of integral variables will be constant (a function of $\delta$).

Recall that for every pair of speed and work (i.e, a pair $j_1,j_2$), the number of different valid configurations is constant (as a function of $\delta$). The number of different speeds of fast machines is at most $|f(\delta )|=-f(\delta )$. The number of different values of $j_1(C)$ such that $C$ is a heavy configuration is at most $-g(\delta )+\lceil {\log }_{1+\delta }\frac{2}{\delta }\rceil \le \frac{2}{{\delta }^2}-g(\delta )=-f(\delta )$, and $j_2(C)$ of a heavy configuration $C$ must be a fast speed (so there are at most $-f(\delta )$ values for it). As the number of integral variables is constant (as a function of $\delta$), an optimal solution can be found in polynomial time [30, 26] that is a function of $\delta$ multiplied by a polynomial in the input encoding length.

We will first compare the cost of the optimal schedule $OPT$ to the cost of an optimal solution of $𝒫$. Later, we will show how to obtain an actual schedule given a solution of $𝒫$, such that the cost of the schedule is larger only by a factor of at most $1+\delta$ than the objective function value of the solution to $𝒫$. Let $(X^{\ast },Y^{\ast })$ denote an optimal solution to the mixed-integer linear program, and let $Z^{\ast }$ be its objective value. Let $Z^{OPT}$ denote the cost of $OPT$.

Our last rounding steps are designed in order to use $(X^{\ast },Y^{\ast })$ for getting an approximate schedule for the rounded ratio problem. These steps are the constructive methods for establishing our scheme.

We start with constructing an alternative set of values of the variables and bounding the resulting cost from above. We will later convert this alternative solution (that may violate some of the constraints of $𝒫$) into a schedule. For every $C\in 𝒞$, let $X_C^{\prime }=\lfloor X_C^{\ast }\rfloor$. If $X_C^{\ast }=0$, then we set $X_C^{\prime }=0$. In this case $Y_{r,i,C}^{\ast }=0$ must hold for all $r,i$ by (3), and we set $Y_{r,i,C}^{\prime }=0$. If $X_C^{\ast }>0$, we consider two cases. If $C\in C_H$, then the variables of configurations are integral, and therefore $X_C^{\prime }=X_C^{\ast }$. In this case we set $Y_{r,i,C}^{\prime }=\lceil Y_{r,i,C}^{\ast }\rceil$ for any $0\le r\le y$, $i\in {ℐ}^{\prime }(C)$. Otherwise, that is, in the case $C\in C_L$, let $Y_{r,i,C}^{\prime }=\lfloor \frac{X_C^{\prime }}{X_C^{\ast }}\cdot Y_{r,i,C}^{\ast }\rfloor$. Using these definitions, in the case $Y_{r,i,C}^{\prime }>0$, if $C\in C_H$, then we have $Y_{r,i,C}^{\prime }\le Y_{r,i,C}^{\ast }+1$, and otherwise we have $Y_{r,i,C}^{\prime }\le \frac{X_C^{\prime }}{X_C^{\ast }}\cdot Y_{r,i,C}^{\ast }$. Moreover, if $C\in C_L$ and $X_C^{\ast }>0$, then we have $Y_{r,i,C}^{\prime }>\frac{X_C^{\prime }}{X_C^{\ast }}\cdot Y_{r,i,C}^{\ast }-1>Y_{r,i,c}^{\ast }-\frac{Y_{r,i,C}^{\ast }}{X_C^{\ast }}-1$, by (that holds even if $X_C^{\prime }=0$).

We will define a schedule and find an upper bound on its objective function value. Before that, we analyze the first increase in the cost which is due to the transformation from $(X^{\ast },Y^{\ast })$ to $(X^{\prime },Y^{\prime })$, and show that it is by an additive factor of at most ${\delta }^{100}\cdot Z^{\ast }$. The solution $(X^{\prime },Y^{\prime })$ that we consider is not a feasible solution for $𝒫$, as (for example) constraint (2) does not necessarily hold as it is possible that ${\sum }_{C\in 𝒞}{n}_{r,i}(C)X_C^{\prime }+{\sum }_{C\in 𝒞}\cdot Y_{r,i,C}^{\prime }\ne n_{r,i}$, but we can still bound its objective function value using the objective function value of the optimal (and feasible) solution.

Since $X_C^{\prime }\le X_C^{\ast }$ for $C\in 𝒞$, and $Y_{r,i,C}^{\prime }\le Y_{r,i,C}^{\ast }$ for all $C\in C_L$, $0\le r\le y$, and $i\in {ℐ}^{\prime }(C)$, the objective function value for these variables is at most $Z^{\ast }$ plus

since for $C\in C_H$ it holds that $Y_{r,i,C}^{\prime }=0$ if $X_C^{\ast }=0$, and otherwise $Y_{r,i,C}^{\prime }-Y_{r,i,C}^{\ast }\le 1\le X_C^{\ast }$. Next, we show that

for any $C\in C_H$, and thus we will conclude that the objective function value of the set of variables $X_C^{\prime }$, $Y_{r,i,C}^{\prime }$ is at most $(1+{\delta }^{100})\cdot Z^{\ast }$. We have $cost(C)\ge \frac{{(1+\delta )}^{2j_1(C)-4}}{2{(1+\delta )}^{j_2(C)}}$ (by Lemma 1, since $cost(C)$ is computed for jobs of total size above ${(1+\delta )}^{j_1(C)-2}$, and the jobs densities are no smaller than $1$). Let $i^{\prime }=\max {ℐ}^{\prime }(C)$. We have

and

Additionally, . For a given $C\in C_H$, we get