Robust Scheduling Against Machine Failures

1 Introduction

Scheduling is a fundamental problem in operations research and computer science. The classical makespan-minimization problem asks for an assignment of jobs to machines that minimizes the completion time of the last job. Modern largescale systems often face incomplete information or uncertainty: jobs may arrive over time (online scheduling [Albers and Hellwig, 2017]), processing times may be revealed only upon completion (non-clairvoyant scheduling [Motwani et al., 1994; Lindermayr and Megow, 2025]), or processing times may be random with known distributions (stochastic scheduling [Ni˜no-Mora, 2009]).

Beyond job-side uncertainty, the machine environment may also be uncertain. Stein and Zhong [2020] considered a robust scheduling problem where the number of machines is unknown a priori. The scheduler first packs jobs into bags; once the number of machines is revealed, it assigns the bags to machines. A generalized model with different machine speeds was studied in [Eberle et al., 2023; Minar´ık and Sgall, 2024].

Following this line of work, we investigate a robust scheduling problem motivated by unreliable machine environments. We adopt the framework of Recoverable Robustness [Liebchen et al., 2009]. Specifically, we are given a set of m identical machines M and a set of n jobs J , with a known processing time pj for each job j ∈ J , and a parameter k. The goal is to assign jobs to machines so as to minimize the makespan while anticipating potential machine failures. We call this assignment the initial schedule. The parameter k is a known upper bound on the number of failures: after the scheduler commits an initial schedule, up to k machines may fail simultaneously, as decided by an adversary. Throughout, we focus on the nontrivial range 1 ≤ k ≤ m- 1, so that at least one machine remains available after failures. The scheduler then reassigns only the jobs initially on the failed machines to the available machines, minimizing the makespan after reassignment. Jobs initially assigned to available machines remain fixed. See Figure 1 for an illustration. This captures settings where reassignment is costly (e.g., cloud computing, where migrating running virtual machines is expensive [Rani et al., 2025]) or where changing jobs on available machines is undesirable (e.g., railway planning [Lusby et al., 2018]).

We formalize this setting through two adversary models.

The Strong Adversary. An adversary selects the specific set of failed machines M′ ⊂ M. This captures settings where the initial schedule corresponds to a physical allocation of resources (e.g., machinery or hardware) that cannot be reconfigured freely.

The Weak Adversary. The adversary decides only the number of failed machines k′ ≤ k, while the scheduler selects which machines to remove. This models elastic scale-in in cloud computing (e.g., AWS Auto Scaling), where a system manager must reduce the active cluster size by k′ nodes but may choose the least disruptive nodes to drain and shut down.

In both models, a scheduler (or an algorithm) ALG consists of two components: an initial schedule and reassignment rules for each possible scenario of machine failures. We measure performance by a robustness ratio, analogous to the competitive ratio in online algorithms.

EvaluationwithRobustness Ratio. Intuitively, the robustness ratio compares our recovered schedule with an optimal schedule that knows the failure scenario in advance. For each 1 ≤ i ≤ m, let OPTi be the optimal makespan when we use only i machines to complete all jobs. Fix an initial schedule S and a subset of machinesM′ ⊂M. Let ALG(S,M′ ) denote the makespan of a new schedule obtained from S by reassigning jobs from the failed machinesM′ to the available machinesM\M′ using the reassignment rules of ALG.

In the strong adversary model, an algorithm ALG is ρrobust if for any instance, its initial schedule and its reassignment rules can guarantee that

That is, for every failure scenario, ALG can reassign jobs to the available machines and obtain a makespan at most ρ times the optimal makespan. When the reassignment rules are clear from context, we also say that the initial schedule S is ρrobust.

Similarly, in the weak adversary model, an algorithm ALG is ρ-robust if for any instance, its initial schedule and its reassignment rules can guarantee that

That is, the adversary decides only the number of failed machines (the outer "max"), while the scheduler chooses which machines are treated as failed (the inner "min"). For each possible number of failed machines, ALG can choose which machines to treat as failed and then reassign jobs to achieve a makespan at most ρ times the optimal makespan.

1.1 Our Contributions and Techniques

We study robust scheduling with up to k machine failures under both adversary models. Table 1 summarizes our results. Our algorithms use optimal makespans for i machines, for each i = 1, . . . ,m; computing these values is NP-hard in general [Garey and Johnson, 1979]. With exact optimum schedules, our algorithms achieve the stated robustness ratios; for a polynomial-time guarantee, we can replace them by (1+ε)-approximate schedules computed in O(poly1/ε(n)) time (see, e.g., [Hochbaum and Shmoys, 1988]), losing only the usual (1 + ε) factor.

