On the Value of Job Migration in Online Makespan Minimization

Abstract

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.

1 Introduction

Makespan minimization on identical machines is a fundamental scheduling problem that has received considerable research interest over the last forty years. Let $\sigma = J_1, \ldots , J_n$ be a sequence of jobs that has to be scheduled non-preemptively on m identical parallel machines. Each job $J_i$ is specified by a processing time $p_i$, $1\le i \le n$. The goal is to minimize the makespan, i.e. the maximum completion time of any job in a schedule. In the offline setting all jobs are known in advance. In the online setting the jobs arrive one by one. Each job $J_i$ has to be scheduled immediately on one of the machines without knowledge of any future jobs $J_k$, $k>i$. An online algorithm A is called c-competitive if, for any job sequence, the makespan of A’s schedule is at most c times the optimum makespan for that sequence [23].

Early work on makespan minimization studied the offline setting. Already in 1966, Graham [12] presented the List scheduling algorithm that schedules each job on a least loaded machine. List can be used both as an offline and as an online strategy and achieves a performance ratio of $2-1/m$. Hochbaum and Shmoys devised a famous polynomial time approximation scheme [15]. More recent research, published mostly in the 1990s, investigated the online setting. The best competitive factor that can be attained by deterministic online algorithms is in the range [1.88, 1.9201]. Due to this relatively high factor, compared to List’s ratio of $2-1/m$, it is interesting to consider scenarios where an online scheduler has more flexibility to serve the job sequence.

In this paper we investigate the impact of job migration. At any time an online algorithm may perform reassignments, i.e. a job already scheduled on a machine may be removed and transfered to another machine. Process migration is a well-known and widely used technique to balance load in parallel and distributed systems. It leads to improved processor utilization and reduced processing delays. Migration policies have been analyzed extensively in theory and practice.

It is natural to investigate makespan minimization with job migration. In this paper we present a comprehensive study and develop tight upper and lower bounds on the competitive ratio that can be achieved by deterministic online algorithms. It shows that even with a very limited number of migration operations, significantly improved performance guarantees are obtained.

Previous work We review the most important results relevant to our work. As mentioned above, List is $(2-1/m)$-competitive. Deterministic online algorithms with a smaller competitive ratio were presented in [2, 4, 10, 11, 16]. The best algorithm currently known is 1.9201-competitive [10]. Lower bounds on the performance of deterministic strategies were given in [2, 3, 9, 14, 18, 19]. The best bound currently known is 1.88, for general m, see [18]. Randomized online algorithms cannot achieve a competitive ratio smaller than $e/(e-1)\approx 1.58$ [6, 21]. No randomized algorithm whose competitive ratio is provably below the deterministic lower bound is currently known, for general m. If job preemption is allowed, the best competitiveness of online strategies is equal to $e/( e-1)\approx 1.58$ [7].

Makespan minimization with job migration was first addressed by Aggarwal et al. [1]. They consider an offline setting. An algorithm is given a schedule, in which all jobs are already assigned, and a budget. The algorithm may perform job migrations up to the given budget. The authors design strategies that perform well with respect to the best possible solution that can be constructed with the budget. Online makespan minimization with migration on $m=2$ machines was considered in [17, 22]. The best competitiveness is 4/3. Sanders et al. [20] study an online setting in which before the assignment of each job $J_i$, jobs up to a total processing volume of $\beta p_i$ may be migrated, for some constant $\beta$. For $\beta =4/3$, they present a 1.5-competitive algorithm. They also show a $(1+\epsilon )$-competitive algorithm, for any $\epsilon >0$, where $\beta$ depends exponentially on $1/\epsilon$. The algorithms are robust in that the stated competitive ratios hold after each job assignment. However in this framework, over time, $\Omega (n)$ migrations may be performed and jobs of total processing volume $\beta \sum _{i=1}^n p_i$ may be moved.

Englert et al. [8] study online makespan minimization if an algorithm is given a buffer that may be used to partially reorder the job sequence. In each step an algorithm assigns one job from the buffer to the machines. Then the next job in $\sigma$ is admitted to the buffer. Englert et al. show that, using a buffer of size $\Theta (m)$, the best competitive ratio is $W_{-1}(-1/e^2)/(1+ W_{-1}(-1/e^2))$, where $W_{-1}$ is the Lambert W function.

Our contribution We investigate online makespan minimization with limited migration. The number of job reassignments does not depend on the length of the job sequence. We determine the exact competitiveness achieved by deterministic algorithms, for general m.

In Sect. 2 we develop an optimal algorithm. For any $m\ge 2$, the strategy is $\alpha _m$-competitive, where $\alpha _m$ is the solution of an equation representing load in an ideal machine profile for a subset of the jobs. For $m=2$, the competitive ratio is 4/3. The ratios are non-decreasing and converge to $W_{-1}(-1/e^2)/(1+ W_{-1}(-1/e^2))\approx 1.4659$ as m tends to infinity. Again, $W_{-1}$ is the lower branch of the Lambert W function. The algorithm uses at most $(\lceil (2-\alpha _m)/(\alpha _m-1)^2\rceil +4)m$ job migrations. For $m\ge 11$, this expression is at most 7m. For smaller machine numbers it is 8m to 10m. We note that the competitiveness of 1.4659 is considerably below the factor of roughly 1.9 obtained by deterministic algorithms in the standard online setting. It is also below the ratio of $e/(e-1)$ attainable if randomization or job preemption are allowed.

In Sect. 3 we give a matching lower bound. We show that no deterministic algorithm that uses o(n) job migrations can achieve a competitive ratio smaller than $\alpha _m$, for any $m\ge 2$. Hence in order to beat the factor of $\alpha _m$, $\Theta (n)$ reassignments are required. Finally, in Sect. 4 we trade migrations for performance. We develop a family of algorithms that is c-competitive, for any constant c with $5/3\le c \le 2$. Setting $c=5/3$ we obtain a strategy that uses at most 4m job migrations. For $c=1.75$, the strategy uses no more than 2.5m migrations.

Our algorithms rely on a number of new ideas. All strategies classify incoming jobs into small and large depending on a careful estimate on the optimum makespan. The algorithms consist of a job arrival phase followed by a migration phase. The optimal algorithm, in the arrival phase, maintains a load profile on the machines with respect to jobs that are currently small. In the migration phase, the algorithm removes a certain number of jobs from each machine. These jobs are then rescheduled using strategies by Graham [12, 13]. Our family of algorithms partitions the m machines into two sets A and B. In the arrival phase the algorithms prefer to place jobs on machines in A so that machines in B are available for later migration. In general, the main challenge in the analyses of the various algorithms is to bound the number of jobs that have to be migrated from each machine.

We finally relate our contributions to some existing results. First we point out that the goal in online makespan minimization is to construct a good schedule when jobs arrive one by one. Once the schedule is constructed, the processing of the jobs may start. It is not stipulated that machines start executing jobs while other jobs of $\sigma$ still need to be scheduled. This framework is assumed in all the literature on online makespan minimization mentioned above. Consequently it is no drawback to perform job migrations when the entire job sequence has arrived. Nonetheless, as for the algorithms presented in this paper, the machines can start processing jobs except for the up to 10 largest jobs on each machine. A second remark is that the algorithms by Aggarwal et al. [1] cannot be used to achieve good results in the online setting. The reason is that those strategies are designed to perform well relative to the best possible makespan attainable from an initial schedule using a given migration budget. The strategies need not perform well compared to a globally optimal schedule. The algorithms by Aggarwal et al. and ours are different, see [1].

On the other hand, our results exhibit similarities to those by Englert et al. [8] where a reordering buffer is given. The optimal competitive ratio of $\alpha _m$ is the solution of an equation that also arises in [8]. This is due to the fact that our optimal algorithm and that in [8] maintain a certain load profile on the machines. Our strategy does so w.r.t. jobs that are currently small while the strategy in [8] considers all jobs assigned to machines. In our framework the profile is harder to maintain because of shrinking jobs, i.e. jobs that are large at some time t but small at later times $t'>t$. In the job migration phase our algorithm reschedules jobs removed from some machines. This operation corresponds to the ”final phase” of the algorithm in [8]. However, our algorithm directly applies policies by Graham [12, 13] while the algorithm in [8] computes a virtual schedule.

In general, an interesting question is if makespan minimization with limited migration is equivalent to makespan minimization with a bounded reordering buffer. We cannot prove this in the affirmative. As for the specific algorithms presented in [8] and in this paper, the following relation holds. All our algorithms can be transformed into strategies with a reordering buffer. The competitive ratios are preserved and the number of job migrations is equal to the buffer size. This transformation is possible because our algorithms are monotone: If a job does not have to be migrated at time t, assuming $\sigma$ ended at time t, then there is no need to migrate it at times $t'>t$. Hence, at any time a buffer can store the candidate jobs to be migrated. On the other hand, to the best of our knowledge, the algorithms by Englert et al. [8] do not translate into strategies with job migration. All the algorithms in [8] use the given buffer of size cm, for some constant c, to store the cm largest jobs of the job sequence. However in our setting, a migration of the largest jobs does not generate good schedules. The problem are again shrinking jobs, i.e. jobs that are among the largest jobs at some time t but not at later times. We cannot afford to migrate all shrinking jobs, unless we invest $\Theta (n)$ migrations. With limited job migration, scheduling decisions are final for almost all of the jobs. Hence the corresponding algorithms are more involved than in the setting with a reordering buffer.

2 An Optimal Algorithm

For the description of the algorithm and the attained competitive ratio we define a function $f_m(\alpha )$. Intuitively, $f_m(\alpha )$ represents accumulated normalized load in a “perfect” machine profile for a subset of the jobs. In such a profile the load fractions of the first $\lfloor m/\alpha \rfloor$ machines follow a Harmonic series of the form $(\alpha -1)/(m-1), \ldots , (\alpha -1)/(m-\lfloor m/\alpha \rfloor )$ while the remaining ratios are $\alpha /m$. Summing up these ratios we obtain $f_m(\alpha )$. Formally, let

$$\begin{aligned} f_m(\alpha ) = (\alpha -1)(H_{m-1}-H_{\lceil (1-1/\alpha )m\rceil -1}) + \lceil (1-1/\alpha )m\rceil \alpha /m, \end{aligned}$$

for any machine number $m\ge 2$ and real-valued $\alpha >1$. Here $H_k = \sum _{i=1}^k 1/i$ denotes the k-th Harmonic number, for any integer $k\ge 1$. We set $H_0 = 0$. For any fixed $m\ge 2$, let $\alpha _m$ be the value satisfying $f_m(\alpha )=1$. Lemma 1 below implies that $\alpha _m$ is well-defined. The algorithm we present is exactly $\alpha _m$-competitive. By Lemma 2, the values $\alpha _m$ form a non-decreasing sequence. There holds $\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$, see also [8]. The following two technical lemmas are proven in the “Appendix”.

