On the Value of Job Migration in Online Makespan Minimization

Makespan minimization on identical parallel machines is a classical scheduling problem. We consider the online scenario where a sequence of n jobs has to be scheduled non-preemptively on m machines so as to minimize the maximum completion time of any job. The best competitive ratio that can be achieved by deterministic online algorithms is in the range [1.88, 1.9201]. Currently no randomized online algorithm with a smaller competitiveness is known, for general m. In this paper we explore the power of job migration, i.e. an online scheduler is allowed to perform a limited number of job reassignments. Migration is a common technique used in theory and practice to balance load in parallel processing environments. As our main result we settle the performance that can be achieved by deterministic online algorithms. We develop an algorithm that is \(\alpha _m\)-competitive, for any \(m\ge 2\), where \(\alpha _m\) is the solution of a certain equation. For \(m=2\), \(\alpha _2 = 4/3\) and \(\lim _{m\rightarrow \infty } \alpha _m = W_{-1}(-1/e^2)/(1+ W_{-1}(-1/e^2)) \approx 1.4659\). Here \(W_{-1}\) is the lower branch of the Lambert W function. For \(m\ge 11\), the algorithm uses at most 7m migration operations. For smaller m, 8m to 10m operations may be performed. We complement this result by a matching lower bound: No online algorithm that uses o(n) job migrations can achieve a competitive ratio smaller than \(\alpha _m\). We finally trade performance for migrations. We give a family of algorithms that is c-competitive, for any \(5/3\le c \le 2\). For \(c= 5/3\), the strategy uses at most 4m job migrations. For \(c=1.75\), at most 2.5m migrations are used.

Authors and Affiliations

1. Department of Computer Science, Technische Universität München, Boltzmannstr. 3, 86748, Garching, Germany

   Susanne Albers

2. Department of Computer Science, Humboldt-Universität zu Berlin, Unter den Linden 6, 10099, Berlin, Germany

   Matthias Hellwig

Corresponding author

Correspondence to Susanne Albers.

A preliminary version of this paper has appeared in Proc. 20th Annual European Symposium on Algorithms (ESA), 2012. Susanne Albers’ work supported by the German Research Foundation, project Al 464/7-1.

Appendix

Proof of Lemma 1

Fix \(m\ge 2\). We first evaluate \(f_m(2)\) and \(f_m(1+1/(3m))\). For \(\alpha =2\), we have \(\lceil (1-1/\alpha )m\rceil \ge m/2\). Hence \(\lceil (1-1/\alpha )m\rceil \alpha /m \ge 1\) and \(f_m(2) \ge 1\). For \(\alpha =1+ 1/(3m)\), there holds \(\lceil (1-1/\alpha )m\rceil =1\). Thus \(f_m(1+1/(3m)) = 1/(3m) H_{m-1} +1/m + 1/(3m^2)< 1/3 + 1/2 + 1/12 < 1\). It remains to show that \(f_m(\alpha )\) is continuous and strictly increasing. To this end we show that, for any \(\alpha >1\) and small \(\epsilon >0\), \(f_m(\alpha ) - f_m(\alpha -\epsilon )\) and \(f_m(\alpha +\epsilon ) - f_m(\alpha )\) converge to 0 as \(\epsilon \rightarrow 0\). Moreover \(f_m(\alpha +\epsilon ) - f_m(\alpha )\) is strictly positive.

First consider an \(\alpha >1\) such that \((1-1/\alpha )m\notin \mathbb {N}\). In this case we choose \(\epsilon > 0\) such that \(\lceil (1-1/(\alpha -\epsilon ))m\rceil = \lceil (1-1/(\alpha +\epsilon ))m\rceil = \lceil (1-1/\alpha )m\rceil \). We have

Thus \(f_m(\alpha ) - f_m(\alpha -\epsilon ) = f_m(\alpha +\epsilon ) - f_m(\alpha ) = \epsilon (H_{m-1}-H_{\lceil (1-1/\alpha )m\rceil -1}) + \lceil (1-1/\alpha )m\rceil \epsilon /m\). Hence \(f_m(\alpha )-f_m(\alpha -\epsilon )\) and \(f_m(\alpha +\epsilon ) - f_m(\alpha )\) tend to 0 as \(\epsilon \rightarrow 0\). Since \(\alpha >1\) there holds \(\lceil (1-1/\alpha )m\rceil \ge 1\) and thus \(f_m(\alpha +\epsilon ) - f_m(\alpha ) >0\).

Next let \(\alpha >1\) such that \((1-1/\alpha )m\in \mathbb {N}\). In this case we choose \(\epsilon > 0\) such that \(\lceil (1-1/(\alpha -\epsilon ))m\rceil = \lceil (1-1/\alpha )m\rceil \) and \(\lceil (1-1/(\alpha +\epsilon ))m\rceil = \lceil (1-1/\alpha )m\rceil +1\). There holds

As above \(f_m(\alpha ) - f_m(\alpha -\epsilon ) = \epsilon (H_{m-1}-H_{\lceil (1-1/\alpha )m\rceil -1}) + \lceil (1-1/\alpha )m\rceil \epsilon /m\) and the latter expression tends to 0 as \(\epsilon \rightarrow 0\). Taking into account that \((1-1/\alpha )m\in \mathbb {N}\) we obtain