We next outline the main algorithmic ideas. Suppose first that we use a schedule attaining OPTm as the initial schedule. When machines fail, we reassign jobs by list scheduling: each job on a failed machine is moved to an available machine of minimum current workload. Let k′ ≤ k be the number of failed machines and let job j be the last completed job after reassignment. This ensures a makespan of OPTm-k′ + pj ≤ OPTm-k′ + OPTm ≤ 2OPTm-k′ , which implies 2-robustness. To improve upon this, we leave some machines idle in the initial schedule. When a machine fails, its jobs can be moved to these idle machines without increasing the makespan, allowing the schedule to tolerate more failures. However, leaving more idle machines may increase the makespan of the initial schedule, which is undesirable when the number of failed machines is small. Our algorithms balance these effects by choosing how many machines to leave idle. For the special case k = 1, a finer case analysis yields better ratios that match our lower bounds.

In the weak adversary model, the scheduler has more flexibility because it can choose which machines are treated as failed. This yields the upper and lower bounds in Table 1 for both arbitrary k and k = 1.

1.2 Other RelatedWork

Buchem et al. [2024] introduced a stochastic scheduling problem with a stochastic number of machines. In their model, a probability distribution over the number of machines is given, and the goal is to minimize the expected makespan. They showed that the problem is NP-hard and presented a polynomial-time approximation scheme (PTAS). Epstein and Levin [2025] later improved the running time and obtained an efficient polynomial-time approximation scheme (EPTAS).

After a machine failure, reassignment reduces to scheduling jobs on machines that already have load; equivalently, machines can process newly assigned jobs only after their current work is completed. This setting is known as scheduling with non-simultaneous machines. Lee [1991] presented a 4/3-approximation algorithm for the problem.

Our problem also falls under Recoverable Robust Optimization [Liebchen et al., 2009; Buchheim and Kurtz, 2017], where one seeks an initial solution that remains good after a limited recovery step. Commonly studied settings include Knapsack [B¨using et al., 2011], Network Flow [Bertsimas et al., 2013], Scheduling [Bold and Goerigk, 2025], and Matroid Basis [Hommelsheim et al., 2023].

2 Preliminaries

Notation. The workload of a job set is the sum of its processing times. For a job set J ′ , let p(J ′ ) := ∑j∈J ′ pj denote its total workload. Given a schedule S, the workload of a machine is the total processing time assigned to that machine. If no job is assigned to a machine, we say it is idle. The makespan of a schedule S is the maximum workload over all machines. For each 1 ≤ i ≤ m, let OPTi be the optimal makespan when we use only i machines to complete all jobs, and let Si be a schedule attaining OPTi. Throughout this paper, we assume that m ≥ 3; the remaining m ∈ {1, 2} cases are degenerate for reassignment and can be handled separately.

Classical Scheduling Algorithms. The makespan minimization problem on m identical machines is NP-hard [Garey and Johnson, 1979]. For any ε > 0, we can compute a schedule with a makespan of at most (1+ε)OPTi in O(poly1/ε(n)) time (see, e.g., [Hochbaum and Shmoys, 1988]).

The list scheduling algorithm processes jobs in an arbitrary order and assigns each job to the currently least-loaded machine. If it runs on i machines and j is the last completed job, then the resulting makespan is at most OPTi +pj since before the start time of job j, all machines are busy.

3 The Strong AdversaryModel

In the strong adversary model, the algorithm first assigns each job to a machine. The adversary then fails a subset of machines M′ ⊂ Mwith |M′ | ≤ k, and the algorithm reassigns the jobs onM′ to the available machinesM\M′ .

We give a general lower bound and algorithms with robustness ratios strictly below 2. For k = 1, our algorithm matches the lower bound and is best possible.

3.1 The General Case with Arbitrary k

Let α ≈ 1.387 be the positive root of the equation 3x2 -2x3 = 0. We first show a lower bound α on the robustness ratio for any algorithm; the same construction already works for k = 1 and thus for every k ≥ 1.

Theorem 1. Under the strong adversary model, no algorithm can achieve a robustness ratio better than α ≈ 1.387, where α is the positive root of the equation 3x2 - 2x - 3 = 0.