Lemma 1

The function $f_m(\alpha )$ is continuous and strictly increasing in $\alpha$, for any integer $m\ge 2$ and real number $\alpha >1$. There holds $f_m(1+1/(3m)) <1$ and $f_m(2) \ge 1$.

Lemma 2

The sequence $(\alpha _m)_{m\ge 2}$ is non-decreasing with $\alpha _2 = 4/3$ and $\lim _{m\rightarrow \infty } \alpha _m = W_{-1}(-1/e^2)/(1+ W_{-1}(-1/e^2))$.

We point out that $\alpha _m$ is a rational number, for any $m\ge 2$. This follows from the fact that, for any $\alpha >1$, $H_{m-1}-H_{\lceil (1-1/\alpha )m\rceil -1}$ and $\lceil (1-1/\alpha )m\rceil /m$ are rational numbers so that the solution to $f_m(\alpha )=1$ is a rational number as well.

2.1 Description of the Algorithm

Let $m\ge 2$ and $M_1, \ldots , M_m$ be the given machines. Furthermore, let $\alpha _m$ be as defined above. The algorithm, called ALG($\alpha _m$), operates in two phases, a job arrival phase and a job migration phase. In the job arrival phase all jobs of $\sigma = J_1, \ldots , J_n$ are assigned one by one to the machines. In this phase no job migrations are performed. Once $\sigma$ is scheduled, the job migration phase starts. First the algorithm removes some jobs from the machines. Then these jobs are reassigned to other machines.

Job arrival phase In this phase ALG($\alpha _m$) classifies jobs into small and large and, moreover, maintains a load profile with respect to the small jobs on the machines. At any time the load of a machine is the sum of the processing times of the jobs currently assigned to it. Let time t be the time when $J_t$ has to be scheduled, i.e. $J_t$ has arrived but not yet been scheduled on any machine, $1\le t \le n$.

In order to classify jobs ALG($\alpha _m$) maintains a lower bound $L_t$ on the optimum makespan, assuming that $J_t$ as already been placed in an optimal schedule. Let $p_t^+ = \sum _{i=1}^t p_i$ be the sum of the processing times of the first t jobs. Furthermore, for $i=1, \ldots , 2m+1$, let $p_t^i$ denote the processing time of the i-th largest job in $J_1, \ldots , J_t$, provided that $i\le t$. More formally, if $i\le t$, let $p_t^i$ be the processing time of the i-th largest job; otherwise we set $p_t^i=0$. Obviously, when t jobs have been scheduled, the optimum makespan cannot be smaller than the average load ${1\over m} p_t^+$ on the m machines. This lower bound was already used in [12]. A second lower bound, used e.g. in [2, 4], is that the optimum makespan cannot be smaller than twice the processing time of the $(m+1)$-st largest job. We slightly generalize this bound. The optimum makespan is lower bounded by three times the processing time of $(2m+1)$-st largest job seen so far, i.e. it is at least $3p_t^{2m+1}$. Define

$$\begin{aligned} L_t = \max \left\{ \textstyle {1\over m}p_t^+, 3p_t^{2m+1}\right\} . \end{aligned}$$