Again, \(f_m(\alpha +\epsilon ) - f_m(\alpha )\) is strictly positive and tends to 0 as \(\epsilon \rightarrow 0\). \(\square \)

Proof of Lemma 2

We first prove that \((\alpha _m)_{m\ge 2}\) is non-decreasing. A first observation is that \(\alpha _m \le m\) because \(f_m(m)\ge 1\). We will show that, for any \(m\ge 3\) and \(1<\alpha \le m\), there holds \(f_{m-1}(\alpha ) \ge f_m(\alpha )\). This implies \(1= f_{m-1}(\alpha _{m-1}) \ge f_m(\alpha _{m-1})\). By Lemma 1, \(f_m\) is strictly increasing and thus \(\alpha _m\ge \alpha _{m-1}\). Consider a fixed \(\alpha \) with \(1<\alpha \le m\). We study two cases depending on whether or not \(\lceil (1-1/\alpha )(m-1)\rceil = \lceil (1-1/\alpha )m\rceil \).

If \(\lceil (1-1/\alpha )(m-1)\rceil = \lceil (1-1/\alpha )m\rceil \), then

We obtain \(f_{m-1}(\alpha ) - f_m(\alpha ) = -(\alpha -1)/(m-1) + \lceil (1-1/\alpha )m\rceil \alpha /(m(m-1)) \ge -(\alpha -1)/(m-1) + (\alpha -1)/(m-1) =0\) and thus \(f_{m-1}(\alpha ) \ge f_m(\alpha )\).

If \(\lceil (1-1/\alpha )(m-1)\rceil < \lceil (1-1/\alpha )m\rceil \), then \(\lceil (1-1/\alpha )(m-1)\rceil = \lceil (1-1/\alpha )m\rceil -1\) and

Since \(\alpha >1\) there holds \(\lceil (1-1/\alpha )(m-1)\rceil \ge 1\). Hence in our case \(\lceil (1-1/\alpha )m\rceil \ge 2\) and \(\lceil (1-1/\alpha )m\rceil -1 >0\). We obtain

Choose x, with \(0\le x <1\), such that \(\lceil (1-1/\alpha )m\rceil = (1-1/\alpha )m +x\). Then

In order to establish \(f_{m-1}(\alpha ) - f_m(\alpha )\ge 0\) is suffices to show

This is equivalent to \((\alpha -1)m(m-1) \ge (m-x)((\alpha -1)m +\alpha x-\alpha )\). Standard algebraic manipulation yield that this is equivalent to \(m \ge mx - \alpha x^2+\alpha x\). Let \(g(x) = mx - \alpha x^2+\alpha x\), for any real number x. This function is increasing for any \(x < (m+\alpha )/(2\alpha )\). Since \(\alpha \le m\), the function is increasing for any \(x <1\). As \(g(0) = 0\) and \(g(1) = m\), it follows that \(m \ge mx - \alpha x^2+\alpha x\) holds for all \(0\le x <1\). We conclude \(f_{m-1}(\alpha ) - f_m(\alpha )\ge 0\).

It is easy to verify that \(f_2(4/3)=1\). We show that \(\lim _{m\rightarrow \infty } \alpha _m\) is upper bounded by \(W_{-1}(-1/e^2)/(1+ W_{-1}(-1/e^2))\). Cesáro [5] proved

where \(\gamma \approx 0.577\) is the Euler-Mascheroni constant. Using this inequality we find, for any c with \(0< c\le 1\) and \(\lceil cm\rceil -2 >0\),

where the second to last inequality holds since \(\ln (m-1/c) \le \ln (m-1)\). for \(0<c\le 1\) and sufficiently large m. We obtain

Obviously, \(\lim _{m\rightarrow \infty } F(m) = (\alpha -1) \ln (\frac{\alpha }{\alpha -1}) +\alpha -1\). We show that \((\alpha -1) \ln (\frac{\alpha }{\alpha -1}) +\alpha -1 = 1\), for \(\alpha =\frac{1}{1-\delta }\), where \(\delta = -1/W_{-1}(-1/e^2)\).

Equation \((\alpha -1) \ln (\frac{\alpha }{\alpha -1}) + \alpha -1 = 1\) is equivalent to \(\ln (\frac{\alpha }{\alpha -1})+1 = \frac{1}{\alpha -1}\), which in turn is equivalent to

Substituting \(x=1/(\alpha -1)\), which is equivalent to \(\alpha =1/x+1\), we find that the above is equivalent to \(xe+e = e^x\). Applying the Lambert W function we find that \(x=-W_{-1}(-1/e^2)-1\) is a solution of the former equality. Substituting we conclude that in fact \(\alpha = W_{-1}(-1/e^2)/(1+ W_{-1}(-1/e^2))\) satisfies the equality. Using the same techniques we can show that \(\lim _{m\rightarrow \infty } \alpha _m\) is lower bounded by \(W_{-1}(-1/e^2)/(1+ W_{-1}(-1/e^2))\). In the calculations, (1) yields that \(H_{m-1} - H_{\lceil cm \rceil } < \ln (1/c) + 1/(2m)\). \(\square \)

Reprints and permissions