Proof. Consider an instance with m = 4 machines, n = 7 jobs, and k = 1. The processing times are as follows. p1 = 1 and pj = α/3 for 2 ≤ j ≤ 7. Observe that OPT4 = 1 and OPT3 = α. To achieve a robustness ratio better than α, the makespan of the initial schedule must be at most α. Hence, in the initial schedule, job 1 must be the only job assigned to some machine, say, machine 1. Otherwise, the makespan of the initial schedule is at least 1 + α/3 > α. If the initial makespan is already at least α, then the lower bound follows. Thus, to beat α, the six jobs of size α/3 must be distributed over the remaining three machines with load strictly below α on each machine, which leaves only the two cases below. See Figure 2 for an illustration.

• Job 1 is assigned to machine 1, and each of the other three machines has two jobs of processing time α/3. In this case, if machine 1 fails, job 1 must be reassigned to another machine. However, the workload of any other machine is 2α/3 in the initial assignment. Thus the makespan after any reassignment is 1 + 2α/3, and the robustness ratio is at least (1 + 2α/3)/α = α.
• Some machine has at least three jobs of processing time α/3. In this case, the initial makespan is at least α, so the robustness ratio is at least α.

Thus no initial assignment can achieve a robustness ratio better than α.

Next, we present a ϕ-robust algorithm, where ϕ is the positive root of x2 - x - 1 = 0, i.e., the golden ratio (1 + √5)/2 ≈ 1.618. The ratio ϕ results from balancing the performance of our algorithm across two worst-case scenarios. We summarize our algorithm for computing an initial schedule in Algorithm 1, and then explain how to reassign jobs when machines fail.

Theorem 2. Under the strong adversary model, there is a ϕrobust algorithm for arbitrary k, where ϕ = (1 + √5)/2 ≈ 1.618.

Proof. For each i = 1, . . . ,m, we compute an optimal schedule Si on i machines. By scaling, assume without loss of generality that OPTm = 1. We use the monotonicity of the optimum throughout: if r ≤ s, then OPTr ≥ OPTs.

If OPTi ≤ ϕ for all i = m- k, . . . ,m, then we use Sm-k as the initial schedule, leaving k machines idle. Since the adversary can only fail up to k machines and we have k idle machines, each failed non-idle machine can be matched to a distinct available idle machine, and we reassign all its jobs there. In this way, we obtain a new schedule without increasing the makespan.

Otherwise, by monotonicity and OPTm = 1 ≤ ϕ, there exists some j ∈ {m- k + 1, . . . , m} such that OPTj ≤ ϕ < OPTj-1. In this case, we use Sj as the initial schedule, leaving m- j machines idle. We show that Sj is ϕ-robust. Let k′ ≤ k be the number of failed machines. Let ALGm-k′ denote the makespan after applying our reassignment rule when k′ machines fail. We have the following two cases.

Case 1: k′ ≤ m - j. In this case, every failed non-idle machine can be paired with a distinct idle machine that remains available, so we reassign its jobs there without increasing the makespan. Hence, using OPTm-k′ ≥ OPTm = 1, ALGm-k′ ≤ ϕ ≤ ϕ · OPTm-k′ .

Case 2: k′ > m - j. In this case, OPTm-k′ > ϕ. We reassign the jobs on failed machines to available machines using list scheduling. Since OPTm = 1 implies that every job has processing time at most 1, the makespan of the resulting schedule is at most OPTm-k′ + 1. Hence, ALGm-k′ /OPTm-k′ = 1 + 1/OPTm-k′ < 1 + 1/ϕ = ϕ. We conclude that our initial schedule Sj is ϕ-robust.

Algorithm 1 ϕ-robust algorithm for arbitrary k under the strong adversary model

• 1: Input: mmachines, n jobs, and the parameter k
• 2: Output: An initial schedule S
• 3: for i = 1 to mdo
• 4: Compute optimal schedule Si on i machines; denote its makespan OPTi
• 5: end for
• 6: if OPTi ≤ ϕ for all i in {m-k, . . . ,m} then
• 7: return Sm-k (leave k machines idle)
• 8: else
• 9: Find index j such that OPTj ≤ ϕ < OPTj-1
• 10: return Sj (leave m- j machines idle)
• 11: end if

3.2 The Special Case with k = 1

For the special case with k = 1, we achieve a best-possible 1.387-robust algorithm, matching the lower bound in Theorem 1.

Theorem 3. Under the strong adversary model, there is an α ≈ 1.387-robust algorithm for k = 1.

Proof. By scaling, we assume OPTm = 1.

Easy cases. If OPTm-1 ≤ α, then we use Sm-1 as the initial schedule, leaving one machine idle. No matter which machine fails, we reassign its jobs to the idle machine (or the failed machine is the idle machine), and the makespan remains OPTm-1 ≤ α. Hence, the robustness ratio is at most α.