The estimates $L_t$ are non-decreasing over time. Hence a job that is large relative to $L_t$ might not be large relative to $L_{t'}$, where $t'>t$. Therefore we need a careful notion of small and large. A job $J_i$, with $i\le t$, is small at time t if $p_i \le (\alpha _m-1)L_t$; otherwise it is large at time t. In particular $J_t$ is small at time t if $p_t \le (\alpha _m-1)L_t$; otherwise $J_t$ is large at time t. We introduce a final piece of notation. In the sequence $p_t^1, \ldots , p_t^{2m}$ of the 2m largest processing times up to time t we focus on those that are large at time t. More specifically, for $i=1, \ldots , 2m$, let $\hat{p}_t^i = p_t^i$ if $p_t^i >(\alpha _m-1)L_t$; otherwise let $\hat{p}_t^i = 0$. Define

$$\begin{aligned} \textstyle {L^*_t = {1\over m}(p_t^+ - \sum _{i=1}^{2m}\hat{p}_t^i)}. \end{aligned}$$

Intuitively, $L_t^*$ is the average machine load ignoring jobs that are large at time t. Note again that this includes job $J_t$. We verify that there exist at most 2m jobs that are large at time t: If there were at least $2m+1$ such jobs, then $L_t \ge 3p_t^{2m+1} > 3(\alpha _m-1)L_t \ge L_t$ because $\alpha _m\ge 4/3$, see Lemma 2.

We describe the scheduling steps in the job arrival phase. Initially, the machines are numbered in an arbitrary way and this numbering $M_1, \ldots , M_m$ remains fixed throughout the execution of ALG($\alpha _m$). As mentioned above the algorithm maintains a load profile on the machines as far as small jobs are concerned. Define

$$\begin{aligned} \beta (j) = \left\{ \begin{array}{ll} (\alpha _m-1){m\over m-j} &{} \text{ if }\ j \le \lfloor m/\alpha _m\rfloor \\ \alpha _m &{} \text{ otherwise. } \end{array} \right. \end{aligned}$$

We observe that $f_m(\alpha _m) = {1\over m}\sum _{j=1}^m \beta (j)$, taking into account that $m - \lfloor m/\alpha _m \rfloor = \lceil (1-1/\alpha _m)m\rceil$. For any machine $M_j$ $1\le j \le m$, let $\ell (j,t)$ denote its load at time t before $J_t$ is assigned to a machine. Let $\ell _s(j,t)$ be the load caused by the jobs on $M_j$ that are small at time t; again this is the load before $J_t$ is scheduled. The algorithm’s classification of small and large jobs ensures that at any time t there exists a machine $M_j$ satisfying $\ell _s(j,t)\le \beta (j)L_t^*$. Lemma 3 in Sect. 2.2 gives a formal proof.

For $t=1, \ldots , n$, each $J_t$ is scheduled as follows. If $J_t$ is small at its arrival time t, then it is scheduled on a machine with $\ell _s(j,t)\le \beta (j)L_t^*$. In Lemma 3 we show that such a machine always exists. If $J_t$ is large at its arrival time t, then it is assigned to a machine having the smallest load among all machines. At the end of the phase let $L = L_n$ and $L^*=L_n^*$.

Job migration phase This phase consists of a job removal step followed by a job reassignment step. At any time during the phase, let $\ell (j)$ denote the current load of $M_j$, $1\le j\le m$. In the removal step ALG($\alpha _m$) maintains a set R of removed jobs. Initially $R=\emptyset$. During the removal step, while there exists a machine $M_j$ whose load $\ell (j)$ exceeds $\max \{\beta (j)L^*,(\alpha _m-1)L\}$, ALG($\alpha _m$) removes the job with the largest processing time currently residing on $M_j$ and adds the job to R.

Fig. 1

The algorithm ALG($\alpha _m$)

If $R= \emptyset$ at the end of the removal step, then ALG($\alpha _m$) terminates. If $R\ne \emptyset$, then the reassignment step is executed. Let $R'\subseteq R$ be the subset of the jobs that are large at the end of $\sigma$, i.e. whose processing time is greater than $(\alpha _m-1)L$. As shown above, the can exist at most 2m such jobs. ALG($\alpha _m$) first sorts the jobs of $R'$ in order of non-increasing processing time; ties are broken arbitrarily. Let $J_r^i$, $1\le i \le |R'|$, be the i-th job in this sorted sequence and $p_r^i$ be its processing time. For $i=1,\ldots ,m$, ALG($\alpha _m$) forms jobs pairs consisting of the i-th largest and the $(2m+1-i)$-th largest jobs provided that the processing time of the latter job is sufficiently high. A pairing strategy combining the i-th largest and the $(2m+1-i)$-th largest jobs was also used by Graham [13]. Formally, ALG($\alpha _m$) builds sets $P_1, \ldots , P_m$ that contain up to two jobs. Initially, all these sets are empty. In a first step $J_r^i$ is assigned to $P_i$, for any i with $1\le i \le \min \{m,|R'|\}$. In a second step $J_r^{2m+1-i}$ is added to $P_i$ provided that $p_r^{2m+1-i}> p_r^i/2$, i.e. the processing time of $J_r^{2m+1-i}$ must be greater than half times that of $J_r^i$. This second step is executed for any i such that $1\le i\le m$ and $2m+1-i\le |R'|$. For any set $P_i$, $1\le i\le m$, let $\pi _i$ be the total summed processing time of the jobs in $P_i$. ALG($\alpha _m$) now renumbers the sets in order of non-increasing $\pi _i$ values such that $\pi _1\ge \ldots \ge \pi _m$. Then, for $i=1, \ldots , m$, it takes the set $P_i$ and assigns the jobs of $P_i$ to a machine with the smallest current load. If $P_i$ contains two jobs, then both are placed on the same machine. Finally, if $R{\setminus } (P_1\cup \ldots \cup P_m) \ne \emptyset$, then ALG($\alpha _m$) takes care of the remaining jobs. These jobs may be scheduled in an arbitrary order. Each job of $R{\setminus } (P_1\cup \ldots \cup P_m)$ is scheduled on a machine having the smallest current load. This concludes the description of ALG($\alpha _m$). A summary in pseudo-code is given in Fig. 1.

Theorem 1

ALG($\alpha _m$) is $\alpha _m$-competitive and uses at most $(\lceil (2-\alpha _m)/(\alpha _m-1)^2\rceil +4)m$ job migrations.

As we shall see in the analysis of ALG($\alpha _m$) in the job migration phase the algorithm has to remove at most $\mu _m= \lceil (2-\alpha _m)/(\alpha _m-1)^2\rceil +4$ jobs from each machine. Table 1 depicts the competitive ratios $\alpha _m$ (exactly and approximately) and the migration numbers $\mu _m$, for small values of m. We point out that $\alpha _m$ is a rational number, for any $m\ge 2$.

Table 1 The values of $\alpha _m$ and $\mu _m$, for small m

2.2 Analysis of the Algorithm

We first show that the assignment operations in the job arrival phase are well defined. A corresponding statement was shown by Englert et al. [8]. The following proof is more involved because we have to take care of large jobs in the current schedule.

Lemma 3

At any time t there exists a machine $M_j$ satisfying $\ell _s(j,t)\le \beta (j)L_t^*$.

Proof

Suppose that there exists a time t, $1\le t\le n$, such that $\ell _s(j,t)> \beta (j)L_t^*$ holds for all $M_j$, $1\le j\le m$. We will derive a contradiction.

As argued before, among the jobs $J_1, \ldots , J_t$, at most 2m can be large at time t. Hence each of the jobs that is large at time t is represented by a positive entry in the sequence $\hat{p}_t^1, \ldots , \hat{p}_t^{2m}$. Conversely, every positive entry in this sequence corresponds to a job that is large at time t and resides on one of the m machines or is equal to $J_t$ if $J_t$ is large at time t. Hence if $J_t$ is large at time t, $\sum _{j=1}^m \ell (j,t) + p_t = \sum _{j=1}^m \ell _s(j,t) + \sum _{i=1}^{2m}\hat{p}_t^i$. If $J_t$ is small at time t, then $\sum _{j=1}^m \ell (j,t) + p_t \ge \sum _{j=1}^m \ell (j,t)= \sum _{j=1}^m \ell _s(j,t) + \sum _{i=1}^{2m}\hat{p}_t^i$. In either case

$$\begin{aligned}&\sum _{j=1}^m \ell (j,t) + p_t \ge \sum _{j=1}^m \ell _s(j,t) + \sum _{i=1}^{2m}\hat{p}_t^i \ > \ \sum _{j=1}^m \beta (j) L_t^* + \sum _{i=1}^{2m}\hat{p}_t^i\\&\quad =\,m(\alpha _m -1)L_t^*\sum _{j=1}^{\lfloor m/\alpha _m\rfloor } 1/(m-j)\\&\quad +\,(m-\lfloor m/\alpha _m\rfloor )\alpha _m L_t^* +\sum _{i=1}^{2m}\hat{p}_t^i. \end{aligned}$$

Taking into account that $m- \lfloor m/\alpha \rfloor = \lceil (1-1/\alpha _m)m \rceil$ and that $f_m(\alpha _m) = 1$, we obtain

$$\begin{aligned}&\sum _{j=1}^m \ell (j,t) + p_t > mL_t^* ((\alpha _m-1)(H_{m-1}-H_{\lceil (1-1/\alpha _m)m\rceil -1})\\&\quad +\,\lceil (1-1/\alpha _m)m\rceil \alpha _m/m) + \sum _{i=1}^{2m}\hat{p}_t^i\\&\quad =\,mL_t^*f_m(\alpha _m) + \sum _{i=1}^{2m}\hat{p}_t^i = m\left( 1/m\sum _{i=1}^t p_t - 1/m \sum _{i=1}^{2m}\hat{p}_t^i\right) + \sum _{i=1}^{2m}\hat{p}_t^i \ = \ \sum _{i=1}^t p_i. \end{aligned}$$

This contradicts the fact that $\sum _{j=1}^m \ell (j,t) + p_t$ is equal to the total processing time $\sum _{i=1}^t p_i$ of $J_1, \ldots , J_t$. $\square$

We next analyze the job migration phase.

Lemma 4

In the job removal step ALG($\alpha _m$) removes at most $\lceil (2-\alpha _m)/(\alpha _m-1)^2\rceil +4$ jobs from each of the machines.

Proof

Consider any $M_j$, with $1\le j \le m$. We show that it suffices to remove at most $\lceil (2-\alpha _m)/(\alpha _m-1)^2\rceil +4$ so that $M_j$’s resulting load is upper bounded by $\max \{\beta (j)L^*,(\alpha _m-1)L\}$. Since ALG($\alpha _m$) always removes the largest jobs the lemma follows.

Let time $n+1$ be the time when the entire job sequence $\sigma$ is scheduled and the job migration phase with the removal step starts. A job $J_i$, with $1\le i \le n$, is small at time $n+1$ if $p_i \le (\alpha _m-1)L$; otherwise it is large at time $n+1$. Since $L=L_n$ any job that is small (large) at time $n+1$ is also small (large) at time n. Let $\ell (j,n+1)$ be the load of $M_j$ at time $n+1$. Similarly, $\ell _s(j,n+1)$ is $M_j$’s load consisting of the jobs that are small at time $n+1$. Throughout the proof let $k:= \lceil (2-\alpha _m)/(\alpha _m-1)^2\rceil$.

First assume $\ell _s(j,n+1) \le \beta (j)L^*$. If at time $n+1$ machine $M_j$ does not contain any jobs that are large at time $n+1$, then $\ell (j,n+1) = \ell _s(j,n+1) \le \beta (j)L^*$. In this case no job has to be removed and we are done. If $M_j$ does contain jobs that are large at time $n+1$, then it suffices to remove these jobs. Let time l be the last time when a job $J_l$ that is large at time $n+1$ was assigned to $M_j$. Since $L_l \le L$, $J_l$ was also large at time l and hence it was assigned to a least loaded machine. This implies that prior to the assignment of $J_l$, $M_j$ has a load of at most $p_l^+/m\le L_l\le L$. Hence it could contain at most $1/(\alpha _m-1)$ jobs that are large at time $n+1$ because any such job has a processing time greater than $(\alpha _m-1)L$. Hence at most $1/(\alpha _m-1)+1$ jobs have to be removed from $M_j$, and the latter expression is upper bounded by $k+4$.

Next assume $\ell _s(j,n+1) >\beta (j)L^*$. If $\ell _s(j,n) \le \beta (j)L^*= \beta (j)L_n^*$, then $J_n$ was assigned to $M_j$. In this case it suffices to remove $J_n$ and, as in the previous case, at most $1/(\alpha _m-1)+1$ jobs that are large at time $n+1$. Again $1/(\alpha _m-1)+2\le k+4$.

In the remainder of this proof we consider the case that $\ell _s(j,n+1) >\beta (j)L^*$ and $\ell _s(j,n) > \beta (j)L_n^*$. Let $t^*$ be the earliest time such that $\ell _s(j,t) > \beta (j)L_t^*$ holds for all times $t^*\le t \le n$. We have $t^*\ge 2$ because $\ell _s(j,1)=0\le \beta (j)L_1^*$. Hence time $t^*-1$ exists. We partition the jobs residing on $M_j$ at time $n+1$ into three sets. Set $T_1$ is the set of jobs that were assigned to $M_j$ at or before time $t^*-1$ and are small at time $t^*-1$. Set $T_2$ contains the jobs that were assigned to $M_j$ at or before time $t^*-1$ and are large at time $t^*-1$. Finally $T_3$ is the set of jobs assigned to $M_j$ at or after time $t^*$. We show a number of claims that we will use in the further proof.

Claim 4.1 :

Each job in $T_2\cup T_3$ is large at the time it is assigned to $M_j$.

Claim 4.2 :

There holds $\sum _{J_i\in T_1{\setminus }\{J_l\}} p_i \le \beta (j)L_{t^*-1}^*$, where $J_l$ is the job of $T_1$ that was assigned last to $M_j$.

Claim 4.3 :

There holds $|T_2| \le 3$.

Claim 4.4 :

For any $J_l\in T_3$, $M_j$’s load immediately before the assignment of $J_l$ is at most $L_l$.

Claim 4.5 :

Let $J_l\in T_3$ be the last job assigned to $M_j$. If $M_j$ contains at least k jobs, different from $J_l$, each having a processing time of at least $(\alpha _m-1)^2L$, then it suffices to remove these k jobs and $J_l$ such that $M_j$’s resulting load is upper bounded by $(\alpha _m-1)L$.

Claim 4.6 :

If there exists a $J_l\in T_3$ with $p_l<(\alpha _m-1)^2L$, then $M_j$’s load immediately before the assignment of $J_l$ is at most $(\alpha _m-1)L$.

Proof of Claim 4.1

The jobs of $T_2$ are large at time $t^*-1$ and hence at the time they were assigned to $M_j$. By the definition of $t^*$, $\ell _s(j,t)> \beta (j)L_t^*$ for any $t^*\le t \le n$. Hence at or after time $t^*$ ALG($\alpha _m$) does not assign jobs that are small at their arrival time to this machine $M_j$.

Proof of Claim 4.2

All jobs of $T_1{\setminus }\{J_l\}$ are small at time $t^*-1$ and their total processing time is at most $\ell _s(j,t^*-1)$. In fact, their total processing time is equal to $\ell _s(j,t^*-1)$ if $l=t^*-1$. By the definition of $t^*$, $\ell _s(j,t^*-1)\le \beta (j)L_{t^*-1}^*$.

Proof of Claim 4.3

We show that for any t, $1\le t\le n$, when $J_t$ has been placed on a machine, $M_j$ can contain at most three jobs that are large at time t. The claim then follows by considering $t^*-1$. Suppose that when $J_t$ has been scheduled, $M_j$ contained more than three jobs that are large as time t. Among these jobs let $J_l$ be the one that was assigned last to $M_j$. Immediately before the assignment of $J_l$ machine $M_j$ had a load greater than $L_l$ because the total processing time of three large jobs is greater than $3(\alpha _m-1)L_t\ge 3(\alpha _m-1)L_l\ge L_l$ since $\alpha _m\ge 4/3$, see Lemma 2. This contradicts the fact that $J_l$ is placed on a least loaded machine, which has a load of at most $p_{l-1}^+/m < p_l^+/m \le L_l$.

Proof of Claim 4.4

By Claim 4.1 $J_l$ is large at time l and hence is assigned to a least loaded machine, which has a load of at most $p_l^+/m \le L_l$.

Proof of Claim 4.5

Claim 4.4 implies that immediately before the assignment of $J_l$ machine $M_j$ has a load of at most $L_l\le L$. If $M_j$ contains at least k jobs, different from $J_l$, with a processing time of at least $(\alpha _m-1)^2L$, then the removal of these k jobs and $J_l$ from $M_j$ leads to a machine load of at most $L - k(\alpha _m-1)^2 L \le L -\lceil (2-\alpha _m)/(\alpha _m-1)^2\rceil (\alpha _m-1)^2 L \le (\alpha _m-1)L$, as desired.

Proof of Claim 4.6

By Claim 4.1 $J_l$ is large at time l and hence $p_l> (\alpha _m-1)L_l$. Since $p_l<(\alpha _m-1)^2L$, it follows $L_l<(\alpha _m-1)L$. By Claim 4.4, $M_j$’s load prior to the assignment of $J_l$ is at most $L_l$ and hence at most $(\alpha _m-1)L$.

We now finish the proof of the lemma and distinguish two cases depending on the cardinality of $T_2\cup T_3$.

Case 1: If $|T_2\cup T_3| <k+4$, then by Claim 4.2 it suffices to remove the jobs of $T_2\cup T_3$ and the last job of $T_1$ assigned to $M_j$.

Case 2: Suppose $|T_2\cup T_3| \ge k+4$. By Claim 4.3, $|T_2|\le 3$ and hence $|T_3|\ge k+1$. Among the jobs of $T_3$ consider the last $k+1$ ones assigned to $M_j$. If each of them has a processing time of at least $(\alpha _m-1)^2L$, then Claim 4.5 ensures that it suffices to remove these $k+1$ jobs. If one of them, say $J_l$, has a processing time smaller than $(\alpha _m-1)^2L$, then by Claim 4.6 $M_j$’s load prior to the assignment of $J_l$ is at most $(\alpha _m-1)L$. Again it suffices to remove these $k+1$ jobs from $M_j$. $\square$

After the job removal step each machine $M_j$, $1\le j\le m$, has a load of at most $\max \{\beta (j)L^*,(\alpha _m-1)L\}$. We first observe that this load is at most $\alpha _mL$. If $(\alpha _m-1)L\ge \beta (j)L^*$, there is nothing to show. We evaluate $\beta (j)L^*$. If $j> \lfloor m/\alpha _m\rfloor$, then $\beta (j)=\alpha _m$ and $\beta (j)L^* = \alpha _m L^* \le \alpha _m L$. If $j\le \lfloor m/\alpha _m\rfloor$, then $\beta (j) = (\alpha _m-1)m/(m-j) \le (\alpha _m-1)m/(m-\lfloor m/\alpha _m\rfloor ) = (\alpha _m-1)m/\lceil (1-1/\alpha _m)m\rceil )\le \alpha _m$ and thus $\beta (j)L^* \le \alpha _m L$. Hence $M_j$’s load is upper bounded by $\alpha _m { O PT}$, where ${ O PT}$ denotes the value of the optimum makespan for the job sequence $\sigma$. The following lemma ensures that after the reassignment step, each machine still has a load of at most $\alpha _m { O PT}$.