If OPTm-1 ≥ 2/α, then we use Sm as the initial schedule. No matter which machine fails, we reassign its jobs to an available machine, incurring a makespan of at most OPTm + 1 = 2 ≤ αOPTm-1. Hence, the robustness ratio is at most α. The remaining analysis focuses on the case with α < OPTm-1 < 2/α.

A light machine. Consider the schedule Sm. Let Li be the workload of machine i in Sm. Suppose that there exists some machine i with Li ≤ α2 - 1. Then we use Sm as the initial schedule. If machine i′ ̸= i fails, we can reassign the jobs on machine i′ to machine i, and the resulting makespan is at most 1 + (α2 - 1) = α2 < αOPTm-1. If machine i fails, we can reassign the jobs on machine i to any other machine i′ ̸= i; the resulting makespan is at most 1 + (α2 - 1) < αOPTm-1. Hence, the robustness ratio is at most α. In the remaining analysis, we consider the case where Li > α2 - 1 for all machines i.

Let Ji be the set of jobs assigned to machine i in Sm. Suppose that for some machine i, there exists a subset of jobs J ′ i ⊆ Ji with p(J ′ i ) ∈ [2 - α, α2 - 1]. Then we modify Sm as follows: move the jobs in Ji \ J ′ i to another machine i′ ̸= i. Note that after this, the workload of machine i is in the interval [2-α, α2 -1], and the workload of machine i′ is at most 1 + (1 - (2 - α)) = α. We show that the robustness ratio of the new schedule is at most α.

If no machine fails, the makespan is at most α. If machine i fails, we can reassign the jobs on machine i to any other machine i′′ /∈ {i, i′ }, and the resulting makespan is at most Algorithm 2 α-robust algorithm for k = 1 under the strong adversary model

• 1: Input: n jobs, mmachines, and the parameter k = 1
• 2: Output: An initial schedule S
• 3: Compute optimal schedules Sm-1 and Sm. Let Li be the workload of machine i in Sm and Ji be the set of jobs assigned to machine i in Sm.
• 4: if OPTm-1 ≤ α then
• 5: return Sm-1 (with one idle machine).
• 6: else if OPTm-1 ≥ 2/α or ∃i,Li ≤ α2 -1 then
• 7: return Sm.
• 8: else if ∃i, J ′ ⊆ Ji such that p(J ′ ) ∈ [2 - α, α2 - 1] then
• 9: return Modified schedule fromSm bymovingJi\J ′ to machine i′ ̸= i.
• 10: else
• 11: Let a1, a2, a3 be the three smallest medium jobs (set a3 := ∞ if fewer than three exist), and let b1 be the smallest large job.
• 12: if a1 + a2 + a3 ≤ a2 + b1 or a1 + a2 ≤ α2 - 1 then

13:

return Modified schedule from Sm by swapping

some jobs between machines of a1 and a2.

• 14: else
• 15: return Modified schedule from Sm by moving small jobs from the machine with b1 to any other machine with two medium jobs.
• 16: end if
• 17: end if

1 + (α2 - 1) < αOPTm-1. If machine i′′ /∈ {i, i′ } fails, we reassign the jobs on machine i′′ to machine i, incurring a makespan of at most 1+(α2 -1) < αOPTm-1. If machine i′ fails, we reassign the jobs on machine i′ as follows. We send the jobs moved from machine i to i′ (with total workload at most 1 - (2 - α)) to any machine i′′ /∈ {i, i′ }, and send the other jobs on i′ (with total workload at most 1) to machine i. After the reassignment, the workload of machine i is at most α2 - 1 + 1 = α2 < αOPTm-1, and the workload of machine i′′ is at most 1 + (1 - (2 - α)) = α. Hence, the robustness ratio is at most α.

Structural case. It remains to consider cases with the following properties:

• (a) α < OPTm-1 < 2/α;
• (b) Li > α2 - 1 for all machines i;
• (c) In Sm, for every machine i, there is no subset of jobs J ′ i ⊆ Ji with p(J ′ i ) ∈ [2 - α, α2 - 1].

To explore more structural properties, we classify jobs by their processing times into the following three categories. We say a job j is:

• small if pj < 2-α2 ;
• medium if α2 + α - 3 < pj < 2 - α;
• large if pj > α2 -1.

Here 2-α2 < α2 +α-3, so the second forbidden interval in the claim below is nonempty; this follows from 3α2 - 2α - 3 = 0. See Figure 3 for an illustration. We first record the

1

Figure 3: Job classification by size. "S", "M" and "L" correspond to small, medium, and large jobs. ×means no jobs in these intervals.

following claim, which shows that these three classes cover all jobs.

Claim. Under Properties (a)-(c), every job must be either small, medium, or large; i.e., no job has processing time in the forbidden intervals

Proof. Property (c) already forbids any job in [2 - α, α2 - 1]. Suppose, for contradiction, that some job j on machine i satisfies pj ∈ [2-α2 , α2 +α-3]. Then the subset Ji \ {j} has a workload of

and

Hence p(Ji \ {j}) ∈ [2 - α, α2 - 1], violating Property (c). ◁

Under Properties (a)-(c), each machine in Sm has either one large job and only small jobs, or two medium jobs and only small jobs. Indeed, a large and a medium job already exceed load 1; three medium jobs contain two jobs with total load in [2 - α, α2 - 1]; and a prefix argument rules out machines with only small jobs or with one medium job and small jobs.

Let ℓ be the number of machines that have two medium jobs, and the other m- ℓ machines that have one large job. We have the following cases.

Case 1: ℓ = 0. In this case, there are m large jobs. So in any schedule with m - 1 machines, some machine has at least 2 large jobs, which implies OPTm-1 > 2(α2 - 1). This violates Property (a), so this case will not happen.

Case 2: ℓ = m. In this case, we use Sm as our initial schedule. When one machine i fails, let j1 and j2 be its two medium jobs. We reassign j1 to another machine i1 and j2 to another machine i2, where i, i1, i2 are distinct. If machine i has small jobs of total workload W, let T = α2 + α - 3. Since W < 1 - 2T , we split them into two groups of workload at most T : if W > T , take the first prefix above W -T , whose load is below W - T + (2 - α2 ) < T. We send one group to i1 and the other to i2. Therefore, each of i1 and i2 starts with workload at most 1, receives at most 2 - α from the failed machine and at most α2 + α - 3 from the split small jobs, and thus ends with workload at most 1 + (2 - α) + (α2 + α - 3) = α2 < αOPTm-1.

Case 3: 1 ≤ ℓ ≤m-1. Let the processing times of the 2ℓ medium jobs be a1 ≤ a2 ≤ · · · ≤ a2ℓ and those of the m- ℓ large jobs be b1 ≤ b2 ≤ · · · ≤ bm-ℓ. For simplicity, we also refer to ai or bi as the corresponding job.

We show another lower bound on OPTm-1. Consider a schedule with m - 1 machines. If there is some machine with 2 large jobs, then we have OPTm-1 ≥ 2(α2 -1), which violates Property (a). Similarly, if there is a machine with one large job and 2 medium jobs, then we have OPTm-1 ≥ 2/α, violating Property (a). Hence, in any schedule with m - 1 machines, either there is some machine that has at least 3 medium jobs or there are at least two machines, each of which has one medium job and one large job. In the former case, we have OPTm-1 ≥ a1 + a2 + a3, where a3 is defined as ∞ if there are only 2 medium jobs, and in the latter we have OPTm-1 ≥ a2 + b1. In any case, we have

We perform a case analysis on Equation (3).

Case 3.1: a1 + a2 + a3 ≤ a2 + b1. Note that we will not be in this case if there are only 2 medium jobs. Since a3 ≥ a2 ≥ a1, we have OPTm-1 ≥ a1 + a2 + a3 ≥ 3/2(a1 + a2). We obtain a new schedule S′m from Sm as follows. Let i1 (resp. i2) be the machine where a1 (resp. a2) is assigned. If i1 = i2, then a1 and a2 are already on one machine, and the same reassignment argument applies without the swap below. Thus, we assume i1 ̸= i2 in the construction below. Let a′1 (resp. a′2 ) be the other medium job assigned to i1 (resp. i2), and J1 (resp. J2) be the set of small jobs assigned to i1 (resp. i2). We move a′1 and J1 to i2, and a2 to i1. In this way, we obtain S′m as the initial schedule. The two modified machines end up with workloads a1 + a2 and at most 2 - (a1 + a2), respectively. The first is below α because a1 + a2 < 2(2 - α) < α, and the second is below α because a1, a2 > α2 + α-3, so a1+a2 > 2(α2 +α-3) > 2-α. It suffices to show that when one machine fails, we can reassign the jobs so that the makespan after reassignment is at most αOPTm-1.