Lemma 5

After the reassignment step each machine $M_j$, $1\le j\le m$, has a load of at most $\alpha _m { O PT}$.

Proof

We show that all scheduling operations in the reassignment step preserve a load of at most $\alpha _m { O PT}$ on each of the machines. We first consider the assignment of the sets $P_1, \ldots , P_m$. Suppose that these sets are already sorted in order of non-increasing total processing times, i.e. $\pi _1\ge \ldots \ge \pi _m$. We first argue that $\pi _1$ and hence any $\pi _i$, $1\le i\le m$, is upper bounded by $OPT$. If $P_1$ contains at most one job, there is nothing to show because $OPT$ cannot be smaller than the processing time of any job in $\sigma$. Assume that $P_1$ contains two jobs. Then it consists of jobs $J_r^{i_1}$ and $J_r^{2m+1-i_1}$, for some $i_1$ with $1\le i_1 \le m$. Since the two jobs are paired there holds $p_r^{2m+1-i_1} > p_r^{i_1}/2$ and hence $p_r^{2m+1-i_1} > \pi _1/3$. Let $OPT'$ denote the optimum makespan for the job sequence $J_r^1, \ldots , J_r^{2m+1-i_1}$. Since $J_r^{i_1}$ and $J_r^{2m+1-i_1}$ are paired, jobs $J_r^{i}$ and $J_r^{2m+1-i}$ are also paired, for any $i_1 <i \le m$, because $p_r^{2m+1-i} \ge p_r^{2m+1-i_1} > p_r^{i_1}/2 \ge p_r^{i}/2$. Hence the sets $P_1, \ldots , P_m$ contain all the jobs $J_r^1, \ldots , J_r^{2m+1-i_1}$, which implies $\pi _1\ge OPT'$ and $p_r^{2m+1-i_1} > OPT' /3$. It follows $p_r^i > OPT' /3$, for all i with $1\le i \le 2m+1-i_1$. Graham [13] showed that given a sequence of up to 2m jobs, each having a processing time greater than a third times the optimum makespan, an optimal schedule is obtained by repeatedly pairing the i-th largest and $(2m+1-i)$-th largest jobs of the sequence. This is exactly the assignment computed by ALG($\alpha _m$) for $J_r^1, \ldots , J_r^{2m+1-i_1}$. We conclude $\pi _1= OPT'$ and $\pi _1\le OPT$.

A final observation is that each job of $R'$ that is not contained in $P_1\cup \ldots \cup P_m$ has a processing time of at most $OPT /3$. A job in $R'{\setminus } (P_1\cup \ldots \cup P_m)$ is equal to a job $J_r^{2m+1-i_0}$, with $1\le i_0\le m$. Since $J_r^{2m+1-i_0}$ is not paired with $J_r^{i_0}$, there holds $p_r^{2m+1-i_0} \le p_r^{i_0}/2$. Assume that $p_r^{2m+1-i_0} > OPT /3$. Then $p_r^{2m+1-i_0}$ is greater than a third times the optimum makespan for the jobs $J_r^1, \ldots , J_r^{2m+1-i_0}$. Using again the results by Graham [13], we obtain that an optimal schedule for the latter job sequence in obtained by repeatedly pairing $J_r^i$ with $J_r^{2m+1-i}$. However, since $p_r^{2m+1-i_0} \le p_r^{i_0}/2$, the processing time $p_r^{2m+1-i_0}$ is at most a third times the resulting optimum makespan for $J_r^1, \ldots , J_r^{2m+1-i_0}$. Hence $p_r^{2m+1-i_0}$ is at most a third times $OPT$, which is a contradiction.

Next we compare the processing time of the jobs of $P_1\cup \ldots \cup P_m$ to $\sum _{i=1}^{2m}\hat{p}_n^i$. Set $R'$ contains the jobs of R that are large at time $n+1$. There exist at most 2m jobs that are large at time $n+1$ and hence the processing time of each job in $R'$ is represented by a positive entry in the sequence $\hat{p}_n^1, \ldots , \hat{p}_n^{2m}$. It follows that the total processing time of the jobs in $R'$ and hence the total processing time of the jobs in $P_1\cup \ldots \cup P_m$ is at most $\sum _{i=1}^{2m}\hat{p}_n^i$. Recall that $\pi _1\ge \ldots \ge \pi _m$. Then, for any j with $1\le j\le m$, the product $j\pi _j$ is upper bounded by the total processing time of $P_1\cup \ldots \cup P_m$ and hence $j\pi _j\le \sum _{i=1}^{2m}\hat{p}_n^i$.

Now consider the assignment of the sets $P_1, \ldots , P_m$ to the machines. Each set is assigned to a least loaded machine. Hence when $P_j$, $1\le j \le m$, is scheduled, it is assigned to a machine whose current load is at most $\max \{\beta (j)L^*,(\alpha _m-1)L\}$. If the load is at most $(\alpha _m-1)L$, then the machine’s load after the assignment is at most $(\alpha _m-1)L+\pi _j \le (\alpha _m-1)L+ OPT \le \alpha _m OPT$. If the current load is only upper bounded by $\beta (j)L^*$, then we distinguish two cases.

If $j\le \lfloor m/\alpha _m\rfloor$, then $j\le m/\alpha _m$, which is equivalent to $m/(m-j) \le \alpha _m/(\alpha _m-1)$. The resulting machine load is at most

$$\begin{aligned}&\beta (j)L^*+\pi _j = (\alpha _m-1){m\over m-j}\left( {1\over m}\sum _{i=1}^n p_i - {1\over m}\sum _{i=1}^{2m}\hat{p}_t^j\right) \\&\quad +\,\pi _j \le (\alpha _m-1){1\over m-j}(mL - j\pi _j) +\pi _j. \end{aligned}$$

The last inequality follows because, as argued above, $j\pi _j \le \sum _{i=1}^{2m}\hat{p}_t^i$. It follows that the machine load is upper bounded by

$$\begin{aligned} (\alpha _m-1)\textstyle {1\over m-j}(mL - m\pi _j) +\alpha _m\pi _j \le \alpha _m(L-\pi _j) + \alpha _m\pi _j= \alpha _mL. \end{aligned}$$

The last inequality holds because $m/(m-j) \le \alpha _m/(\alpha _m-1)$, as mentioned above.

If $j> \lfloor m/\alpha _m\rfloor$, then $j\ge m/\alpha _m$ because j is integral. In this case the machine load is upper bounded by

$$\begin{aligned} \beta (j)L^* +\pi _j= & {} \alpha _m\left( \sum _{i=1}^n p_i - \sum _{i=1}^{2m}\hat{p}_t^i\right) /m +\pi _j \le \alpha _m\left( \sum _{i=1}^n p_i- j\pi _j\right) {/}m+\pi _j \le \alpha _m L, \end{aligned}$$

because $j\alpha _m\ge m$.

Finally we consider the jobs $R{\setminus } (P_1\cup \ldots \cup P_m)$. Each job of $R{\setminus } R'$ has a processing time of at most $(\alpha _m-1)L$. As argued above, each job of $R'{\setminus } (P_1\cup \ldots \cup P_m)$ has a processing time of at most ${ O PT}/3$, which is upper bounded by $(\alpha _m-1) OPT$ since $\alpha _m\ge 4/3$. Hence each job of $R{\setminus } (P_1\cup \ldots \cup P_m)$ has a processing time of at most $(\alpha _m-1) OPT$. Each of these jobs is scheduled on a least loaded machine and thus after the assignment the corresponding machine has a load of at most $OPT + (\alpha _m-1) OPT \le \alpha _m OPT$. $\square$

The proof of Theorem 1 is complete.

3 A Lower Bound

We present a lower bound showing that ALG($\alpha _m$) is optimal.

Theorem 2

Let $m\ge 2$. No deterministic online algorithm can achieve a competitive ratio smaller than $\alpha _m$ if o(n) job migrations are allowed.

Proof

Let A be any deterministic online algorithm that is allowed to use up to g(n) job migrations on a job sequence of length n. Suppose that A achieves a competitive ratio smaller than $\alpha _m$. We will derive a contradiction.