If a third machine i3 /∈ {i1, i2} fails, send its jobs to i1, whose load is at most a1 + a2 + 1. If 3 2 (a1 + a2) ≤ α, this is at most α2 ; otherwise it is below α · 3 2 (a1 + a2). In both cases it is at most αOPTm-1. If i1 fails, we can reassign all the jobs on i1 to some i3 /∈ {i1, i2} by the same arguments as above. If i2 fails, we reassign a′1 and J1 to i1, and reassign a′2 and J2 to some i3 /∈ {i1, i2}. After that, the workload of i1 is at most 1 + a2 < α2 , and the workload of i3 is at most 1 + (1 - a2) < 2 - (α2 + α - 3) < α2 ; both are below αOPTm-1. We conclude that S′m has a robustness ratio of α.

Case 3.2: a1 + a2 ≤ 2α/3 = α2 - 1. We use the same modification as in Case 3.1 and the same analysis, using the fact that 1 + a1 + a2 ≤ 1 + α2 - 1 = α2 ≤ αOPTm-1.

Case 3.3: a1+a2+a3 > a2+b1 and a1+a2 > 2α/3. Note that a2 ≥ a1, which implies that a2 > α/3. We obtain a new schedule S′m from Sm as follows. Let i be the machine where b1 is assigned and J be the set of small jobs on i. We move J to some other machine i′ ̸= i that has two medium jobs. In this way, we obtain S′m. If no machine fails, the makespan of S′m is at most max{1, 2 - b1} < α, since b1 > α2 - 1. If i′′ /∈ {i, i′ } fails, we reassign all its jobs to i, increasing its workload to 1+b1. Since a2 > α/3 and b1 > α2 -1 = 2α/3, we have α(a2+b1)-(1+b1) > α2 /3+(α-1)2α/3-1 = 0; hence 1 + b1 < α(a2 + b1) ≤ αOPTm-1. If i fails, we can reassign all its jobs to i′′ /∈ {i, i′ } by the same arguments as above. If i′ fails, send one medium job and all small jobs on i′ to i, and the other medium job to i′′ /∈ {i, i′ }. The original small workload of i′ is at most 1 - (α2 - 1), since its two medium jobs total more than a1+a2 > α2 -1. The makespan after reassignment is at most 1 + 2 - α + (1 - (α2 - 1)) < α2 ≤ αOPTm-1.

4 TheWeak AdversaryModel

In the weak adversary model, the adversary reveals the number of failed machines k′ ≤ k after the algorithm fixes its initial schedule. The algorithm then chooses which k′ machines are treated as failed. This weaker adversary allows better robustness ratios.

4.1 The General Case with Arbitrary k

We start with a lower bound of γ ≈ 1.281, where γ is the positive root of x2 - x/2 - 1 = 0.

Theorem 4. Under the weak adversary model, no algorithm can achieve a robustness ratio better than γ ≈ 1.281, where γ is the positive root of x2 - x/2 - 1 = 0.

Proof. Consider an instance with m = 6 machines, n = 12 jobs, and k = 1. There are 6 large jobs of processing time γ/2 and 6 small jobs of processing time 1 - γ/2. Observe that OPTm = 1 and OPTm-1 = γ. Indeed, a makespan of γ on five machines is feasible by placing the six large jobs as three pairs and the six small jobs as two triples; the latter have load 3(1 - γ/2) ≤ γ. Also, because there are six large jobs and only five machines, some machine must contain two large jobs, so OPTm-1 ≥ γ and hence OPTm-1 = γ.

To achieve a robustness ratio strictly smaller than γ, no machine can have two large jobs in the initial schedule; otherwise the makespan, and hence the robustness ratio, is at least γ. Thus each machine must contain exactly one large job. If some machine has at least two small jobs, then its workload is at least γ/2 + 2(1 - γ/2) = 2 - γ/2 > γ, which results in a robustness ratio greater than γ. Hence, the only possible initial schedule is that each machine has exactly one large job and one small job.

When one machine fails, one large job and one small job must be reassigned. Some machine receiving the large job then has workload at least 1+γ/2 = γ 2 . Since OPTm-1 = γ, the robustness ratio is γ 2 /γ = γ.

Next, we show a 1.5-robust algorithm for arbitrary k.

Theorem 5. Under the weak adversary model, there is a 1.5robust algorithm for arbitrary k.

Proof. We use similar ideas as in Section 3.1 to decide an initial schedule, and then carefully select which machines to fail. Again, by scaling, we can assume that OPTm = 1.

If OPTi ≤ 1.5 for all i with m - k ≤ i ≤ m, we use Sm-k as the initial schedule and leave k machines idle. This is 1.5-robust: when failures occur, we select idle machines as the failed machines, so the makespan is unchanged.

Otherwise, there exists some i ∈ {m-k+1, . . . ,m} such that OPTi ≤ 1.5 and OPTi-1 > 1.5. Then we use Si as the initial schedule, leaving m- i machines idle. We show this ensures a robustness ratio of 1.5. Let k′ ≤ k be the number of failed machines chosen by the adversary. The case k′ = 0 is already covered by the first branch below and requires no special handling. If k′ ≤m-i, thenwe can select k′ idlemachines as the failed machines without affecting the makespan. Hence, it remains to consider the case where m-i < k′ ≤ k. We first select the m-i idle machines as the failed machines. It remains to choose the other k′′ := k′ - (m - i) failed machines. Let ALGi-k′′ denote the makespan after applying our reassignment rule when the final number of machines is i - k′′ .

Call a job large if its processing time is at least 0.75 and small otherwise. Without loss of generality, we can assume that in Si, the first i′ machines contain a large job, the next i - i′ machines contain only small jobs, and the last m- i machines are idle.

Case 1: i - k′′ ≥ i′ . In this case, k′′ ≤ i - i′ , so we select any k′′ machines among the i - i′ machines without large jobs as the failed machines. We reassign the jobs of these k′′ machines to the remaining i - k′′ machines using list scheduling. The makespan of the new schedule is at most OPTi-k′′ + 0.75, which implies

where the second inequality uses OPTi-k′′ ≥ OPTi-1 > 1.5. Case 2: i - k′′ < i′ /2. Here the number of remaining machines i - k′′ is so small that in any feasible schedule on i - k′′ machines, some machine must contain at least 3 large jobs. This is just the pigeonhole principle: there are i′ large jobs in total, but fewer than i′ /2 remaining machines, so one machine must receive at least three large jobs. Hence, OPTi-k′′ ≥ 3 · 0.75 = 2.25. We reassign the jobs of the failed k′′ machines to the remaining i - k′′ machines using list scheduling. The makespan of the new schedule is at most OPTi-k′′ + 1, which implies

Case 3: i′ /2 ≤ i - k′′ < i′ . For each machine r ∈ {1, . . . , i}, let br be the processing time of the largest job on machine r. Without loss of generality, assume that b1 ≥ b2 ≥ · · · ≥ bi. We keep the first i - k′′ machines as the remaining machines, and the next k′′ machines as the failed machines. Note that there are i - k′′ + 1 jobs with a processing time of at least bi-k′′+1. Hence, in any feasible schedule with i - k′′ machines, some machine has at least 2 jobs with a processing time of at least bi-k′′+1, which implies OPTi-k′′ ≥ 2bi-k′′+1. We reassign the jobs of the failed k′′ machines to the remaining i-k′′ machines using list scheduling, incurring a makespan of at most OPTi-k′′ + bi-k′′+1, because every job on a failed machine has processing time at most bi-k′′+1. Therefore, we have

4.2 The Special Case with k = 1

For the special case with k = 1, we achieve a best-possible 1.281-robust algorithm.

Theorem 6. Under the weak adversary model, there is a γ ≈ 1.281-robust algorithm for k = 1.

Proof. By scaling, assume OPTm = 1.

We call a job j large if pj > γ/2 ≈ 0.64, and small otherwise. We first handle m ≥ 4 and then treat m = 3 separately. Case m ≥ 4. If OPTm-1 ≤ γ, then we use Sm-1 as the initial schedule. If no machine fails, the makespan is OPTm-1 ≤ γOPTm. If the adversary decides to fail one machine, we can pick the empty machine as the failed machine, without affecting the makespan. This proves that the robustness ratio is at most γ.

If OPTm-1 > γ, we use Sm as the initial schedule. Since OPTm = 1, each machine contains at most one large job, and there are at most m large jobs. If there are exactly m large jobs, then any schedule on m- 1 machines has some machine containing at least two large jobs. Hence, we have OPTm-1 ≥ 2b, where b is the smallest processing time of large jobs. If the adversary decides to fail one machine, we pick the machine that has a large job j with pj = b as the failed machine. We assign job j to some machine i′ ̸= i, and the other jobs of machine i to another machine i′′ /∈ {i, i′ }. After the reassignment, the makespan of the new schedule is at most max{1+b, 1+(1-b)} = 1+b. Since (1+b)/(2b) = 1/2+1/(2b) ≤ 1/2+1/γ = γ, the robustness ratio is at most γ.

If there are fewer than m large jobs, then some machine i in Sm has no large job. We treat machine i as the failed machine and partition its jobs using the following claim.