Choose an $\epsilon >0$ such that A has a competitive ratio strictly smaller than $\alpha _m-\epsilon$. Let $\epsilon '=\epsilon /3$. Since $g(n)=o(n)$ there exists an $n_0$ such that $g(n)/n \le \epsilon '/(2m)$, for all $n\ge n_0$. Hence there exists an $n_0$ such that $g(n+m)/(n+m) \le \epsilon '/(2m)$, for all $n\ge \max \{m,n_0\}$. Let $n'$, with $n'\ge \max \{m,n_0\}$, be the smallest integer multiple of m. We have $g(n'+m)/n'\le \epsilon '/m$ because $n'+m\le 2n'$. An adversary constructs a job sequence consisting of $n'+m$ jobs. Let $p_1= m/n'$. By our choice of $n'$, there holds $p_1\le \epsilon '/g(n'+m)$. The following adversarial sequence is similar to that used by Englert et al. [8]. However, here we have to ensure that in migrating o(n) jobs, an online algorithm cannot benefit much.

First the adversary presents $n'$ jobs of processing time $p_1$. We will refer to them as $p_1$-jobs. If after the assignment of these jobs A has a machine $M_j$, $1\le j \le m$, whose load is at least $\alpha _m$, then the adversary presents m jobs of processing time $p_2=\epsilon '/m$. Using job migration, A can remove at most $g(n'+m)$ $p_1$-jobs from $M_j$. Since $g(n'+m)p_1\le \epsilon '$, after job migration $M_j$ still has a load of at least $\alpha _m-\epsilon$. On the other hand the optimal makespan is $1+\epsilon '/m$. In an optimal assignment each machine contains $n'/m$ $p_1$-jobs and one $p_2$-job. The ratio $(\alpha _m-\epsilon ')/(1+\epsilon '/m)$ is at least $\alpha _m-\epsilon$ by our choice of $\epsilon '$ and the fact that $\alpha _m\le 2$, see Lemma 1. We obtain a contradiction.

In the following we study the case that after the assignment of the $p_1$-jobs each machine in A’s schedule has a load strictly smaller than $\alpha _m$. We number the machines in order of non-decreasing load such that $\ell (1)\le \ldots \le \ell (m)$. Here $\ell (j)$ denotes the load of $M_j$ after the $p_1$-jobs have arrived, $1\le j\le m$. For $j=1, \ldots , m-1$, define $\beta (j) = (\alpha _m-1)m/(m-j)$. We remark that these values are identical to those used by ALG($\alpha _m$) for $j\le \lfloor m/\alpha _m\rfloor$. For larger j, the values are different. We first argue that there must exist a machine $M_j$, $1\le j\le m-1$, in A’s schedule whose load is at least $\beta (j)$. Suppose that each machine $M_j$, $1\le j\le m-1$, had a load strictly smaller than $\beta (j)$. By Lemma 1, $\alpha _m>1$ and hence $\lceil (1-1/\alpha _m)m\rceil \ge 1$. Consider the $\lceil (1-1/\alpha _m)m\rceil$ machines with the highest load in A’s schedule. Each of these machines has a load strictly smaller than $\alpha _m$. The remaining machines have a load strictly smaller than $\beta (j) = (\alpha _m-1)m/(m-j)$, for $j=1,\ldots , m - \lceil (1-1/\alpha _m)m\rceil$. We conclude that after the arrival of the $p_1$-jobs the total load on the machines is strictly smaller than

$$\begin{aligned}&(\alpha _m-1)m \sum _{j=1}^{m-\lceil (1-1/\alpha _m)m\rceil } {1\over m-j} + \lceil (1-1/\alpha _m)m\rceil \alpha _m\\&\quad = m((\alpha _m-1)(H_{m-1}-H_{\lceil (1-1/\alpha _m)m\rceil -1}) + \lceil (1-1/\alpha _m)m\rceil \alpha _m/m)\\&\quad = mf_m(\alpha _m) = m. \end{aligned}$$

The last equation holds because $f_m(\alpha _m)=1$, by the choice of $\alpha _m$. We obtain a contradiction to the fact that after the arrival of the $p_1$-jobs a total load of exactly m resides on the machines.

Let $M_{j_0}$, with $1\le j_0\le m-1$, be a machine whose load is at least $\beta (j_0)$. Since A’s machines are numbered in order of non-decreasing load there exist at most $j_0-1$ machines having a smaller load than $\beta (j_0)$. The adversary presents $j_0$ jobs of processing time $p_2=m/(m-j_0)$. Using job migration A can remove at most $g(n'+m)$ $p_1$-jobs from any of the machines, thereby reducing the load by at most $\epsilon '$. Hence in A’s final schedule there exists a machine having a load of a least $\beta (j_0)+m/(m-j_0)-\epsilon '$. This holds true if the $p_2$-jobs reside on different machines. If there exists a machine containing two $p_2$-jobs, then its load is at least $2m/(m-j_0)\ge (\alpha _m-1)m/(m-j_0) + m/(m-j_0) = \beta (j_0) + m/(m-j_0)$ as desired. The inequality holds because $\alpha _m\le 2$, by Lemma 1. Hence A’s makespan is at least $\beta (j_0)+m/(m-j_0)-\epsilon '$.

The optimum makespan for the job sequence is upper bounded by $m/(m-j_0)+\epsilon '$. In an optimal schedule the $j_0$ $p_2$-jobs are assigned to different machines. The $n'$ $p_1$-jobs are distributed evenly among the remaining $m-j_0$ machines. If $n'$ is an integer multiple of $m-j_0$, then the load on each of these $m-j_0$ machines is exactly $n'p_1/(m-j_0)= m/(m-j_0)$, which is exactly equal to the processing time of a $p_2$-job. If $n'$ is not divisible by $m-j_0$, then the maximum load on any of these $m-j_0$ machines cannot be higher than $m/(m-j_0)+p_1 \le m/(m-j_0) + \epsilon '/g(n'+m) \le m/(m-j_0) + \epsilon '$.

Dividing the lower bound on A’s makespan by the upper bound on the optimum makespan we obtain $(\alpha _m m/(m-j_0) - \epsilon ')/(m/(m-j_0) + \epsilon ') \ge (\alpha _m-\epsilon ')/(1+\epsilon ')\ge \alpha _m-\epsilon$. The last inequality holds because $\epsilon '=\epsilon /3$ and $\alpha _m\le 2$, see Lemma 1. We obtain a contradiction to the assumption that A’s competitiveness is strictly smaller than $\alpha _m-\epsilon$. $\square$

4 Algorithms Using Fewer Migrations

We present a family of algorithms ALG(c) that uses a smaller number of job migrations. We first describe the family and then analyze its performance.

4.1 Description of ALG(c)

ALG(c) is defined for any constant c with $5/3\le c \le 2$, where c is the targeted competitive ratio. An important feature of ALG(c) is that it partitions the machines $M_1, \ldots , M_m$ into two sets $A=\{M_1, \ldots , M_{\lfloor m/2\rfloor }\}$ and $B=\{M_{\lceil m/2\rceil }, \ldots , M_m\}$ of roughly equal size. In a job arrival phase the jobs are preferably assigned to machines in A, provided that their load it not too high. In the job migration phase, jobs are mostly migrated from machines of A (preferably to machines in B) and this policy will allow us to achieve a smaller number of migrations. Setting $c=5/3$ we obtain an algorithm ALG(5 / 3) that is 5 / 3-competitive using 4m migrations. For $c=1.75$ the resulting algorithm ALG(1.75) is 1.75-competitive and uses at most 2.5m migrations. In the following let $5/3\le c \le 2$.

Algorithm ALG(c): job arrival phase At any time t ALG(c) maintains a lower bound $L_t$ on the optimum makespan, which is defined as $\textstyle {L_t = \max \{{1\over m}p_t^+,p_t^1,2p_t^{m+1}\}}.$ Here we use the same notation as in Sect. 2. Recall that $p_t^1$ and $p_t^{m+1}$ are the processing times of the largest and $(m+1)$-st largest jobs in $J_1, \ldots , J_t$, respectively. A job $J_i$, with $i\le t$, is small at time t if $p_i\le (2c-3)L_t$; otherwise the job is large at time t. For any machine $M_j$ and any time t, $\ell (j,t)$ is $M_j$’s load immediately before $J_t$ is assigned and $\ell _s(j,t)$ is its load consisting of the jobs that are small at time t.

Any job $J_t$, $1\le t\le n$, is processed as follows. If $J_t$ is small at its arrival time t, then ALG(c) checks if there is a machine in A whose load value $\ell _s(j,t)$ is at most $(c-1)L_t$. If this is the case, then among the machines in A with this property, $J_t$ is assigned to one having the smallest $\ell _s(j,t)$ value. If there is no such machine in A, then $J_t$ is assigned to a least loaded machine in B. If $J_t$ is large at time t, then ALG(c) checks if there is machine in A whose load value $\ell (j,t)$ is at most $(3-c)L_t$. If this is the case, then $J_t$ is scheduled on a least loaded machine in A. Otherwise $J_t$ is assigned to a least loaded machine in B. At the end of the phase let $L= L_n$.

Job migration phase At any time during the phase let $\ell (j)$ denote the current load of $M_j$, $1\le j\le m$. We first describe the job removal step. For any machine $M_j\in B$, ALG(c) removes the largest job from that machine. Furthermore, while there exists a machine $M_j\in A$ whose current load exceeds $(c-1)L$, ALG(c) removes the largest job from the machine. Let R be the set of all removed jobs. In the job reassignment step ALG(c) first sorts the jobs in order of non-increasing processing times. For any i, $1\le i \le |R|$, let $J_r^i$ be the i-th largest job in this sequence, and let $p_r^i$ be the corresponding processing time. For $i=1, \ldots , |R|$, $J_r^i$ is scheduled as follows. If there exists a machine $M_j\in B$ such that $\ell (j)+p_r^i\le cL$, i.e. $J_r^i$ can be placed on $M_j$ without exceeding a makespan of cL, then $J_r^i$ is assigned to this machine. Otherwise the job is scheduled on a least loaded machine in A. A pseudo-code description of ALG(c) is given in Fig. 2.

Fig. 2

The algorithm ALG(c)

Theorem 3

ALG(c) is c-competitive, for any constant c with $5/3\le c\le 2$.

The proof of the above theorem is presented in Sect. 4.2.1. In order to obtain good upper bounds on the number of job migrations, we focus on specific values of c. First, set $c=5/3$. In ALG(5/3) a job $J_t$ is small if $p_t \le 1/3\cdot L_t$. In the arrival phase a small job is assigned to a machine in A if there exists a machine in this set whose load consisting of jobs that are currently small is at most $2/3\cdot L_t$. A large job is assigned to a machine in A if there exists a machine in this set whose load is at most $4/3 L_t$.

Theorem 4

ALG(5/3) is ${5\over 3}$-competitive and uses at most 4m job migrations.

In fact, for any c with $5/3\le c \le 2$, ALG(c) uses at most 4m job migrations. Finally, let $c=1.75$. In ALG(1.75) a job $J_t$ is small if $p_t \le 0.5\cdot L_t$. In the arrival phase a small job is assigned to a machine in A if there is a machine in this set whose load consisting of jobs that are currently small is no more than $0.75 L_t$. A large job is assigned to a machine in A if there exists a machine in this set whose load is at most $1.25 L_t$.

Theorem 5

ALG(1.75) is 1.75-competitive and uses at most 2.5m job migrations.

Again, for any c with $1.75\le c \le 2$, ALG(c) uses at most 2.5m job migrations. The proofs of Theorems 4 and 5 are contained in Sect. 4.2.2.

4.2 Analysis of ALG(c)

In this section we analyze ALG(c), for any c with $5/3\le c \le 2$, and prove Theorems 3, 4 and 5. We first determine the competitive ratio of ALG(c) and then bound the number of job migrations performed for $c=5/3$ and $c=1.75$.

4.2.1 Analysis of the Competitive Ratio

We start by showing two lemmas that will allow us to bound load on machines in B. The lemmas will be applied depending on the final loads of small jobs residing on machines in A. In particular, for any time t, Lemma 6 bounds the load of any machine in B when ignoring the last job assigned to that machine. Again, let time $n+1$ be the time when the entire job sequence $\sigma =J_1, \ldots , J_n$ has been scheduled and the migration phase starts. A job $J_i$, $1\le i\le n$, is small at time $n+1$ if $p_i\le (2c-3)L= (2c-3)L_n$; otherwise the job is large at time $n+1$. For any $M_j$, $1\le j\le m$, let $\ell (j,n+1)$ be its load at time $n+1$ and let $\ell _s(j,n+1)$ be the load consisting of the jobs that are small at time $n+1$. Let $L_{n+1}:=L$.

Lemma 6

For any t, $1\le t\le n+1$, and any $M_j\in B$, there holds $\ell (j,t)-p_l\le (3-c)L_{t-1}$, where $J_l$ with $l<t$ is the last job assigned to $M_j$.

Proof

By the definition of ALG(c), when $J_l$ is assigned to $M_j$, all machines of A have a load greater than $(c-1)L_l$ and $M_j$ is a least loaded machine in B. Hence $M_j$’s load at time l is at most $(3-c)L_l$ since otherwise the total load on the m machines would be greater than $\lfloor m/2\rfloor (c-1) L_l+\lceil m/2\rceil (3-c) L_l \ge mL_l\ge \sum _{i=1}^l p_i$, which is a contradiction. Hence $\ell (j,t) = \ell (j,l)+p_l \le (3-c)L_l+p_l \le (3-c)L_{t-1}+p_l$. $\square$

Lemma 7

Suppose that there exists a machine $M_{j^*}\in A$ with $\ell _s(j^*,n+1)< (2-c)L$. Then, for any $B\in M_j$, $\ell (j,n+1)-p_l \le (c-1)L$, where $J_l$ is the last job assigned to $M_j$.

Proof

Consider any $M_j\in B$ and let $J_l$ be the last job assigned to it. First assume that $J_l$ is large at time l. By the definition of ALG(c), at time l all machines of A have a load greater than $(3-c) L_l$. Moreover, $M_j$ is a least loaded machine in B at time l. We argue that a least loaded machine in B has a load of at most $(c-1) L_l$. If this were not the case, then immediately after the assignment of $J_l$ the total load on the m machines would be greater than $\lfloor m/2\rfloor (3-c) L_l+\lceil m/2\rceil (c-1) L_l +p_l \ge (m/2-1/2) (3-c)L_l + (m/2+1/2) (c-1) L_l +(2c-3)L_l = mL_l + (3c-5)L_l$. The inequality holds because $3-c \ge c-1$. Since $c \ge 5/3$ it follows $\lfloor m/2\rfloor (3-c) L_l+\lceil m/2\rceil (c-1) L_l +p_l \ge mL_l \ge \sum _{i=1}^l p_i$, which is a contradiction. Hence $\ell (j,n+1) = \ell (j,l)+p_l \le (c-1)L_l+p_l \le (c-1)L+p_l$.

Next assume that $J_l$ is small at time l. This implies $\ell _s(j,l) > (c-1)L_l$, for all $M_j\in A$. In particular, $\ell _s(j^*,l) > (c-1)L_l$. Since $\ell _s(j^*,l)\le \ell _s(j^*,n+1)< (2-c) L$ it follows $L_l < (2-c)/(c-1)\cdot L$. By Lemma 6, $\ell (j,l+1)\le (3-c)L_l+p_l$ and we conclude $\ell (j,n+1)= \ell (j,l+1)\le (3-c)L_l+p_l\le (3-c)(2-c)/(c-1)\cdot L+p_l \le (c-1) L+p_l$. The last inequality holds because $(3-c)(2-c)/(c-1)\le c-1$ holds since $c\ge 5/3$. $\square$

We next analyze the job migration phase assuming that the job removal step has already taken place, i.e. each machine of A has a load of at most $(c-1)L$ and the largest job was removed from each machine of B. We show that, given such a machine configuration, each job of R can be assigned to a machine so that a load bound of cL is preserved. For the analysis of the reassignment step we study two cases depending on whether or not at time $n+1$ all machines $M_j\in A$ have a load $\ell _s(j,n+1)\ge (2-c) L$.

Lemma 8

If $\ell _s(j,n+1)\ge (2-c) L$, for all $M_j\in A$, then in the reassignment step all jobs of R are scheduled so that the resulting load on any of the machines is at most cL.

Proof

By assumption, at the end of the job arrival phase $\ell _s(j,n+1)\ge (2-c)L$, for all $M_j\in A$. We first show that this property is maintained throughout the job removal step. Suppose that a job $J_i$ that is small at time $n+1$ is removed from a machine $M_j\in A$. Since ALG(c) always removes the largest jobs from a machine, $M_j$ currently contains no jobs that are large at time $n+1$. Hence $M_j$’s current load $\ell (j)$ is equal to its current load $\ell _s(j)$ consisting of jobs that are small at time $n+1$. Since a job removal needs to be performed, $\ell _s(j) = \ell (j)> (c-1) L$. Since $p_i \le (2c-3) L$, the removal of $J_i$ leads to a load consisting of small jobs of at least $\ell _s(j) -p_l > (c-1) L - (2c-3) L = (2-c)L$.

After the job removal step each machine $M_j\in A$ has a load of at most $(c-1) L$. By Lemma 6 each machine of B has a load of at most $(3-c) L<cL$ after ALG(c) has removed the largest job from any of these machines. We show that each $J_k\in R$ can be scheduled on a machine such that the resulting load is at most cL. Consider any $J_k\in R$. There holds $p_k\le L$. Suppose that $J_k$ cannot be feasibly scheduled on any of the machines. Let $\ell (j)$ denote $M_j$’s load immediately before the assignment of $J_k$, $1\le j\le m$. If $J_k$ cannot be placed on a machine in A, then each machine $M_j\in A$ must have a load greater than $(c-1) L$: If $\ell (j)\le (c-1) L$, then $\ell (j) + p_k\le c L$ and the assignment of $J_k$ to $M_j$ would be feasible. Hence since the start of the reassignment step each machine $M_j\in A$ must have received at least one job $J_{i_j}$ and its current load is $\ell (j) \ge (2-c) L + p_{i_j}$. When $J_{i_j}$ was reassigned, it could not be scheduled on any machine in B without exceeding a load of cL. This implies, in particular, that $\ell (\lfloor m/2\rfloor +j) + p_{i_j} > c L$. Recall that the machines of A are numbered $1, \ldots , \lfloor m/2\rfloor$ and those of B are numbered $\lfloor m/2\rfloor +1, \ldots , m$. Finally, since $J_k$ cannot be placed on a machine in B, we have $\ell (m) + p_k > c L$.

It follows that when $J_k$ has to be scheduled the total processing time of the jobs is at least

$$\begin{aligned} \sum _{j=1}^m \ell (j) + p_k \ge \lfloor m/2\rfloor (2-c) L + \sum _{j=1}^{\lfloor m/2\rfloor } p_{i_j} + \sum _{j=\lfloor m/2\rfloor +1}^m \ell (j) + p_k. \end{aligned}$$

If m is even, then $\sum _{j=\lfloor m/2\rfloor +1}^m \ell (j) = \sum _{j=1}^{m/2} \ell (m/2 +j)$. In this case we have

$$\begin{aligned}&\sum _{j=1}^m \ell (j) + p_k \ge m/2 \cdot (2-c)L\\&\quad +\,\sum _{j=1}^{m/2} (\ell (m/2 +j) +p_{i_j}) + p_k > m/2 \cdot (2-c) L + m/2\cdot c L \ = \ mL. \end{aligned}$$

If m is odd, then $\sum _{j=\lfloor m/2\rfloor +1}^m \ell (j) = \sum _{j=1}^{\lfloor m/2\rfloor } \ell (\lfloor m/2\rfloor +j)+ \ell (m)$ and

$$\begin{aligned} \sum _{j=1}^m \ell (j) + p_k\ge & {} \lfloor m/2\rfloor \cdot (2-c) L + \sum _{j=1}^{\lfloor m/2\rfloor } (\ell (\lfloor m/2\rfloor +j)+p_{i_j}) + \ell (m)+ p_k\\>&\lfloor m/2\rfloor \cdot (2-c) L + \lfloor m/2\rfloor \cdot c L + c L\\= & {} (m/2 - 1/2)2L + c L \ > \ mL. \end{aligned}$$

In both cases with obtain $\sum _{i=1}^n p_i \ge \sum _{j=1}^m \ell (j) + p_k > mL$, which contradicts the definition of L. $\square$

Lemma 9

If $\ell _s(j^*,n+1)< (2-c) L$, for some $M_{j^*}\in A$, then in the reassignment step all jobs of R are scheduled so that the resulting load on any of the machines is at most cL.

Proof

In the removal step ALG(c) removes the largest job from each machine $M_j\in B$. Hence, if $\ell _s(j^*,n+1)< (2-c) L$ for some $M_j\in A$, then by Lemma 7 each machine of B has a load of at most $(c-1)L$ after the removal step. Moreover, each machine of A has a load of at most $(c-1)L$ after the job removal.

Hence when the reassignment step starts, all machines have a load of at most $(c-1) L$. By the definition of L each job has a processing time of at most L. Hence in the reassignment step the first m jobs can be scheduled without exceeding a load of cL on any of the machines. ALG(c) sorts the jobs of R in order of non-increasing processing times. Thus when m jobs of R have been scheduled, each of the remaining jobs has a processing time of at most 1 / 2L. This holds true because by the definition of L there cannot exist $m+1$ jobs of processing time greater than 1 / 2L. Each job of processing time at most 1 / 2L can be scheduled on a least loaded machine without exceeding a load of cL since $L+ 1/2 L < cL$. Hence every remaining job can be scheduled on a machine of B and A. $\square$

Lemmas 8 and 9 imply Theorem 3.

4.2.2 Analysis of the Job Migrations

It remains to evaluate the number of job removals in the job migration phase. ALG(c) removes one job from each machine in B. Hence, in the following we analyze the number of jobs removed by ALG(c) from any machine in A. To this end we consider the final machine loads consisting of small jobs.

Lemma 10

Let $M_j\in A$. If $\ell _s(j,n+1)\le (c-1)L$ or if $\ell _s(j,n+1)> (c-1)L$ and $\ell _s(j,n)\le (c-1)L_n$, then ALG(c) removes less than $(3-c)/(2c-3) +2$ jobs from $M_j$.

Proof

We show that it suffices to remove less than $(3-c)/(2c-3) +2$ jobs from $M_j$ such that the resulting load is upper bounded by $(c-1)L$. The lemma then follows because in each removal operation ALG(c) removes the largest job.

First assume that $\ell _s(j,n+1)\le (c-1)L$. In this case it suffices to remove all jobs that are large at time $n+1$. Each such job has a processing time greater than $(2c-3)L$ and was large at the time it was assigned to $M_j$. Consider the last time when such a job was assigned to $M_j$. At that time $M_j$ had a load of at most $(3-c)L$ and hence contained less than $(3-c)/(2c-3)$ jobs of processing time greater than $(2c-3)L$. Thus at time $n+1$ machine $M_j$ contains less than $(3-c)/(2c-3)+1$ of these large jobs.

Next assume $\ell _s(j,n+1)> (c-1)L$ and $\ell _s(j,n)\le (c-1)L_n$. The latter inequality implies that $J_n$ is assigned to $M_j$ because $L=L_n$. Hence it suffices to remove $J_n$ and, as shown in the last paragraph, less than $(3-c)/(2c-3)+1$ additional jobs of processing time greater than $(2c-3) L_n = (2c-3)L$. $\square$

In the following we concentrate on a machine $M_j\in A$ such that $\ell _s(j,n+1)> (c-1)L$ and $\ell _s(j,n)> (c-1)L_n$. Let $t^*$ be the earliest time such that $\ell _s(j,t)> (c-1)L_t$ holds for all times $t\ge t^*$. We have $t^*>1$ because $\ell _s(j,0)=0$. We partition the jobs that reside on $M_j$ at time $n+1$ into three sets. Set $T_1$ (set $T_2$) contains those jobs that were assigned to $M_j$ at or before time $t^*-1$ are small (large) at time $t^*-1$. Set $T_3$ contains the remaining jobs, which have arrived at or after time $t^*$.

Claim 1

Each job of $T_2\cup T_3$ is large at the time it is assigned to $M_j$.

Claim 2

There holds $\sum _{J_i\in T_1{\setminus }\{J_l\}} p_i \le (c-1) L_{t^*-1}$, where $J_l$ is the job of $T_1$ that was assigned last to $M_j$.

Claim 3

$|T_2|$ is smaller than $(3-c)/(2c-3)+1$.

Claim 4

For any $J_l\in T_3$, $M_j$’s load immediately before the assignment of $J_l$ is at most $(3-c) L_l$.

Claim 5

Let $J_l\in T_3$ be the last job assigned to $M_j$. If $M_j$ contains at least $\lceil 12(2-c)\rceil$ jobs, different from $J_l$, each having a processing time of at least 1 / 6L, then it suffices to remove these $\lceil 12(2-c)\rceil$ jobs and $J_l$ such that $M_j$’s resulting load is upper bounded by $(c-1)L$.

Proof of Claim 1

The jobs of $T_2$ are large at time $t^*-1$ and hence at the time they were assigned to $M_j$. By the definition of $t^*$, $\ell _s(j,t)> (c-1) L_t$, for any $t^*\le t \le n$, and hence ALG(c) does not assign small jobs to $M_j$. $\square$

Proof of Claim 2

By the choice of $t^*$, all jobs of $T_1{\setminus }\{J_l\}$ are small at time $t^*-1$ and their total processing time is at most $\ell _s(j,t^*-1)\le (c-1) L_{t^*-1}$. $\square$

Proof of Claim 3

Each job of $T_2$ has a processing time greater than $(2c-3) L_{t^*-1}$. Consider the last time l when a job $J_l\in T_2$ was assigned to $M_j$. Before the assignment, $M_j$ had a load of at most $(3-c) L_{t^*-1}$ and hence contained less than $(3-c)/(2c-3)$ jobs of processing time greater than $(2c-3) L_{t^*-1}$. $\square$

Proof of Claim 4

Consider any $J_l\in T_3$. By Claim 1 $J_l$ is large at time l and hence $M_j$’s load prior to the assignment of $J_l$ is at most $(3-c)L_l$. $\square$

Proof of Claim 5

By Claim 4 $M_j$’s load immediately before the assignment of $J_l$ is at most $(3-c)L_l$. Removing $\lceil 12(2-c)\rceil$ jobs of processing time at least 1 / 6L each as well as $J_l$ reduces $M_j$’s load to a value of at most $(3-c)L_l-12(2-c)/6\cdot L \le (c-1)L$. $\square$

We are ready to analyze ALG(5 / 3).

Lemma 11

In the removal step ALG(5 / 3) removes at most seven jobs from each machine $M_j\in A$.

Proof

Consider any $M_j\in A$. If $\ell _s(j,n+1)\le (c-1)L$ or if $\ell _s(j,n+1)> (c-1)L$ and $\ell _s(j,n)\le (c-1)L_n$, then by Lemma 10 ALG(5 / 3) removes less than $(3-c)/(2c-3) +2=6$ jobs from $M_j$. In the remainder of this proof we assume that $\ell _s(j,n+1)> (c-1)L$ and $\ell _s(j,n)> (c-1)L_n$. In this case Claims 1–5 hold. We need two additional statements.

Claim 6

If there exists a $J_l\in T_3$ with $p_l<1/6L$, then $M_j$’s load immediately before the assignment of $J_l$ is at most $(c-1)L=2/3L$.

Claim 7

If there exists a $J_k\in T_2$ with $p_k<1/6L$, then $\sum _{J_i\in T_1}p_i + p_k\le (c-1)L=2/3L$.

Proof of Claim 6

By Claim 1 $J_l$ is large at time l and hence $p_l> (2c-3)L_l=1/3 L_l$. Since $p_l<1/6L$, we have $L_l<1/2L$. By Claim 4, $M_j$’s load immediately before the assignment of $J_l$ is at most $(3-c)L_l=4/3 L_l$ and hence at most 2 / 3L. $\square$

Proof of Claim 7

Job $J_k$ is large at time $t^*-1$ and hence $p_k > (2c-3) L_{t^*-1} = 1/3 L_{t^*-1}$. Since $p_k < 1/6 L$ it follows $L_{t^*-1} < 1/2 L$. By Claim 2, we have $\sum _{J_i\in T_1} p_i \le (c-1) L_{t^*-1} + p_l$, where $J_l$ is the last job of $T_1$ assigned to $M_j$. Since $p_l$ is small at time $t^*-1$ we have $p_l \le (2c-3) L_{t^*-1} =1/3 L_{t^*-1} < 1/6 L$. In summary $\sum _{J_i\in T_1} p_i + p_k \le 1/3L + 1/6 L + 1/6 L = 2/3 L$. $\square$

We distinguish two cases.

Case 1: Suppose that $|T_2\cup T_3|\le 4$. By Claim 2 it suffices to remove the jobs of $T_2\cup T_3$ and the last job of $T_1$ assigned to $M_j$.

Case 2: Assume $|T_2\cup T_3|\ge 5$. Then by Claim 3 $|T_2|$ is smaller than $(3-c)/(2c-3)+1=5$. Thus $|T_2|\le 4$ and $T_3\ne \emptyset$. Let $J_l$ be the last job of $T_3$ assigned to $M_j$. If $T_2\cup T_3{\setminus } \{J_l\}$ contains at least $\lceil 12(2-c)\rceil =4$ jobs of processing time at least 1 / 6L, then by Claim 5 it suffices to remove these four jobs and $J_l$. So suppose that this is not the case. Then $T_2\cup T_3{\setminus } \{J_l\}$ must contain a job of processing time smaller than 1 / 6L.

Assume there exists a job in $T_3{\setminus } \{J_l\}$ with this property. Then let $J_{l'}$ be the last job assigned to $M_j$ having a processing time smaller than 1 / 6L. By Claim 6, immediately before the assignment of $J_{l'}$ machine $M_j$ has a load of at most 2 / 3L. Therefore it suffices to remove $J_{l'}$ and the jobs of $T_3$ subsequently scheduled on $M_j$. In addition to $J_l$, this sequence consists of at most three jobs $J_k\ne J_l$, because $T_3{\setminus } \{J_l\}$ contains less than four jobs of processing time at least 1 / 6L.

Finally consider the case that all jobs of $T_3{\setminus } \{J_l\}$ have a processing time of at least 1 / 6L and there is a job $J_{l'}\in T_2$ having a processing time smaller than 1 / 6L. By Claim 7 it suffices to remove $T_2{\setminus } \{J_{l'}\}\cup T_3$. By Claim 3 we have $|T_2{\setminus } \{J_{l'}\}| \le 3$. Since $T_3{\setminus } \{J_l\}$ contains less than four jobs, each having a processing time of at least 1 / 6L, we have $|T_3|\le 4$. We conclude that at most seven jobs have to be removed. $\square$

Lemma 11 ensures that in the job removal step ALG(5 / 3) removes at most 7 jobs from any machine in A. For any machine in B, one job is removed. Hence the total number of migrations is at most $7\lfloor m/2 \rfloor + \lceil m/2 \rceil \le 4m$. Combined with Theorem 3, this concludes the proof of Theorem 4. We next turn to the algorithm ALG(1.75).

Lemma 12

In the job removal step ALG(1.75) removes at most four jobs from each machine $M_j\in A$.

Proof

Let $M_j$ be any machine in A. If $\ell _s(j,n+1)\le (c-1)L$ or if $\ell _s(j,n+1)> (c-1)L$ and $\ell _s(j,n)\le (c-1)L_n$, then by Lemma 10 ALG(1.75) removes less than $(3-c)/(2c-3) +2=4.5$ jobs from $M_j$. Therefore, we focus on the case that $\ell _s(j,n+1)> (c-1)L$ and $\ell _s(j,n)> (c-1)L_n$. Again, Claims 1–5 hold and we need two additional claims.

Claim 8

If there exists a $J_l\in T_3$ with $p_l<1/6L$, then $M_j$’s load immediately after the assignment of $J_l$ is at most $(c-1)L=0.75L$.

Claim 9

If $T'_2\subseteq T_2$ is a subset with $1\le |T_2|\le 2$ and $p_i\le 1/6L$, for all $J_i\in T_2$, then $\sum _{J_i\in T_1}p_i + \sum _{J_i\in T'_2}p_i\le (c-1)L=0.75L$.

Proof of Claim 8

By Claim 1 $J_l$ is large at time l and hence $p_l> (2c-3)L_l = 0.5 L_l$. Since $p_l<1/6L$, we have $L_l<1/3L$. Using Claim 4 we obtain that $M_j$’s load immediately after the assignment of $J_l$ is at most $(3-c)L_l +p_l = 1.25 L_l + p_l \le 5/12 L + 1/6L < 0.75L$. $\square$

Proof of Claim 9

Any job $J_i\in T'_2$ is large at time $t^*-1$ and hence $p_i > (2c-3)L_{t^*-1} = 0.5 L_{t^*-1}$. Since $p_i < 1/6 L$ it follows $L_{t^*-1} < 1/3 L$. By Claim 2, we have $\sum _{J_i\in T_1} p_i \le 0.75 L_{t^*-1} + p_l\le 0.25L + 1/6 L$, where $J_l$ is the last job of $T_1$ assigned to $M_j$. Thus $\sum _{J_i\in T_1}p_i + \sum _{J_i\in T'_2}p_i\le 0.25L + 3\cdot 1/6L\le 0.75L$. $\square$

We finish the proof of the lemma using a case distinction on the size of $T_3$. By Claim 3, $T_2$ contains no more than three jobs. Moreover, $\lceil 12(2-c)\rceil = 3$, which is a quantity used in Claim 5.

• $|T_3|=0$: Then by Claim 2 is suffices to remove $T_2$ and the last job of $T_1$ assigned to $M_j$.

• $|T_3|= 1$: We may assume that the only job $J_l\in T_3$ has a processing time of at least 1 / 6L since otherwise by Claim 8 no job has to be removed. Moreover, we may assume that $|T_2|=3$ since otherwise, by Claim 2 it suffices to remove $T_2\cup T_3$ and the last job of $T_1$ assigned to $M_j$. If all the jobs of $T_2$ have a processing time of at least 1 / 6L, then Claim 5 ensures that it suffices to remove $T_2\cup T_3$. If one job in $T_2$ has a processing time of at most 1 / 6L, then Claim 9 ensures that it suffices to remove the other two jobs of $T_2$ and $T_3$.

• $|T_3|= 2$: We assume that both jobs in $T_3$ have a processing time of at least 1 / 6L since otherwise, by Claim 8, we can just remove one job of $T_3$ and $T_2$. If $|T_2|=1$, then by Claim 2 it suffices to remove $T_2\cup T_3$ and the last job of $T_1$ assigned to $M_j$. It remains to consider the case $|T_2|\ge 2$. If none of the jobs in $T_2$ has a processing time smaller than 1 / 6L, then Claim 5 applies. If one of the jobs has a processing time smaller than 1 / 6L, then Claim 9 applies and it suffices to remove the at most two other jobs of $T_2$ and the jobs of $T_3$.

• $|T_3|= 3$: Again we assume that all jobs in $T_3$ have a processing time of at least 1 / 6L since otherwise the desired statement follows from Claim 8. Moreover, we assume $|T_2|>0$; otherwise we can apply again Claim 2. If there is one job in $T_2$ having a processing time of at least 1 / 6L, the desired number of job removals follows from Claim 5. If this is not the case, then Claim 9 ensures that it suffices to remove the last job of $T_2$ assigned to $M_j$ as well as $T_3$.

• $|T_3|\ge 4$: If four jobs in $T_3$ have a processing time of at least 1 / 6L, then by Claim 5 it is sufficient to remove these four jobs. If at most three jobs have a processing time of at least 1 / 6L, then let $J_l\in T_3$ be last jobs assigned to $M_j$ having a processing time smaller than 1 / 6L. By Claim 8 it suffices to remove the jobs of $T_3$ subsequently assigned to $M_j$, and there exist at most three of these.

This concludes the proof. $\square$

Recall that ALG(1.75) migrates $\lceil m/2\rceil$ jobs from machines in B. Hence, using the above Lemma 12, we obtain that the total number of migrations is at most $4\lfloor m/2\rfloor + \lceil m/2\rceil \le 2.5m$. Combined with Theorem 3, this finishes the proof of Theorem 5.

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

$$\begin{aligned} f_m(\alpha )= & {} (\alpha -1)(H_{m-1}-H_{\lceil (1-1/\alpha )m\rceil -1}) + \lceil (1-1/\alpha )m\rceil \alpha /m\\ f_m(\alpha -\epsilon )= & {} (\alpha -\epsilon -1)(H_{m-1}-H_{\lceil (1-1/\alpha )m\rceil -1}) + \lceil (1-1/\alpha )m\rceil (\alpha -\epsilon )/m\\ f_m(\alpha +\epsilon )= & {} (\alpha +\epsilon -1)(H_{m-1}-H_{\lceil (1-1/\alpha )m\rceil -1}) + \lceil (1-1/\alpha )m\rceil (\alpha +\epsilon )/m. \end{aligned}$$

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

$$\begin{aligned} f_m(\alpha )= & {} (\alpha -1)(H_{m-1}-H_{\lceil (1-1/\alpha )m\rceil -1}) + \lceil (1-1/\alpha )m\rceil \alpha /m\\ f_m(\alpha -\epsilon )= & {} (\alpha -\epsilon -1)(H_{m-1}-H_{\lceil (1-1/\alpha )m\rceil -1}) + \lceil (1-1/\alpha )m\rceil (\alpha -\epsilon )/m\\ f_m(\alpha +\epsilon )= & {} (\alpha +\epsilon -1)(H_{m-1}-H_{\lceil (1-1/\alpha )m\rceil }) + (\lceil (1-1/\alpha )m\rceil +1) (\alpha +\epsilon )/m. \end{aligned}$$

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

$$\begin{aligned} f_m(\alpha +\epsilon ) - f_m(\alpha )= & {} -(\alpha -1)\cdot 1/((1-1/\alpha )m) + \epsilon (H_{m-1}-H_{\lceil (1-1/\alpha )m\rceil })\\&+ (\lceil (1-1/\alpha )m\rceil +1) \epsilon /m + \alpha /m\\= & {} \epsilon (H_{m-1}-H_{\lceil (1-1/\alpha )m\rceil }) + (\lceil (1-1/\alpha )m\rceil +1) \epsilon /m. \end{aligned}$$

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

$$\begin{aligned} f_m(\alpha )= & {} (\alpha -1)(H_{m-1}-H_{\lceil (1-1/\alpha )m\rceil -1}) + \lceil (1-1/\alpha )m\rceil \alpha /m\\ f_{m-1}(\alpha )= & {} (\alpha -1)(H_{m-2}-H_{\lceil (1-1/\alpha )m\rceil -1}) + \lceil (1-1/\alpha )m\rceil \alpha /(m-1). \end{aligned}$$

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

$$\begin{aligned} f_m(\alpha )= & {} (\alpha -1)(H_{m-1}-H_{\lceil (1-1/\alpha )m\rceil -1}) + \lceil (1-1/\alpha )m\rceil \alpha /m\\ f_{m-1}(\alpha )= & {} (\alpha -1)(H_{m-2}-H_{\lceil (1-1/\alpha )m\rceil -2}) + (\lceil (1-1/\alpha )m\rceil -1) \alpha /(m-1). \end{aligned}$$

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

$$\begin{aligned} \textstyle {f_{m-1}(\alpha ) - f_m(\alpha ) = -{\alpha -1\over m-1} + {\alpha -1\over \lceil (1-1/\alpha )m\rceil -1} + \lceil (1-1/\alpha )m\rceil {\alpha \over m(m-1)} - {\alpha \over m-1}.} \end{aligned}$$

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

$$\begin{aligned} \textstyle {f_{m-1}(\alpha ) - f_m(\alpha )}= & {} \textstyle { -{\alpha -1\over m-1} + {\alpha -1\over (1-1/\alpha )m +x-1} + (1-1/\alpha )m {\alpha \over m(m-1)} + {\alpha x\over m(m-1)}- {\alpha \over m-1}}\\= & {} \textstyle {{\alpha -1\over (1-1/\alpha )m +x-1} + {\alpha x\over m(m-1)}- {\alpha \over m-1}} \end{aligned}$$

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

$$\begin{aligned} \textstyle {{\alpha -1\over (1-1/\alpha )m +x-1} \ge {\alpha (m-x)\over m(m-1)}.} \end{aligned}$$

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

$$\begin{aligned} 0< H_m - \frac{1}{2} \ln \left( m(m+1) \right) -\gamma < \frac{1}{6m(m+1)}, \end{aligned}$$

(1)

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$,

$$\begin{aligned} H_{m-1} - H_{\lceil cm \rceil -2 }> & {} \frac{1}{2} \ln ((m-1)m) + \gamma - \frac{1}{2} \ln ((\lceil cm \rceil -2)(\lceil cm\rceil -1))\\&-\gamma - \frac{1}{6(\lceil cm \rceil -2)(\lceil cm \rceil -1)}\\\ge & {} \frac{1}{2} \left( \ln (m-1)+ \ln m - \ln (cm -1) - \ln ( cm) \right) - \frac{1}{2(\lceil cm \rceil -1)} \\= & {} \frac{1}{2} \left( \ln (m-1)+ \ln m - \ln (c(m-1/c)) - \ln (cm) \right) - \frac{1}{2(\lceil cm \rceil -1)} \\= & {} \frac{1}{2} \left( \ln (m-1) - \ln (m-1/c) -2 \ln (c) \right) - \frac{1}{2(\lceil cm \rceil -1)} \\\ge & {} \frac{1}{2} \left( 2 \ln (1/c) \right) - \frac{1}{2(\lceil cm \rceil -1)} \\\ge & {} \ln (1/c) - \frac{1}{2(cm-1)}, \end{aligned}$$

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

$$\begin{aligned} f_m(\alpha )= & {} (\alpha -1)(H_{m-1}-H_{\lceil (1-1/\alpha )m \rceil -1}) + \left( \lceil (1-1/\alpha )m \rceil \right) \frac{\alpha }{m} \\> & {} (\alpha -1)\left( \ln (\frac{\alpha }{\alpha -1}) - \frac{1}{2((1-1/\alpha )m -1)} - \frac{1}{\lceil (1-1/\alpha )m \rceil -1} \right) \\&+ \left( \lceil (1-1/\alpha )m \rceil \right) \frac{\alpha }{m} \\\ge & {} (\alpha -1)\left( \ln \left( \frac{\alpha }{\alpha -1}\right) - \frac{1}{(1-1/\alpha )m -1} \right) + \alpha -1 =: F(m). \end{aligned}$$

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

$$\begin{aligned} \frac{\alpha }{\alpha -1} \cdot e = e^\frac{1}{\alpha -1}. \end{aligned}$$

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$