Claim. Any set of small jobs with total workload at most 1 can be split into at most 3 parts, each of workload at most γ/2.

Proof. If the total workload is at most γ/2, we are done with only one part. Otherwise, index the jobs as 1, . . . , ℓ and write Zi := ∑ij=1 pj for each 1 ≤ i ≤ ℓ. If there exists 1 ≤ i ≤ ℓ such that 1-γ/2 ≤ Zi ≤ γ/2, then we can partition the jobs into 2 parts, i.e., the first i jobs and the last ℓ - i jobs, and we are done. Otherwise, there must be some index 1 ≤ i < ℓ such that Zi < 1 - γ/2 and Zi+1 > γ/2. In this case, we partition the jobs into 3 parts, i.e., the first i jobs, the job i+1, and the last ℓ - i - 1 jobs. The workload of the first i jobs is at most 1-γ/2 < γ/2, and the workload of the last ℓ-i-1 jobs is at most 1-γ/2 < γ/2. The workload of the job i+1 is at most γ/2 since there is no large job. ◁

Then we assign each part to a distinct machine, which is possible since m ≥ 4, incurring a new makespan of at most 1 + γ/2 = γ 2 ≤ γOPTm-1.

Case m = 3. The previous three-part argument may fail when m = 3. Again assume OPTm-1 > γ and at most m-1 large jobs; use Sm and fix a machine without large jobs as the one that may fail. Let B be its workload. If some job has size above 2B/3, assign this job and the remaining workload separately, giving makespan at most 1+γ/2 = γ 2 ≤ γOPTm-1. Thus every job has size at most 2B/3, and we use the following claim.

Claim. If a job set J has total workload at most B and no job exceeds 2B/3, then J can be split into two parts, each of workload at most 2B/3.

Proof. If the total workload is at most 2B/3, we are done with J1 := ∅ and J2 := J . Otherwise, index the jobs as 1, . . . , ℓ and let Zi := ∑ij=1 pj for each 1 ≤ i ≤ ℓ. Let i be the largest index with Zi ≤ 2B/3, and let W := Zℓ be the total workload. If W - Zi ≤ 2B/3, then we are done with J1 := {1, . . . , i} and J2 := {i + 1, . . . , ℓ}. Otherwise, we have W - Zi > 2B/3, which implies Zi < B/3 since W ≤ B. By maximality of i, we have Zi+1 > 2B/3, so pi+1 > 2B/3 - Zi > B/3. Then we set J2 := {i + 1} and J1 := J \ {i + 1}. We have p(J2) = pi+1 ≤ 2B/3 and p(J1) = W - pi+1 ≤ B - B/3 = 2B/3. ◁

Let the two resulting parts be labeled so that p(J1) ≤ p(J2). Note that p(J1) ≤ 0.5 since p(J1) ≤ B/2 ≤ 1/2.

When this chosen machine fails, we reassign J1 and J2 to the remaining two machines as follows. We can assume that p(J1) + p(J2) ≥ γ/2, as otherwise we can reassign both J1 and J2 to one remaining machine to ensure a makespan of at most 1 + γ/2 = γ 2 ≤ γOPTm-1. If one remaining machine has workload at most γ 2 - 2/3, put J2 there and J1 on the other; their loads become at most γ 2 and 1+0.5 ≤ γ 2 , respectively. Hence, the makespan of the new schedule is at most γ 2 ≤ γOPTm-1. If both of the remaining two machines have a workload of at least γ 2-2/3, then we have OPTm-1 ≥ γ 2 - 2/3 + (p(J1) + p(J2))/2 = γ 2 - 2/3 +B/2. In this case, we reassign J1 to one remaining machine and J2 to the other. This ensures that the makespan of the new schedule is at most 1 + p(J2) ≤ 1 + 2B/3. Set

5 Conclusion

We studied robust scheduling under machine failures, where an initial schedule must be paired with reassignment rules that move only jobs on failed machines. For both the strong and weak adversary models, we gave robust algorithms and matching lower bounds for the single-failure case; for arbitrary k, we obtained ratios strictly below the baseline obtained by direct list-scheduling recovery. The main technical tradeoff is how much idle capacity to reserve for recovery while keeping the no-failure schedule close to optimal; the weak model further exploits the freedom to choose which machines are treated as failed. Open questions include designing algorithms with better robustness ratios for arbitrary k, establishing stronger lower bounds for k ≥ 2, and finding better-than-2-robust algorithms without (approximately) computing OPTi.

Acknowledgements

This work was supported by the National Natural Science Foundation of China (NSFC) under Grant No. 12271477.