Introduction
We study two-stage scheduling for minimizing the total completion time when the available machines and their speeds are initially unknown. The jobs and their processing times are known in advance, but the jobs must be grouped before the machine environment is revealed. Such grouping may be necessary when computational tasks and their input data are bundled before submission to a shared computing system. The challenge is to choose groups that admit good schedules for every possible machine environment.
We consider speed-robust scheduling , which was introduced by Stein and Zhong [13 ] for an unknown number of identical machines and extended to general speeds by Eberle et al. [4 ] . In Phase I, an algorithm partitions the jobs into M M M groups, called bags . An adversary then reveals either a number 1 ≤ m ≤ M 1 \le m \le M 1 ≤ m ≤ M of identical machines (*speeds in { 0 , 1 } \{0,1\} { 0 , 1 } ) or a nonnegative speed for each of the M M M machines (general speeds ). Machines with speed zero are unavailable. In Phase II, all jobs of a bag must be assigned to the same available machine, and several bags may share a machine. Jobs from different bags may be interleaved and are processed in shortest-processing-time-first (SPT) order, which minimizes the total completion time for a fixed assignment [12 ] .
We evaluate an algorithm by its robustness factor , the worst-case ratio between the objective value of its schedule and that of an optimal schedule that knows the machine environment in advance and may assign jobs individually. This comparison measures the loss caused by fixing the bags before the machine specification is known. Following Eberle et al. [4 ] , we distinguish infinitesimally small jobs (sand ), unit-size jobs (bricks ), and jobs with arbitrary processing times (rocks ).
Previous work on this model has focused primarily on makespan minimization. For an unknown number of identical machines, Stein and Zhong [13 ] gave the first algorithms and lower bounds, including a ( 5 / 3 + ε ) (5/3+\varepsilon) ( 5/3 + ε ) -robust algorithm for rocks. Eberle et al. [4 ] closed the gaps for sand and bricks, establishing optimal uniform robustness factors of ( 1 + 2 ) / 2 ≈ 1.2071 (1+\sqrt{2})/2 \approx1.2071 ( 1 + 2 ) /2 ≈ 1.2071 and 4 / 3 4/3 4/3 , respectively. For general speeds, they determined the optimal factor for sand, which tends to e / ( e − 1 ) ≈ 1.5820 e/(e-1) \approx1.5820 e / ( e − 1 ) ≈ 1.5820 as the number of machines grows, and gave constant guarantees for bricks and rocks; the guarantee for bricks was subsequently improved by Minařík and Sgall [11 ] . For identical machines, Yu and Tan [14 ] gave a simpler optimal algorithm for bricks.
Stein and Zhong [13 ] explicitly raised total completion time as an open problem, noting that it introduces additional questions about job ordering. Unlike makespan, this objective depends on the processing order on each machine. Although SPT determines the optimal processing order for a fixed assignment, the bags must still admit an assignment of small total completion time for every revealed machine environment. For sand, the objective reduces to a sum of squared assigned volumes weighted by inverse speeds. Every ρ \rho ρ -robust makespan algorithm for sand is also ρ \rho ρ -robust for total completion time (Lemma 3). Thus, the makespan factors 1.2071 and 1.5820 provide natural benchmarks. Our results show that substantially smaller robustness factors are possible.
Our results
We initiate the study of speed-robust scheduling for total completion time and obtain tight or nearly tight bounds for an unknown number of identical machines and small constant bounds for general speeds. Our bounds are uniform over the number M M M of bags: upper bounds hold for every M M M , while lower bounds rule out smaller guarantees valid for every M M M . All upper bounds are attained by deterministic polynomial-time algorithms and lower bounds assume deterministic algorithms. Table 1 summarizes the bounds.
Table 1. Table 1. Summary of our robustness bounds (uniform over the number of bags). Entries spanning two columns are tight.
Speeds in { 0 , 1 } \{0,1\} { 0 , 1 } The optimal robustness factor is exactly 13/12 for both bricks and rocks (Theorems 3 and 4). Thus, arbitrary processing times are no harder than unit-size jobs. For the makespan, in contrast, rocks are not known to be as easy as bricks. Our algorithm deliberately creates bags with different job counts, which can be combined to balance the machines in Phase II. For bricks, the analysis controls the variance of the machine job counts. For rocks, we construct the bags in non-increasing order of processing times. A single bag-to-machine assignment satisfies the brick guarantee for every prefix of this order viewed as unit-size jobs. A layer decomposition then transfers the guarantee to the original processing times (Lemma 1).
For sand, the optimal robustness factor lies between 31/30 and 28/27, leaving a gap of 1/270 < 0.004. The lower bound holds even for randomized algorithms against an oblivious adversary. Equal-volume bags achieve a tight factor of 9/8 (Observation 5); our bag volumes instead follow a linear profile, so that small bags can be paired when fewer machines are available. Our lower bound combines Cauchy–Schwarz relaxations for four machine counts with M = 12 M = 12 M = 12 bags.
General speeds Allowing arbitrary speeds makes the problem strictly harder: no deterministic algorithm is better than 1.2669-robust, already for sand (Theorem 5). This exceeds our factor of 13/12 even for rocks for { 0 , 1 } \{0,1\} { 0 , 1 } -speeds, and by Observation 2 the bound carries over to bricks and rocks. The adversary uses one fast machine and M − 1 M - 1 M − 1 equally slow machines, choosing their speeds after observing the bags. A fractional cost profile captures the trade-off between sending bags to the slow machines and concentrating volume on the fast machine. The restriction to M M M bags bounds the integral of its reciprocal slope, independently of the bag volumes. This limits how well any partition can accommodate all speed vectors.
For the upper bound, we give a common 25/16-robust algorithm for sand, bricks, and rocks (Theorem 6). It uses equal-volume bags for sand and assigns jobs cyclically to bags in non-increasing processing-time order for bricks and rocks. In Phase II, bags are assigned by a greedy rule based on bag counts and machine speeds. Its threshold structure keeps bag counts proportional to machine speeds up to rounding. For bricks, the analysis compares machine costs with those of an optimal schedule using correction terms whose sum is non-positive. The prefix transfer again handles rocks. The factor 25 / 16 25/16 25/16 is tight for these bag constructions, even with an optimal Phase II assignment (Theorem 6). For sand, bags of different volumes and a modified Phase II rule improve the guarantee to 1681 / 1152 ≈ 1.4592 1681/1152 \approx1.4592 1681/1152 ≈ 1.4592 (Theorem 7), clearly below the makespan benchmark of 1.5820 1.5820 1.5820 . Smaller bags allow slow machines to receive less volume. We assign them to machines with less speed per assigned bag. Cauchy–Schwarz bounds the cost by a sum of squared bag volumes, each weighted by the number of bags per unit of speed on its machine. We use threshold inequalities of the assignment rule and convexity to bound this sum.
Additional variants We show that the freedom to reorder jobs is essential: in a non-adaptive variant, where every bag must be processed contiguously, no algorithm with M M M bags is better than M M M -robust, already for identical machines. This bound is trivially achieved by placing all jobs in a single bag; we determine the optimal robustness factor exactly as a function of M M M and the number of distinct processing times (Appendix § 9 .§ 1 ).
We also study a model proposed by Liu, Zhang, and Zhao [10 ] , in which jobs are assigned directly to machines in Phase I and the adversary chooses which machines fail. Jobs on surviving machines must remain there. For identical machines, we give an algorithm matching the unrestricted optimum when jobs from failed machines may be reassigned individually. We also introduce a more restrictive variant in which they must be reassigned together, and give bounds for it (Appendix § 9 .§ 2 ).
Further related work
Without bag constraints, the total completion time can be minimized in polynomial time if the machine environment is known: by SPT list scheduling on identical machines [2 ] and by a greedy assignment to positional slots on uniformly related machines [9 ] . For a single machine whose speed changes in an unknown way, Epstein et al. [8 ] constructed universal job sequences for the total weighted completion time that are good for all speed patterns simultaneously.
Other work assumes additional information about the machine environment. Buchem et al. [3 ] considered a stochastic number of identical machines with a known distribution and gave PTASs for the expected makespan and the expected minimum machine load. Epstein and Levin [7 ] improved these to EPTASs and also considered expected ℓ p \ell_p ℓ p norms of the loads. Their guarantees are relative to the best two-stage solution for the given distribution, whereas our benchmark may assign jobs individually. Balkanski et al. [1 ] considered predicted machine speeds and obtained makespan guarantees that improve with prediction accuracy while remaining bounded for arbitrary predictions.
Epstein [5 ] studied an online variant of speed-robust scheduling in which jobs arrive one by one and must be assigned to bags immediately, for makespan minimization and for maximizing the minimum load. She also studied in [6 ] ordinal scheduling with an unknown number of machines, where processing times remain unknown when bags are formed and merged.
Preliminaries
This section formalizes the model from the introduction and introduces three auxiliary results used throughout the paper: a transfer of guarantees from bricks to rocks, a transfer of lower bounds from sand to bricks and rocks, and a transfer of makespan guarantees to the total completion time for sand. Omitted proofs are in Appendix § 6 .
Problem definition An instance consists of n n n jobs with processing times p j > 0 p_j > 0 p j > 0 , j ∈ [ n ] j \in[n] j ∈ [ n ] , and the number M M M of bags, which is also the maximum number of machines. All jobs are available at time zero. In Phase I, an algorithm partitions the given jobs into bags B 1 , … , B M B_1,\ldots,B_M B 1 , … , B M , some of which may be empty. Then, an adversary reveals a speed vector s ∈ R ≥ 0 M ∖ { 0 } \boldsymbol{s}\in\mathbb{R}_{\ge0}^{M}\setminus\{\boldsymbol{0}\} s ∈ R ≥ 0 M ∖ { 0 } : a job j j j on a machine of speed s i > 0 s_i>0 s i > 0 takes p j / s i p_j/s_i p j / s i time units, and a machine of speed zero is unavailable. Let m : = ∣ { i ∈ [ M ] : s i > 0 } ∣ m:=|\{i\in[M]:s_i>0\}| m := ∣ { i ∈ [ M ] : s i > 0 } ∣ , and relabel the machines so that the available machines are indexed by 1 , … , m 1,\ldots,m 1 , … , m . We call the unrestricted choice of s \boldsymbol{s} s the setting of general speeds . For speeds in { 0 , 1 } \{0,1\} { 0 , 1 } , the adversary chooses only the number m ∈ [ M ] m\in[M] m ∈ [ M ] of available identical machines.
In Phase II, the algorithm assigns every bag to one of the available machines via a map π : [ M ] → [ m ] \pi:[M]\to[m] π : [ M ] → [ m ] where several bags may share a machine. Machine i i i then processes the jobs J i : = ⋃ r : π ( r ) = i B r J_i:=\bigcup_{r:\pi(r)=i}B_r J i := ⋃ r : π ( r ) = i B r in non-decreasing order of processing times (SPT), one at a time without preemption or idle time.
Objective and robustness guarantee The objective is to minimize the total completion time ∑ j ∈ [ n ] C j \sum_{j\in[n]}C_j ∑ j ∈ [ n ] C j , where C j C_j C j is the completion time of job j j j . For an instance I I I and a speed vector s \boldsymbol{s} s , let Alg ( I , s ) \operatorname{Alg}(I,\boldsymbol{s}) Alg ( I , s ) denote the cost of the algorithm’s schedule, and let Opt ( I , s ) \operatorname{Opt}(I,\boldsymbol{s}) Opt ( I , s ) denote the minimum total completion time of a schedule that knows s \boldsymbol{s} s in advance and may assign jobs individually, without bag constraints. An algorithm is ρ \rho ρ -robust if Alg ( I , s ) ≤ ρ Opt ( I , s ) \operatorname{Alg}(I,\boldsymbol{s})\leq\rho\operatorname{Opt}(I,\boldsymbol{s}) Alg ( I , s ) ≤ ρ Opt ( I , s ) for every instance I I I and every feasible speed vector s \boldsymbol{s} s . Its robustness factor is the infimum over all such ρ \rho ρ . The optimal robustness factor of a setting is the infimum of the robustness factors of all deterministic algorithms. For a fixed number M M M of bags, we define the corresponding robustness factors by restricting to instances with M M M bags. We omit the instance I I I from the notation whenever it is clear.
Sand, bricks, and rocks For sand, we normalize the total volume to one. Let b r b_r b r denote the volume of bag B r B_r B r and y i : = ∑ r : π ( r ) = i b r y_i:=\sum_{r:\pi(r)=i}b_r y i := ∑ r : π ( r ) = i b r the volume assigned to machine i i i . We view sand as the limit of equal-size jobs whose common size δ \delta δ tends to zero. For fixed assigned volumes, total completion time grows like 1 / δ 1/\delta 1/ δ . We therefore multiply algorithmic and optimal costs by δ \delta δ , preserving their ratio and obtaining a finite limit. If machine i i i receives k i k_i k i jobs of total volume y i = k i δ y_i=k_i\delta y i = k i δ , its scaled total completion time is
δ ∑ h = 1 k i h δ s i = y i 2 + δ y i 2 s i ⟶ y i 2 2 s i as δ → 0. \delta\sum_{h=1}^{k_i}\frac{h\delta}{s_i}=\frac{y_i^2+\delta y_i}{2s_i}\longrightarrow\frac{y_i^2}{2s_i}\quad\text{as }\delta\to0. δ h = 1 ∑ k i s i h δ = 2 s i y i 2 + δ y i ⟶ 2 s i y i 2 as δ → 0.
We therefore use 1 2 ∑ i y i 2 / s i \frac{1}{2}\sum_i y_i^2/s_i 2 1 ∑ i y i 2 / s i as the objective for sand. Write S : = ∑ i = 1 m s i S:=\sum_{i=1}^{m}s_i S := ∑ i = 1 m s i . By Cauchy–Schwarz, ∑ i = 1 m y i 2 / s i ≥ ( ∑ i = 1 m y i ) 2 / S = 1 / S \sum_{i=1}^{m}y_i^2/s_i\geq(\sum_{i=1}^{m}y_i)^2/S=1/S ∑ i = 1 m y i 2 / s i ≥ ( ∑ i = 1 m y i ) 2 / S = 1/ S , with equality for y i = s i / S y_i=s_i/S y i = s i / S . Hence, the unrestricted optimum for sand has cost 1 / ( 2 S ) 1/(2S) 1/ ( 2 S ) , and the ratio between the cost of an assignment with loads y i y_i y i and this optimum is
R ( s ) : = S ∑ i = 1 m y i 2 s i . R(\boldsymbol{s}):=S\sum_{i=1}^{m}\frac{y_i^2}{s_i}. R ( s ) := S i = 1 ∑ m s i y i 2 .
For speeds in { 0 , 1 } \{0,1\} { 0 , 1 } , we write R ( m ) : = m ∑ i = 1 m y i 2 R(m):=m\sum_{i=1}^{m}y_i^2 R ( m ) := m ∑ i = 1 m y i 2 for this ratio. For bricks, a machine of speed s i s_i s i processing k k k unit-size jobs contributes F ( k ) / s i F(k)/s_i F ( k ) / s i , where F ( k ) : = k ( k + 1 ) / 2 F(k):=k(k+1)/2 F ( k ) := k ( k + 1 ) /2 . For speeds in { 0 , 1 } \{0,1\} { 0 , 1 } , the linear part of the total cost is always n / 2 n/2 n /2 ; for general speeds, it depends on the assignment.
Transferring guarantees Write p 1 ≥ ⋯ ≥ p n p_1\geq\cdots\geq p_n p 1 ≥ ⋯ ≥ p n and set p n + 1 = 0 p_{n+1}=0 p n + 1 = 0 . For any fixed assignment, its cost under SPT is a weighted sum of the costs of treating each prefix as bricks, with weight p r − p r + 1 p_r-p_{r+1} p r − p r + 1 for the prefix 1 , … , r 1,\ldots,r 1 , … , r . Thus, a guarantee for bricks transfers to rocks if the same assignment satisfies it for every prefix.
Lemma 1. Fix an instance I I I with p 1 ≥ ⋯ ≥ p n p_1\geq\cdots\geq p_n p 1 ≥ ⋯ ≥ p n and speeds s \boldsymbol{s} s . Consider an algorithm’s assignment A A A on ( I , s ) (I,\boldsymbol{s}) ( I , s ) . Suppose that, for every r ∈ [ n ] r\in[n] r ∈ [ n ] , restricting A A A to the jobs 1 , … , r 1,\ldots,r 1 , … , r and setting their processing times to one gives a schedule of cost at most α \alpha α times the unrestricted optimum for r r r unit-size jobs and speeds s \boldsymbol{s} s . Then Alg ( I , s ) ≤ α Opt ( I , s ) \operatorname{Alg}(I,\boldsymbol{s})\leq\alpha\operatorname{Opt}(I,\boldsymbol{s}) Alg ( I , s ) ≤ α Opt ( I , s ) .
Lower bounds for sand also extend to bricks and rocks by a limiting argument: sufficiently many unit-size jobs approximate sand after normalizing the total volume.
Observation 2. For every fixed number of bags, every lower bound on the optimal robustness factor for sand also holds for bricks and rocks in the same machine setting.
For sand, robustness guarantees for the makespan carry over to our objective.
Lemma 3. For sand, every algorithm that is γ \gamma γ -robust for the makespan is also γ \gamma γ -robust for the total completion time, using the same bags and Phase II assignment.
Speeds in { 0 , 1 } \{0,1\} { 0 , 1 }
We first consider speeds in { 0 , 1 } \{0,1\} { 0 , 1 } , where the adversary only chooses the number m ≤ M m \le M m ≤ M of available machines, all running at unit speed. Since SPT is optimal for m = 1 m = 1 m = 1 , and assigning jobs cyclically in non-increasing order of size to the bags is optimal for M = 2 M = 2 M = 2 , the challenge arises for M ≥ 3 M \ge3 M ≥ 3 : the bags should be nearly balanced for m = M m = M m = M , yet still allow balanced assignments when fewer machines are available.
For sand, we resolve this trade-off up to an additive 0.004: bag volumes following a linear profile yield a robustness factor of 28 / 27 28/27 28/27 , and no algorithm achieves a factor smaller than 31 / 30 31/30 31/30 (Theorems 1 and 2).
For bricks and rocks, we give a 13 / 12 13/12 13/12 -robust algorithm and show that no deterministic algorithm does better (Theorems 3 and 4). Omitted proofs are provided in Appendix § 7 .
Sand: linear bag profiles within 0.004 of optimal
For sand, we normalize the total volume to one, so that ∑ i = 1 M b i = 1 \sum_{i=1}^{M} b_i = 1 ∑ i = 1 M b i = 1 , and denote the resulting machine loads by y 1 , … , y m y_1,\ldots,y_m y 1 , … , y m . By § 2 , the ratio of a bag assignment on m m m machines is R ( m ) : = m ∑ i = 1 m y i 2 R(m) := m\sum_{i=1}^{m} y_i^2 R ( m ) := m ∑ i = 1 m y i 2 .
A simple algorithm already beats the makespan benchmark of 1.2071 (cf. Lemma 3): If all bags receive volume $1/M$ and Phase II distributes the bags as evenly as possible, then R ( m ) = 1 + r ( m − r ) / M 2 ≤ 9 / 8 R(m) = 1 + r(m-r)/M^2 \le9/8 R ( m ) = 1 + r ( m − r ) / M 2 ≤ 9/8 , where M = q m + r M = qm + r M = q m + r with 0 ≤ r < m 0 \le r < m 0 ≤ r < m . This is tight for M = 4 M = 4 M = 4 and $m = 3 (Observation 5 in App. § 7 .§ 1 ).
For M / 2 < m < M M/2 < m < M M /2 < m < M , equal bags lose because some machines must receive two bags and thus carry twice the load of others. Unequal bag volumes reduce this imbalance: small bags can be paired when fewer machines are available, while large bags remain alone.
Our algorithm uses bag volumes that follow a linear profile, ranging approximately from 2 / ( 3 M ) 2/(3M) 2/ ( 3 M ) to 4 / ( 3 M ) 4/(3M) 4/ ( 3 M ) .
Theorem 1. For sand and speeds in { 0 , 1 } \{0,1\} { 0 , 1 } , the linear-profile algorithm has an asymptotically tight robustness factor of 28 / 27 ≈ 1.0370 28/27 \approx1.0370 28/27 ≈ 1.0370 .
Proof (sketch). In Phase I, we use the linear profile x ( t ) = 2 ( 1 + t ) / 3 x(t) = 2(1+t)/3 x ( t ) = 2 ( 1 + t ) /3 , defining the bag volumes by b i = ∫ ( i − 1 ) / M i / M x ( t ) d t b_i = \int_{(i-1)/M}^{i/M} x(t)\,\mathrm{d}t b i = ∫ ( i − 1 ) / M i / M x ( t ) d t . For m > M / 2 m > M/2 m > M /2 , we pair the 2 ( M − m ) 2(M-m) 2 ( M − m ) smallest bags in opposite order, i.e., bag i i i with bag 2 ( M − m ) + 1 − i 2(M-m)+1-i 2 ( M − m ) + 1 − i , and assign the remaining bags individually. Since the bag volumes form an arithmetic progression, all pairs have equal total volume. Then, Jensen’s inequality bounds the contribution of the remaining bags, yielding an upper bound on R ( m ) R(m) R ( m ) that depends only on the fraction of bags that are paired. We show that this bound is at most 28 / 27 28/27 28/27 .
For m ≤ M / 2 m \le M/2 m ≤ M /2 , choose the smallest power of two h h h with h m > M / 2 hm > M/2 hm > M /2 . We first assign the bags to h m hm hm virtual machines as above and then merge groups of h h h machines. By Cauchy–Schwarz, the resulting ratio does not exceed that of the virtual assignment. □ \square □
For the lower bound, we use a fixed probability distribution over four machine counts with M = 12 M = 12 M = 12 bags. Cauchy–Schwarz yields an expected ratio of at least 31 / 30 31/30 31/30 for all bag constructions. By Yao’s principle the bound also holds for randomized algorithms.
Theorem 2. For sand and speeds in { 0 , 1 } \{0,1\} { 0 , 1 } , no algorithm for minimizing the total completion time achieves a robustness factor smaller than 31 / 30 ≈ 1.0333 31/30 \approx1.0333 31/30 ≈ 1.0333 .
Bricks and rocks: a tight bound of 13/12
We construct an algorithm for bricks whose guarantee holds simultaneously for every prefix of the sorted job sequence. Lemma 1 allows us to extend the guarantee to rocks.
Our algorithm 3:2-Cyclic sorts the jobs in non-increasing order of processing times. For M ≤ 2 M \le2 M ≤ 2 , it assigns jobs cyclically to the bags and the bags optimally to the available machines. Scheduling the jobs in SPT order is then optimal, as discussed above. For M ≥ 3 M \ge3 M ≥ 3 , let L : = ⌊ M / 2 ⌋ L := \lfloor M/2\rfloor L := ⌊ M /2 ⌋ and x : = 2 M + L = ⌊ 5 M / 2 ⌋ x := 2M + L = \lfloor5M/2\rfloor x := 2 M + L = ⌊ 5 M /2 ⌋ . In Phase I, we partition this sequence into consecutive packages of x x x jobs, with possibly fewer jobs in the last package. Within each package, we assign the jobs cyclically to the bags, starting with B 1 B_1 B 1 . Thus, each complete package contributes three jobs to each of the first L L L bags and two jobs to each of the remaining M − L M-L M − L bags. We call these long and short bags, respectively.
In Phase II, let K : = m ⌈ L / m ⌉ K := m\lceil L/m\rceil K := m ⌈ L / m ⌉ . We assign B 1 , … , B K B_1,\ldots,B_K B 1 , … , B K cyclically to the machines, starting with machine 1. Thus, all long bags are assigned, and every machine receives exactly ⌈ L / m ⌉ \lceil L/m\rceil ⌈ L / m ⌉ bags. The remaining bags are assigned in increasing bag-index order, cyclically in reverse machine order, starting with machine m m m . All bag labels are assigned, including those of empty bags. On each machine, we schedule the jobs in SPT order. A formal description and an illustration of both phases are given in Appendix § 7 .5.
The 3:2 pattern is the discrete version of a two-size construction for sand: volumes 3 / ( 2 M + L ) 3/(2M+L) 3/ ( 2 M + L ) for the first L L L bags and 2 / ( 2 M + L ) 2/(2M+L) 2/ ( 2 M + L ) for the others, assigned by longest-processing-time-first (LPT) in Phase II, give a tight robustness factor of 18/17 for sand. For bricks, the 3:2-Cyclic algorithm is asymptotically 18/17-robust as n → ∞ n \to\infty n → ∞ for every fixed M M M (Lemma 6 and Remark 1 in Appendix § 7 .§ 2 ). We use this pattern rather than the linear profile because it is easy to realize with integral bag loads and is consistent on prefixes of the job sequence, which we need for rocks. Since the lower bound of 13/12 for bricks exceeds both 18/17 and 28/27, a finer profile cannot improve the worst case.
For bricks, let b i : = ∣ B i ∣ b_i := |B_i| b i := ∣ B i ∣ denote the load of bag B i B_i B i , and let y i y_i y i denote the number of jobs assigned to machine i i i . We write Alg ( m , M ) \operatorname{Alg}(m,M) Alg ( m , M ) and Opt m \operatorname{Opt}_m Opt m for the algorithm’s cost and the unrestricted optimum on m m m identical machines, respectively.
Theorem 3. For speeds in { 0 , 1 } \{0,1\} { 0 , 1 } , the 3:2-Cyclic algorithm is 13/12-robust for minimizing the total completion time of bricks and rocks.
Proof (sketch). We first consider bricks with M ≥ 3 M \ge3 M ≥ 3 . The forward cyclic rounds yield non-increasing machine loads, while the reverse rounds add non-decreasing loads. Consequently, the machine loads differ by at most max { 1 , s } \max\{1,s\} max { 1 , s } , where s : = b L + 1 s := b_{L+1} s := b L + 1 is the largest short-bag load.
For s ≤ 2 s \le2 s ≤ 2 , the schedule is either optimal or has loads in { β , β + 1 , β + 2 } \{\beta,\beta+1,\beta+2\} { β , β + 1 , β + 2 } with β ≥ 2 \beta\ge2 β ≥ 2 . In the latter case, balancing each pair of extreme loads saves one unit of cost, while the balanced pair contributes at least 12, giving the factor 13/12. The same argument handles any later case with these three consecutive loads.
For the remaining cases, let y i y_i y i denote the load of machine i i i , and write y ˉ : = n / m \bar{y} := n/m y ˉ := n / m and V : = m − 1 ∑ i = 1 m ( y i − y ˉ ) 2 V := m^{-1}\sum_{i=1}^{m}(y_i-\bar{y})^2 V := m − 1 ∑ i = 1 m ( y i − y ˉ ) 2 . Since F ( k ) = k ( k + 1 ) / 2 F(k)=k(k+1)/2 F ( k ) = k ( k + 1 ) /2 , the algorithm’s cost is m ( V + y ˉ 2 + y ˉ ) / 2 m(V+\bar{y}^{2}+\bar{y})/2 m ( V + y ˉ 2 + y ˉ ) /2 . Convexity bounds the optimum from below by m ( y ˉ 2 + y ˉ ) / 2 m(\bar{y}^{2}+\bar{y})/2 m ( y ˉ 2 + y ˉ ) /2 , so
Alg ( m , M ) Opt m ≤ 1 + V y ˉ 2 + y ˉ . \frac{\operatorname{Alg}(m,M)}{\operatorname{Opt}_m} \le1+\frac{V}{\bar{y}^{2}+\bar{y}}. Opt m Alg ( m , M ) ≤ 1 + y ˉ 2 + y ˉ V .
It therefore suffices to show 12 V ≤ y ˉ 2 + y ˉ 12V \le\bar{y}^{2}+\bar{y} 12 V ≤ y ˉ 2 + y ˉ . For this, we distinguish whether a short bag is assigned alone. If not, every machine receives a long bag or at least two short bags. Thus, the minimum machine load β \beta β satisfies β ≥ 3 s / 2 − 1 \beta\ge3s/2-1 β ≥ 3 s /2 − 1 , and all machine loads belong to [ β , β + s ] [\beta,\beta+s] [ β , β + s ] . If a short bag is assigned alone, all long bags are assigned alone as well. Let a a a be the smallest load of a short bag assigned alone. All machine loads belong to [ a , 2 a ] [a,2a] [ a , 2 a ] , and the loads of the machines receiving long bags differ from 3 a / 2 3a/2 3 a /2 by at most one. These machines account for at least one third of all available machines. In both cases, we bound the squared deviations from the midpoint c c c of the respective interval and use
V = 1 m ∑ i = 1 m ( y i − c ) 2 − ( y ˉ − c ) 2 . V = \frac{1}{m}\sum_{i=1}^{m}(y_i-c)^2-(\bar{y}-c)^2. V = m 1 i = 1 ∑ m ( y i − c ) 2 − ( y ˉ − c ) 2 .
The resulting bounds yield 12 V ≤ y ˉ 2 + y ˉ 12V \le\bar{y}^{2}+\bar{y} 12 V ≤ y ˉ 2 + y ˉ for the remaining cases. Details are given in Appendix § 7 .5. The package boundaries and the assignment of bag labels are independent of n n n and the processing times. Thus, every prefix of the sorted job sequence is assigned as in the corresponding bricks instance, and Lemma 1 extends the guarantee to rocks.
We next show that the robustness factor of 13/12 is best possible, even for bricks.
Theorem 4. For speeds in { 0 , 1 } \{0,1\} { 0 , 1 } , no deterministic algorithm for minimizing the total completion time of bricks achieves a robustness factor smaller than 13/12. For rocks, the same lower bound holds for every n ≥ 6 n \ge6 n ≥ 6 .
Proof. Consider n = 6 n=6 n = 6 unit jobs and M = 3 M=3 M = 3 bags. If the bag loads are balanced, each bag contains two jobs. The adversary chooses m = 2 m=2 m = 2 , for which the best possible machine loads for the algorithm are ( 4 , 2 ) (4,2) ( 4 , 2 ) . Thus, Alg ( 2 , 3 ) / Opt 2 ≥ 13 / 12 \operatorname{Alg}(2,3)/\operatorname{Opt}_{2} \ge13/12 Alg ( 2 , 3 ) / Opt 2 ≥ 13/12 . Otherwise, the adversary chooses m = 3 m=3 m = 3 . Since some bag contains at least three jobs, the algorithm’s cost is at least that of machine loads ( 3 , 2 , 1 ) (3,2,1) ( 3 , 2 , 1 ) . Hence, Alg ( 3 , 3 ) / Opt 3 ≥ 10 / 9 > 13 / 12 \operatorname{Alg}(3,3)/\operatorname{Opt}_{3} \ge10/9 > 13/12 Alg ( 3 , 3 ) / Opt 3 ≥ 10/9 > 13/12 .
For rocks and every n ≥ 7 n \ge7 n ≥ 7 , adding n − 6 n-6 n − 6 jobs of size ε > 0 \varepsilon> 0 ε > 0 and letting ε → 0 \varepsilon\to0 ε → 0 yields the same lower bound (Appendix § 7 .6).
General Speeds
We now study general speeds, where the adversary chooses the individual machine speeds rather than just the number of available machines. We show that general speeds are strictly harder (Theorem 5), give a common 25/16-robust algorithm for sand, bricks, and rocks that is tight for its bag constructions (Theorem 6), and improve the guarantee for sand using bags of different volumes (Theorem 7).
Throughout this section, we normalize the total speed to one, which does not affect robustness factors. Ties are broken according to a fixed order on the machines. Omitted proofs can be found in Appendix § 8 .
General speeds are strictly harder
We first present a lower bound for sand that holds even with an optimal Phase II assignment. For M ≥ 2 M \ge2 M ≥ 2 , given the bag volumes b 1 , … , b M b_1,\ldots,b_M b 1 , … , b M chosen in Phase I, the adversary chooses M − 1 M-1 M − 1 slow machines of speed σ / ( M − 1 ) \sigma/(M-1) σ / ( M − 1 ) and one fast machine of speed 1 − σ 1-\sigma 1 − σ , where 0 < σ ≤ ( M − 1 ) / M 0 < \sigma\le(M-1)/M 0 < σ ≤ ( M − 1 ) / M . Thus, σ \sigma σ is the total speed of the slow machines.
Assigning bags to slow machines reduces the volume processed by the fast machine, but incurs a cost depending on the squared volumes of these bags. The adversary chooses the total speed σ \sigma σ of the slow machines to exploit this trade-off.
Theorem 5. For general speeds, no deterministic algorithm for minimizing the total completion time of sand achieves a robustness factor smaller than γ = ( 1 − 1 2 e − 3 / 2 ) − 2 > 1. 2669 \gamma=(1-\frac{1}{2}e^{-3/2})^{-2}>1. 2669 γ = ( 1 − 2 1 e − 3/2 ) − 2 > 1.2669 , uniformly over the number of machines.
Proof (sketch). Fix the bag volumes chosen in Phase I. For a prescribed total volume u u u assigned to the slow machines, we relax the choice of bags by allowing fractional selections. Let q ( u ) q(u) q ( u ) be the minimum of ( M − 1 ) ∑ r z r b r 2 (M-1)\sum_r z_r b_r^2 ( M − 1 ) ∑ r z r b r 2 subject to ∑ r z r b r = u \sum_r z_r b_r=u ∑ r z r b r = u and 0 ≤ z r ≤ 1 0 \le z_r \le1 0 ≤ z r ≤ 1 . Since selecting a bag of positive volume b r b_r b r has a relaxed cost of ( M − 1 ) b r (M-1)b_r ( M − 1 ) b r per unit of selected volume, the minimum is attained by selecting bags in non-decreasing order of volume with at most one bag selected fractionally. Dropping cross terms between bags assigned to the same slow machine and applying this relaxation shows that every Phase II assignment that sends a total volume of u u u to the slow machines has ratio at least
q ( u ) σ + ( 1 − u ) 2 1 − σ . \frac{q(u)}{\sigma}+\frac{(1-u)^2}{1-\sigma}. σ q ( u ) + 1 − σ ( 1 − u ) 2 .
The function q q q is convex and each positive bag volume b r b_r b r contributes a segment of length b r b_r b r and slope ( M − 1 ) b r (M-1)b_r ( M − 1 ) b r . Hence,
∫ 0 1 d u q ′ ( u ) = ∣ { r : b r > 0 } ∣ M − 1 ≤ M M − 1 . \int_0^1 \frac{du}{q'(u)}=\frac{|\{r:b_r>0\}|}{M-1}\leq\frac{M}{M-1}. ∫ 0 1 q ′ ( u ) d u = M − 1 ∣ { r : b r > 0 } ∣ ≤ M − 1 M .
Thus, each positive bag contributes exactly 1 / ( M − 1 ) 1/(M-1) 1/ ( M − 1 ) , independently of its volume.
Suppose that the fixed bags admit a ratio of at most ρ \rho ρ for every speed vector. We show that this requires q ( u ) ≤ ( u + ρ − 1 ) 2 q(u)\leq(u+\sqrt{\rho}-1)^2 q ( u ) ≤ ( u + ρ − 1 ) 2 for every u u u . If this inequality fails, we construct a speed vector for which every assignment has ratio above ρ \rho ρ , using either uniform speeds or a tangent to q q q . Using convexity and q ( 0 ) = 0 q(0)=0 q ( 0 ) = 0 , we show that this upper bound on q q q implies that the reciprocal-slope integral is larger than M / ( M − 1 ) M/(M-1) M / ( M − 1 ) whenever ρ < γ \rho<\gamma ρ < γ and M M M is sufficiently large. This contradicts the upper bound on the integral above.
By Observation 2, this extends to bricks and rocks and exceeds our factor 13/12 for rocks with { 0 , 1 } \{0,1\} { 0 , 1 } -speeds (Theorem 3). So general speeds are strictly harder than { 0 , 1 } \{0,1\} { 0 , 1 } -speeds.
Balanced and cyclic bags: a tight 25/16 guarantee
We next present a common algorithm for sand, bricks and rocks. For sand, we distribute the volume equally among the M M M bags, so each bag has volume 1 / M 1/M 1/ M .
For bricks and rocks, order the jobs in Phase I so that p 1 ≥ ⋯ ≥ p n p_1\geq\cdots\geq p_n p 1 ≥ ⋯ ≥ p n and assign them cyclically to B 1 , … , B M B_1,\ldots,B_M B 1 , … , B M . That is,
B r = { r , r + M , r + 2 M , … } ∩ [ n ] , r ∈ [ M ] . B_r=\{r,r+M,r+2M,\ldots\}\cap[n],\qquad r\in[M]. B r = { r , r + M , r + 2 M , … } ∩ [ n ] , r ∈ [ M ] .
Assigning one of these bags to each of M M M identical machines and processing its jobs in SPT order gives an optimal schedule. The same holds after restricting the construction to any prefix of the jobs in this order. In particular, for every prefix the job counts of bags differ by at most one. This property will allow us to transfer the guarantee for bricks to rocks using Lemma 1. This order of the jobs is used only to construct the bags.
In Phase II, let x i x_i x i denote the number of bags already assigned to machine i i i . We initialize x i = 0 x_i=0 x i = 0 and assign all M M M bag labels B 1 , … , B M B_1,\ldots,B_M B 1 , … , B M in this order, including those of empty bags. For each bag, choose an available machine minimizing the marginal value
( x i + 1 ) 2 − x i 2 s i = 2 x i + 1 s i . \frac{(x_i+1)^2-x_i^2}{s_i}=\frac{2x_i+1}{s_i}. s i ( x i + 1 ) 2 − x i 2 = s i 2 x i + 1 .
and increase x i x_i x i by one. We call this the quadratic marginal assignment . This rule minimizes the increase in ∑ i x i 2 / s i \sum_i x_i^2/s_i ∑ i x i 2 / s i , which is proportional to the cost for balanced sand bags. For bricks and rocks, we use the same rule which depends only on bag counts and machine speeds. Once the bag-to-machine assignment is fixed, we process jobs on each machine in SPT order. We call the resulting algorithms the cyclic-bag algorithm for bricks and rocks and the balanced-bag algorithm for sand.
Theorem 6. For general speeds, the balanced-bag algorithm for sand and the cyclic-bag algorithm for bricks and rocks are 25/16-robust for minimizing the total completion time. This bound is tight uniformly over the number of machines for these bag constructions, even with an optimal Phase II assignment.
Proof (Upper bound for sand). Let x i x_i x i be the final number of bags on machine i i i . Since every bag has volume 1 / M 1/M 1/ M and the total speed is one, the algorithm’s ratio is
R ( s ) = 1 M 2 ∑ i = 1 m x i 2 s i . R(s)=\frac{1}{M^2}\sum_{i=1}^{m}\frac{x_i^2}{s_i}. R ( s ) = M 2 1 i = 1 ∑ m s i x i 2 .
Let λ > 0 \lambda>0 λ > 0 denote the marginal value selected when assigning the last bag B M B_M B M . The marginal values on each machine increase, so the values selected by the algorithm are non-decreasing. If x i > 0 x_i>0 x i > 0 , the last selected value on machine i i i is ( 2 x i − 1 ) / s i (2x_i-1)/s_i ( 2 x i − 1 ) / s i , while its next unselected value is ( 2 x i + 1 ) / s i (2x_i+1)/s_i ( 2 x i + 1 ) / s i . Hence,
2 x i − 1 s i ≤ λ ≤ 2 x i + 1 s i . \frac{2x_i-1}{s_i}\leq\lambda\leq\frac{2x_i+1}{s_i}. s i 2 x i − 1 ≤ λ ≤ s i 2 x i + 1 .
Thus, ∣ 2 x i − λ s i ∣ ≤ 1 \lvert2x_i-\lambda s_i\rvert\leq1 ∣ 2 x i − λ s i ∣ ≤ 1 and λ s i ≥ 2 x i − 1 ≥ 1 \lambda s_i\geq2x_i-1\geq1 λ s i ≥ 2 x i − 1 ≥ 1 . If x i = 0 x_i=0 x i = 0 , the first marginal value remains unselected, so 0 < λ s i ≤ 1 0<\lambda s_i\leq1 0 < λ s i ≤ 1 . In either case, ( 2 x i − λ s i ) 2 ≤ λ s i (2x_i-\lambda s_i)^2\leq\lambda s_i ( 2 x i − λ s i ) 2 ≤ λ s i . Rearranging gives
x i 2 s i ≤ λ x i + λ 4 − λ 2 s i 4 . \frac{x_i^2}{s_i}\leq\lambda x_i+\frac{\lambda}{4}-\frac{\lambda^2s_i}{4}. s i x i 2 ≤ λ x i + 4 λ − 4 λ 2 s i .
Summing over all available machines, including those receiving no bags, and using ∑ i x i = M \sum_i x_i=M ∑ i x i = M and ∑ i s i = 1 \sum_i s_i=1 ∑ i s i = 1 , we obtain
R ( s ) ≤ λ ( 4 M + m − λ ) 4 M 2 = ( 4 M + m ) 2 − ( 2 λ − 4 M − m ) 2 16 M 2 ≤ ( 4 M + m ) 2 16 M 2 ≤ 25 16 , R(s)\leq\frac{\lambda(4M+m-\lambda)}{4M^2}
=\frac{(4M+m)^2-(2\lambda-4M-m)^2}{16M^2}
\leq\frac{(4M+m)^2}{16M^2}
\leq\frac{25}{16}, R ( s ) ≤ 4 M 2 λ ( 4 M + m − λ ) = 16 M 2 ( 4 M + m ) 2 − ( 2 λ − 4 M − m ) 2 ≤ 16 M 2 ( 4 M + m ) 2 ≤ 16 25 ,
where the last inequality follows from m ≤ M m\leq M m ≤ M .
Proof (sketch for upper bound for bricks and rocks). For bricks, we must also account for the linear term in F ( k ) = k ( k + 1 ) / 2 F(k)=k(k+1)/2 F ( k ) = k ( k + 1 ) /2 and the possible difference in bag sizes. Write n = q M + ℓ n=qM+\ell n = q M + ℓ , where 0 ≤ ℓ < M 0\leq\ell<M 0 ≤ ℓ < M . The first ℓ \ell ℓ bags contain q + 1 q+1 q + 1 jobs and the remaining bags contain q q q jobs. Let u i u_i u i and x i x_i x i denote the bag counts on machine i i i after ℓ \ell ℓ and M M M assignments, respectively. Machine i i i then processes k i = q x i + u i k_i=qx_i+u_i k i = q x i + u i jobs. Both count vectors satisfy the threshold inequalities used for sand, with their respective thresholds. We define the threshold for zero steps to be zero.
The algorithm and the optimum may assign different numbers of jobs to a machine, so we cannot compare their costs separately on each machine. Instead, we allow correction terms whose total over all machines is non-positive. Let z i z_i z i be the number of jobs on machine i i i in an unrestricted optimal schedule. Using the two sets of threshold inequalities, we prove in Appendix § 8 .§ 2 that there are nonnegative values P , G P,G P , G , common to all machines, such that
F ( k i ) s i ≤ 25 16 F ( z i ) s i + P ( k i − z i ) + G ( 1 − x i ) . \frac{F(k_i)}{s_i}\leq\frac{25}{16}\frac{F(z_i)}{s_i}+P(k_i-z_i)+G(1-x_i). s i F ( k i ) ≤ 16 25 s i F ( z i ) + P ( k i − z i ) + G ( 1 − x i ) .
After summing over all machines, the job-count corrections cancel because both schedules process n n n jobs. The bag count corrections sum to G ( m − M ) ≤ 0 G(m-M)\leq0 G ( m − M ) ≤ 0 , giving the desired bound. For rocks, both phases of the algorithm are consistent on prefixes of the job sequence, so Lemma 1 applies as for Theorem 3.
Tightness is shown in Appendix § 8 .§ 3 : with one fast machine of speed 3 M / ( 5 M − 2 ) 3M/(5M-2) 3 M / ( 5 M − 2 ) and M − 1 M-1 M − 1 equally slow ones, even an optimal assignment of balanced bags puts about 3 / 4 3/4 3/4 of the volume on the fast machine, although its share of the speed tends to 3 / 5 3/5 3/5 .
Imbalanced bags for sand
The tightness of 25/16 for balanced bags (Theorem 6) shows that improving the guarantee requires a different Phase I construction. With balanced bags, every machine that is used receives a volume of at least 1 / M 1/M 1/ M . Smaller bags allow us to assign less volume to slow machines, while larger bags carry the remaining volume. For sand, we use this flexibility to obtain an improved guarantee.
In Phase I, let h = ⌊ M / 2 ⌋ h = \lfloor M/2\rfloor h = ⌊ M /2 ⌋ . We create h h h bags of volume 3 / ( 4 M ) 3/(4M) 3/ ( 4 M ) and h h h bags of volume 5 / ( 4 M ) 5/(4M) 5/ ( 4 M ) . If M M M is odd, we add one intermediate bag of volume 1 / M 1/M 1/ M . In either case, there are M M M bags of total volume one. Let b 1 , … , b M b_1,\ldots,b_M b 1 , … , b M denote their volumes.
In Phase II, we first determine the number of bags assigned to each machine, independently of the bag volumes. Starting with x i = 0 x_i = 0 x i = 0 , we repeat the following M M M times: choose an available machine minimizing
3 x i + 1 s i \frac{3x_i+1}{s_i} s i 3 x i + 1
and increase x i x_i x i by one. The selection score for the first bag on machine i i i is still 1 / s i 1/s_i 1/ s i , while each assigned bag increases the next score by 3 / s i 3/s_i 3/ s i instead of 2 / s i 2/s_i 2/ s i . Compared with the quadratic marginal assignment, this makes choosing an unused machine relatively cheaper than adding another bag to an occupied machine.
After fixing the counts, we determine the explicit bag-to-machine assignment. We order the machines with x i > 0 x_i > 0 x i > 0 in non-increasing order of x i / s i x_i/s_i x i / s i and the bags by non-decreasing volume. In this order, each machine receives the x i x_i x i smallest remaining bags. Thus, machines with less speed per assigned bag receive smaller bags, whereas machines with more speed per assigned bag receive larger bags. We call the resulting algorithm the imbalanced-bag algorithm .
Theorem 7. For general speeds, the imbalanced-bag algorithm is 1681/1152-robust for minimizing the total completion time of sand, where 1681/1152 ≈ 1.4592.
Proof (sketch). The bag volumes satisfy M ∑ r b r 2 ≤ 17 / 16 M\sum_{r} b_r^2 \le17/16 M ∑ r b r 2 ≤ 17/16 , so their total squared volume is at most 17 / 16 17/16 17/16 times that of balanced bags. To obtain an improved guarantee, we also account for how the small and large bags are assigned. By Cauchy–Schwarz, the contribution of machine i i i to the ratio R ( s ) R(s) R ( s ) satisfies
( ∑ r : π ( r ) = i b r ) 2 s i ≤ x i s i ∑ r : π ( r ) = i b r 2 . \frac{\left(\sum_{r:\pi(r)=i} b_r\right)^2}{s_i} \le\frac{x_i}{s_i}\sum_{r:\pi(r)=i} b_r^2. s i ( ∑ r : π ( r ) = i b r ) 2 ≤ s i x i r : π ( r ) = i ∑ b r 2 .
For the chosen counts, our assignment minimizes the sum of these upper bounds by pairing the smaller squared bag volumes with the larger coefficients x i / s i x_i/s_i x i / s i .
Let λ \lambda λ be the largest score selected when fixing the bag counts. For a bag r r r assigned to machine i i i , set t r = max { 1 / 3 , x i / ( λ s i ) } t_r = \max\{1/3,x_i/(\lambda s_i)\} t r = max { 1/3 , x i / ( λ s i )} . The count rule gives t r ∈ [ 1 / 3 , 1 ] t_r \in[1/3,1] t r ∈ [ 1/3 , 1 ] . Indexing the bags by non-decreasing volume, our assignment gives t 1 ≥ ⋯ ≥ t M t_1 \ge\cdots\ge t_M t 1 ≥ ⋯ ≥ t M . Using the Cauchy–Schwarz bound and the threshold inequalities for all available machines, including those with x i = 0 x_i = 0 x i = 0 , we obtain
R ( s ) ≤ λ ∑ r = 1 M t r b r 2 ≤ ( ∑ r = 1 M ( 3 2 t r − 1 2 ) ) ( ∑ r = 1 M t r b r 2 ) . R(s) \le\lambda\sum_{r=1}^{M}t_r b_r^2 \le\left(\sum_{r=1}^{M}\left(\frac{3}{2t_r}-\frac{1}{2}\right)\right)\left(\sum_{r=1}^{M}t_r b_r^2\right). R ( s ) ≤ λ r = 1 ∑ M t r b r 2 ≤ ( r = 1 ∑ M ( 2 t r 3 − 2 1 ) ) ( r = 1 ∑ M t r b r 2 ) .
The first inequality follows from Cauchy–Schwarz and the definition of t r t_r t r . The threshold inequalities bound λ \lambda λ by the first factor in the product.
We maximize this upper bound over all ordered coefficients in [ 1 / 3 , 1 ] [1/3,1] [ 1/3 , 1 ] . For fixed bag volumes, the product is convex when equal coefficients are varied together while preserving their order. Hence, its maximum over ordered coefficients is attained when the first k k k coefficients equal 1 and the remaining coefficients equal 1 / 3 1/3 1/3 .
The resulting bound depends on the sum of squared volumes of all bags and the corresponding sum for the k k k smallest bags. Substituting the bag volumes gives two quadratic expressions in k / M k/M k / M , according to whether k ≤ M / 2 k \le M/2 k ≤ M /2 or k ≥ M / 2 k \ge M/2 k ≥ M /2 . Both are bounded by 1681/1152. For odd M M M , the intermediate bag preserves the same estimates on these sums of squared volumes. ∐
Acknowledgments. This work was supported by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany’s Excellence Strategy – EXC 3036 The Martian Mindset – project number 533607631.
AI Disclosure The results for identical machines in § 3 were developed primarily by the authors. The authors developed the sand lower bound for general speeds in Theorem 5, the balanced-bag upper bound for sand in Theorem 6, and the prefix transfer in Lemma 1. Their construction for identical machines motivated the imbalanced bags in Theorem 7. They also developed the non-adaptive results in Appendix § 9 .§ 1 and, for the strong-adversary variants in Appendix § 9 .§ 2 , the impossibility result for general speeds, the indivisible variant and its 9/8 upper bound for sand, and the lower bound for bricks and rocks in Theorem 13 .
ChatGPT Astra generated initial proof ideas and assisted with checking and simplifying proofs, including those for identical machines. It generated the initial proof for bricks in Theorem 6 and drafted the initial proof of Theorem 7 based on the authors’ imbalanced-bag idea. The algorithm and proof in Theorem 11 and the sand lower bound in Theorem 13 were also initially AI-generated. The authors substantially revised and simplified these proofs, including their technical arguments and, for bricks, the presentation of the scheduling intuition. ChatGPT Astra and Claude Opus 5.5 also assisted with manuscript review, presentation, and structure. The authors take full responsibility for the content and correctness of this work. They grant reviewers permission to upload this submission to generative AI services for the purpose of peer review.
Appendices
Transfer results
From bricks to rocks {#sec:A.1} (Lemma 1)
Lemma 1. Fix an instance I I I with p 1 ≥ ⋯ ≥ p n p_1 \ge\cdots\ge p_n p 1 ≥ ⋯ ≥ p n and speeds s s s . Consider an algorithm’s assignment A A A on ( I , s ) (I,s) ( I , s ) . Suppose that, for every r ∈ [ n ] r \in[n] r ∈ [ n ] , restricting A A A to the jobs 1 , … , r 1,\ldots,r 1 , … , r and setting their processing times to one gives a schedule of cost at most α \alpha α times the unrestricted optimum for r r r unit-size jobs and speeds s s s . Then ALG ( I , s ) ≤ α OPT ( I , s ) \operatorname{ALG}(I,s) \le\alpha\operatorname{OPT}(I,s) ALG ( I , s ) ≤ α OPT ( I , s ) .
Proof. Fix an instance I I I with processing times p 1 ≥ ⋯ ≥ p n p_1 \ge\cdots\ge p_n p 1 ≥ ⋯ ≥ p n and a revealed speed vector s s s . Set p n + 1 = 0 p_{n+1}=0 p n + 1 = 0 , and consider the assignment produced by the algorithm. For every r ∈ [ n ] r \in[n] r ∈ [ n ] , let A r A_r A r denote the cost of restricting this assignment to the first r r r jobs and setting their processing times to one. Similarly, let OPT r ( s ) \operatorname{OPT}_r(s) OPT r ( s ) be the unrestricted optimum for r r r unit-size jobs and speed vector s s s . By assumption, A r ≤ α OPT r ( s ) A_r \le\alpha\operatorname{OPT}_r(s) A r ≤ α OPT r ( s ) .
We now decompose the processing times in the original instance into layers. For every r ∈ [ n ] r \in[n] r ∈ [ n ] , the layer of height p r − p r + 1 p_r-p_{r+1} p r − p r + 1 contributes to precisely the first r r r jobs. Whenever p r − p r + 1 > 0 p_r-p_{r+1}>0 p r − p r + 1 > 0 , these jobs form a suffix of the SPT schedule on each machine. If machine i i i contains h h h of them, the layer contributes
p r − p r + 1 s i ( 1 + ⋯ + h ) = ( p r − p r + 1 ) h ( h + 1 ) 2 s i \frac{p_r-p_{r+1}}{s_i}(1+\cdots+h)=(p_r-p_{r+1})\frac{h(h+1)}{2s_i} s i p r − p r + 1 ( 1 + ⋯ + h ) = ( p r − p r + 1 ) 2 s i h ( h + 1 )
to its total completion time. Summing over all machines and layers gives
ALG ( I , s ) = ∑ r = 1 n ( p r − p r + 1 ) A r ≤ α ∑ r = 1 n ( p r − p r + 1 ) OPT r ( s ) . \operatorname{ALG}(I,s)=\sum_{r=1}^{n}(p_r-p_{r+1})A_r\le\alpha\sum_{r=1}^{n}(p_r-p_{r+1})\operatorname{OPT}_r(s). ALG ( I , s ) = r = 1 ∑ n ( p r − p r + 1 ) A r ≤ α r = 1 ∑ n ( p r − p r + 1 ) OPT r ( s ) .
We can apply the same decomposition to an unrestricted optimal SPT schedule for instance I I I . For every r r r , restricting its assignment to the first r r r jobs and setting their processing times to one gives a feasible schedule of cost at least OPT r ( s ) \operatorname{OPT}_r(s) OPT r ( s ) . Hence,
OPT ( I , s ) ≥ ∑ r = 1 n ( p r − p r + 1 ) OPT r ( s ) . \operatorname{OPT}(I,s)\ge\sum_{r=1}^{n}(p_r-p_{r+1})\operatorname{OPT}_r(s). OPT ( I , s ) ≥ r = 1 ∑ n ( p r − p r + 1 ) OPT r ( s ) .
Combining the two inequalities yields ALG ( I , s ) ≤ α OPT ( I , s ) \operatorname{ALG}(I,s)\le\alpha\operatorname{OPT}(I,s) ALG ( I , s ) ≤ α OPT ( I , s ) . □ \square □
From sand to bricks and rocks {#sec:A.2} (Observation 2)
Observation 4 For every fixed number of bags, every lower bound on the optimal robustness factor for sand also holds for bricks and rocks in the same machine setting.
Proof. Fix M M M , and let γ \gamma γ be a lower bound on the robustness factor for sand. Consider any algorithm for bricks and an instance I n I_n I n consisting of n n n unit-size jobs. After Phase I, interpret a bag containing b b b jobs as a sand bag of volume b / n b/n b / n . These volumes sum to one.
Fix ε > 0 \varepsilon>0 ε > 0 . By the lower bound for sand, there is an admissible speed vector s s s for which every assignment of these bags has ratio at least γ − ε \gamma-\varepsilon γ − ε . Write S : = ∑ i s i S:=\sum_i s_i S := ∑ i s i . If the algorithm assigns a i a_i a i jobs to machine i i i , the corresponding sand load is a i / n a_i/n a i / n . Hence,
ALG ( I n , s ) = ∑ i : s i > 0 a i ( a i + 1 ) 2 s i ≥ ∑ i : s i > 0 a i 2 2 s i ≥ ( γ − ε ) n 2 2 S . \operatorname{ALG}(I_n,s)=\sum_{i:s_i>0}\frac{a_i(a_i+1)}{2s_i}\ge\sum_{i:s_i>0}\frac{a_i^2}{2s_i}\ge\frac{(\gamma-\varepsilon)n^2}{2S}. ALG ( I n , s ) = i : s i > 0 ∑ 2 s i a i ( a i + 1 ) ≥ i : s i > 0 ∑ 2 s i a i 2 ≥ 2 S ( γ − ε ) n 2 .
To bound the unrestricted optimum, assign each job independently to machine i i i with probability s i / S s_i/S s i / S . Let X i X_i X i denote the resulting number of jobs on machine i i i , and let m ≤ M m \le M m ≤ M be the number of positive-speed machines. Since
E [ X i ( X i + 1 ) ] = n ( n − 1 ) ( s i S ) 2 + 2 n s i S , \mathbb{E}[X_i(X_i+1)] = n(n-1)\left(\frac{s_i}{S}\right)^2 + 2n\frac{s_i}{S}, E [ X i ( X i + 1 )] = n ( n − 1 ) ( S s i ) 2 + 2 n S s i ,
the expected total completion time is
∑ i : s i > 0 E [ X i ( X i + 1 ) ] 2 s i = n ( n − 1 ) 2 S + n m S ≤ n ( n + 2 M − 1 ) 2 S . \sum_{i:s_i>0}\frac{\mathbb{E}[X_i(X_i+1)]}{2s_i}
= \frac{n(n-1)}{2S} + \frac{nm}{S}
\le\frac{n(n+2M-1)}{2S}. i : s i > 0 ∑ 2 s i E [ X i ( X i + 1 )] = 2 S n ( n − 1 ) + S nm ≤ 2 S n ( n + 2 M − 1 ) .
Some assignment has cost at most this expectation, so the same upper bound holds for Opt ( I n , s ) \operatorname{Opt}(I_n,s) Opt ( I n , s ) . Consequently,
Alg ( I n , s ) Opt ( I n , s ) ≥ ( γ − ε ) n n + 2 M − 1 . \frac{\operatorname{Alg}(I_n,s)}{\operatorname{Opt}(I_n,s)}
\ge(\gamma-\varepsilon)\frac{n}{n+2M-1}. Opt ( I n , s ) Alg ( I n , s ) ≥ ( γ − ε ) n + 2 M − 1 n .
Letting n n n tend to infinity and then ε \varepsilon ε tend to zero proves the lower bound for bricks. The bound for rocks follows because bricks are a special case. □ \square □
From makespan to total completion time {#sec:A.3} (Lemma 3)
Lemma 3. For sand, every algorithm that is γ \gamma γ -robust for the makespan is also γ \gamma γ -robust for the total completion time, using the same bags and Phase II assignment.
Proof. Let S : = ∑ i s i S := \sum_i s_i S := ∑ i s i , and let y i y_i y i denote the volume assigned to machine i i i by the algorithm. Since the total volume is one, the optimal makespan is 1 / S 1/S 1/ S . The algorithm’s makespan
T : = max i : s i > 0 y i s i T := \max_{i:s_i>0}\frac{y_i}{s_i} T := i : s i > 0 max s i y i
therefore satisfies T ≤ γ / S T \le\gamma/S T ≤ γ / S . Using Opt ( s ) = 1 / ( 2 S ) \operatorname{Opt}(s) = 1/(2S) Opt ( s ) = 1/ ( 2 S ) , we obtain
Alg ( s ) Opt ( s ) = S ∑ i : s i > 0 y i 2 s i ≤ S T ∑ i : s i > 0 y i = S T ≤ γ . \frac{\operatorname{Alg}(s)}{\operatorname{Opt}(s)}
= S\sum_{i:s_i>0}\frac{y_i^2}{s_i}
\le ST\sum_{i:s_i>0}y_i
= ST \le\gamma. Opt ( s ) Alg ( s ) = S i : s i > 0 ∑ s i y i 2 ≤ S T i : s i > 0 ∑ y i = S T ≤ γ .
□ \square □
Proofs for speeds in { 0 , 1 } \{0,1\} { 0 , 1 } (§ 3 )
Equal bags for sand (Observation 5)
Observation 5 For speeds in { 0 , 1 } \{0,1\} { 0 , 1 } , the algorithm that distributes sand equally among the bags and assigns them as evenly as possible in Phase II is 9 / 8 9/8 9/8 -robust for minimizing the total completion time. This bound is tight for the algorithm.
Proof. Write M = q m + r M = qm + r M = q m + r with q ≥ 1 q \ge1 q ≥ 1 and 0 ≤ r < m 0 \le r < m 0 ≤ r < m . In Phase II, each machine receives q q q bags, and r r r machines receive one additional bag. Only these additional bags cause an imbalance between the machine loads since all bags have size 1 / M 1/M 1/ M . Consequently,
R ( m ) = m M 2 ( ( m − r ) q 2 + r ( q + 1 ) 2 ) = 1 + r ( m − r ) M 2 . R(m) = \frac{m}{M^2}\left((m-r)q^2+r(q+1)^2\right)
= 1+\frac{r(m-r)}{M^2}. R ( m ) = M 2 m ( ( m − r ) q 2 + r ( q + 1 ) 2 ) = 1 + M 2 r ( m − r ) .
Since M = m q + r ≥ m + r M=mq+r\ge m+r M = m q + r ≥ m + r , we obtain
R ( m ) ≤ 1 + r ( m − r ) ( m + r ) 2 . R(m)\le1+\frac{r(m-r)}{(m+r)^2}. R ( m ) ≤ 1 + ( m + r ) 2 r ( m − r ) .
Moreover, ( m + r ) 2 − 8 r ( m − r ) = ( m − 3 r ) 2 ≥ 0 (m+r)^2-8r(m-r)=(m-3r)^2\ge0 ( m + r ) 2 − 8 r ( m − r ) = ( m − 3 r ) 2 ≥ 0 , and hence R ( m ) ≤ 1 + 1 / 8 = 9 / 8 R(m)\le1+1/8=9/8 R ( m ) ≤ 1 + 1/8 = 9/8 .
Observe that for M = 4 M=4 M = 4 and m = 3 m=3 m = 3 , the algorithm yields machine loads of ( 1 / 2 , 1 / 4 , 1 / 4 ) (1/2,1/4,1/4) ( 1/2 , 1/4 , 1/4 ) and the ratio is R ( 3 ) = 3 16 ( 2 2 + 1 2 + 1 2 ) = 9 / 8 R(3)=\frac{3}{16}(2^2+1^2+1^2)=9/8 R ( 3 ) = 16 3 ( 2 2 + 1 2 + 1 2 ) = 9/8 . Hence, the bound is tight. □ \square □
3:2 pattern for sand (Lemma 6)
We show that the robustness factor can be significantly improved even with the simple 3:2 pattern using two different bag sizes.
Lemma 6. For speeds in { 0 , 1 } \{0,1\} { 0 , 1 } , consider the algorithm that distributes sand equally among the bags for M ≤ 2 M \le2 M ≤ 2 and, for M ≥ 3 M \ge3 M ≥ 3 , uses two bag sizes in a ratio of 3:2, with the larger size assigned to the first ⌊ M / 2 ⌋ \lfloor M/2\rfloor ⌊ M /2 ⌋ bags. In Phase II, it assigns the bags in non-increasing order of volume to a least-loaded machine, breaking ties by machine index (LPT). This algorithm is 18/17-robust for minimizing the total completion time, and this bound is tight for the algorithm.
Proof. For M ≤ 2 M \le2 M ≤ 2 , the algorithm is optimal. Let M ≥ 3 M \ge3 M ≥ 3 , L : = ⌊ M / 2 ⌋ L := \lfloor M/2\rfloor L := ⌊ M /2 ⌋ , and T : = 2 M + L T := 2M + L T := 2 M + L . The algorithm uses L L L bags of volume 3 / T 3/T 3/ T and M − L M-L M − L bags of volume 2 / T 2/T 2/ T . For the analysis, multiply all volumes by T T T and write u i : = T y i u_i := T y_i u i := T y i for the resulting integer machine loads. Thus,
∑ i = 1 m u i = T and R ( m ) = m T 2 ∑ i = 1 m u i 2 . \sum_{i=1}^{m} u_i = T \qquad\text{and}\qquad R(m) = \frac{m}{T^2}\sum_{i=1}^{m} u_i^2. i = 1 ∑ m u i = T and R ( m ) = T 2 m i = 1 ∑ m u i 2 .
For m ≤ L m \le L m ≤ L , we bound the difference between machine loads. For m > L m > L m > L , the long bags occupy distinct machines, and we distinguish whether there are enough short bags to assign two to every remaining machine.
Case 1: m ≤ L m \le L m ≤ L . After assigning the bags of size 3, the machine loads are equal or differ by 3. In the latter case, each least loaded machine receives one bag of size 2 before any other machine does. There are enough such bags, since M − L ≥ m M-L \ge m M − L ≥ m , and the load difference becomes 1. Further assignments of bags of size 2 preserve a load difference of at most 2. The same bound holds if the loads were initially equal.
Let a : = min i u i a := \min_i u_i a := min i u i . Since the mean minimizes the sum of squared deviations,
∑ i = 1 m ( u i − T m ) 2 ≤ ∑ i = 1 m ( u i − a − 1 ) 2 ≤ m . \sum_{i=1}^{m}\left(u_i-\frac{T}{m}\right)^2 \le\sum_{i=1}^{m}(u_i-a-1)^2 \le m. i = 1 ∑ m ( u i − m T ) 2 ≤ i = 1 ∑ m ( u i − a − 1 ) 2 ≤ m .
Consequently,
R ( m ) = 1 + m T 2 ∑ i = 1 m ( u i − T m ) 2 ≤ 1 + m 2 T 2 ≤ 26 25 < 18 17 . R(m) = 1+\frac{m}{T^2}\sum_{i=1}^{m}\left(u_i-\frac{T}{m}\right)^2 \le1+\frac{m^2}{T^2}\le\frac{26}{25}<\frac{18}{17}. R ( m ) = 1 + T 2 m i = 1 ∑ m ( u i − m T ) 2 ≤ 1 + T 2 m 2 ≤ 25 26 < 17 18 .
where we used m ≤ L m \le L m ≤ L and T ≥ 5 L T \ge5L T ≥ 5 L .
Case 2: L < m ≤ ( M + L ) / 2 L < m \le(M+L)/2 L < m ≤ ( M + L ) /2 . The bags of size 3 are assigned to distinct machines. Since 2 ( m − L ) ≤ M − L 2(m-L) \le M-L 2 ( m − L ) ≤ M − L , LPT assigns two bags of size 2 to each of the other m − L m-L m − L machines. The remaining M + L − 2 m M+L-2m M + L − 2 m bags are assigned to machines of load 3. Thus, exactly m − L m-L m − L machines have load 4, and the remaining L L L machines have load 3 or 5. It follows that
∑ i = 1 m ( u i − 4 ) 2 = L , and hence ∑ i = 1 m u i 2 = 8 T − 16 m + L . \sum_{i=1}^{m}(u_i-4)^2=L,\qquad\text{and hence}\qquad\sum_{i=1}^{m}u_i^2=8T-16m+L. i = 1 ∑ m ( u i − 4 ) 2 = L , and hence i = 1 ∑ m u i 2 = 8 T − 16 m + L .
Since L / T ≤ 1 / 5 L/T \le1/5 L / T ≤ 1/5 , we obtain
R ( m ) = ( 8 + L T ) m T − 16 ( m T ) 2 ≤ 41 5 m T − 16 ( m T ) 2 ≤ 1681 1600 < 18 17 , \begin{aligned}
R(m)=\left(8+\frac{L}{T}\right)\frac{m}{T}-16\left(\frac{m}{T}\right)^2 \\
&\le\frac{41}{5}\frac{m}{T}-16\left(\frac{m}{T}\right)^2\le\frac{1681}{1600}<\frac{18}{17},
\end{aligned} R ( m ) = ( 8 + T L ) T m − 16 ( T m ) 2 ≤ 5 41 T m − 16 ( T m ) 2 ≤ 1600 1681 < 17 18 ,
where we bounded the quadratic by completing the square.
Case 3: ( M + L ) / 2 < m ≤ M (M+L)/2 < m \le M ( M + L ) /2 < m ≤ M . In this case, all long bags remain alone, while each remaining machine receives one or two short bags. Thus, exactly L L L machines have load 3, and the remaining machines have load 2 or 4.
First, suppose m < M m<M m < M . Then m ≤ M − 1 ≤ 2 L m\le M-1\le2L m ≤ M − 1 ≤ 2 L , so at least half the machines have load 3. Consequently,
∑ i = 1 m ( u i − 3 ) 2 = m − L ≤ m 2 . \sum_{i=1}^{m}(u_i-3)^2=m-L\le\frac{m}{2}. i = 1 ∑ m ( u i − 3 ) 2 = m − L ≤ 2 m .
and expanding the squares gives
∑ i = 1 m u i 2 ≤ 6 T − 17 2 m . \sum_{i=1}^{m}u_i^2\le6T-\frac{17}{2}m. i = 1 ∑ m u i 2 ≤ 6 T − 2 17 m .
It follows that
R ( m ) ≤ 6 m T − 17 2 ( m T ) 2 = 18 17 − 17 2 ( m T − 6 17 ) 2 ≤ 18 17 . \begin{aligned}
R(m)&\le6\frac{m}{T}-\frac{17}{2}\left(\frac{m}{T}\right)^2\\
&=\frac{18}{17}-\frac{17}{2}\left(\frac{m}{T}-\frac{6}{17}\right)^2\le\frac{18}{17}.
\end{aligned} R ( m ) ≤ 6 T m − 2 17 ( T m ) 2 = 17 18 − 2 17 ( T m − 17 6 ) 2 ≤ 17 18 .
For m = M m=M m = M , every bag is assigned separately, and
R ( M ) = 1 + L ( M − L ) T 2 ≤ 25 24 < 18 17 , R(M)=1+\frac{L(M-L)}{T^2}\le\frac{25}{24}<\frac{18}{17}, R ( M ) = 1 + T 2 L ( M − L ) ≤ 24 25 < 17 18 ,
where the inequality follows from
T 2 − 24 L ( M − L ) = ( 2 M − 5 L ) 2 ≥ 0. T^2-24L(M-L)=(2M-5L)^2\ge0. T 2 − 24 L ( M − L ) = ( 2 M − 5 L ) 2 ≥ 0.
For tightness, take M = 7 M=7 M = 7 and m = 6 m=6 m = 6 . The bag volumes are ( 3 , 3 , 3 , 2 , 2 , 2 , 2 ) / 17 (3,3,3,2,2,2,2)/17 ( 3 , 3 , 3 , 2 , 2 , 2 , 2 ) /17 , and LPT produces machine loads ( 4 , 3 , 3 , 3 , 2 , 2 ) / 17 (4,3,3,3,2,2)/17 ( 4 , 3 , 3 , 3 , 2 , 2 ) /17 . Thus,
R ( 6 ) = 6 17 2 ( 4 2 + 3 ⋅ 3 2 + 2 ⋅ 2 2 ) = 18 17 . R(6)=\frac{6}{17^2}\left(4^2+3\cdot3^2+2\cdot2^2\right)=\frac{18}{17}. R ( 6 ) = 1 7 2 6 ( 4 2 + 3 ⋅ 3 2 + 2 ⋅ 2 2 ) = 17 18 .
The lemma also determines the asymptotic behavior of the algorithm from § 3 for bricks.
Remark 1. For every fixed M ≥ 3 M\ge3 M ≥ 3 , the normalized bag loads converge to the two-size distribution of Lemma 6, and, on this limiting distribution, the Phase II assignment corresponds to LPT up to tie-breaking. Since F ( k ) = k 2 / 2 + O ( k ) F(k)=k^2/2+O(k) F ( k ) = k 2 /2 + O ( k ) , Algorithm 1 is asymptotically 18 / 17 18/17 18/17 -robust as n → ∞ n\to\infty n → ∞ , which is tight for M = 7 M=7 M = 7 and m = 6 m=6 m = 6 .
Linear bag profiles for sand (Theorem 1)
Theorem 1. For sand and speeds in { 0 , 1 } \{0,1\} { 0 , 1 } , the linear-profile algorithm has an asymptotically tight robustness factor of 28 / 27 ≈ 1.0370 28/27\approx1.0370 28/27 ≈ 1.0370 .
Proof. Let x ( t ) : = 2 ( 1 + t ) / 3 x(t):=2(1+t)/3 x ( t ) := 2 ( 1 + t ) /3 . In Phase I, we define the volume of bag B i B_i B i by
b i : = ∫ ( i − 1 ) / M i / M x ( t ) d t = 2 3 M + 2 i − 1 3 M 2 , i ∈ [ M ] . b_i:=\int_{(i-1)/M}^{i/M}x(t)\,\mathrm{d}t=\frac{2}{3M}+\frac{2i-1}{3M^2},\qquad i\in[M]. b i := ∫ ( i − 1 ) / M i / M x ( t ) d t = 3 M 2 + 3 M 2 2 i − 1 , i ∈ [ M ] . Thus, the bag volumes form an increasing arithmetic progression and sum to one.
We first reduce the analysis to M / 2 < m ≤ M M/2 < m \le M M /2 < m ≤ M . If m ≤ M / 2 m \le M/2 m ≤ M /2 , let h h h be the smallest power of two with h m > M / 2 hm > M/2 hm > M /2 . Then h m ≤ M hm \le M hm ≤ M , since ( h / 2 ) m ≤ M / 2 (h/2)m \le M/2 ( h /2 ) m ≤ M /2 . Phase II first assigns the bags to h m hm hm virtual machines using the pairing rule below, and then merges consecutive groups G 1 , … , G m G_1,\ldots,G_m G 1 , … , G m of h h h virtual machines each. If their loads are z 1 , … , z h m z_1,\ldots,z_{hm} z 1 , … , z hm , Cauchy–Schwarz gives
R ( m ) = m ∑ j = 1 m ( ∑ ℓ ∈ G j z ℓ ) 2 ≤ m h ∑ ℓ = 1 h m z ℓ 2 = R ( h m ) . R(m) = m\sum_{j=1}^{m}\left(\sum_{\ell\in G_j}z_\ell\right)^2 \le mh\sum_{\ell=1}^{hm}z_\ell^2 = R(hm). R ( m ) = m j = 1 ∑ m ℓ ∈ G j ∑ z ℓ 2 ≤ mh ℓ = 1 ∑ hm z ℓ 2 = R ( hm ) .
Thus, merging these groups cannot increase the ratio.
Now let M / 2 < m ≤ M M/2 < m \le M M /2 < m ≤ M , and put k : = M − m k := M-m k := M − m and s : = 2 k / M ∈ [ 0 , 1 ) s := 2k/M \in[0,1) s := 2 k / M ∈ [ 0 , 1 ) . Phase II pairs the 2 k 2k 2 k smallest bags in opposite order and assigns each pair and each remaining bag to a separate machine. There are k k k pairs and M − 2 k M-2k M − 2 k remaining bags, hence exactly m m m machines. All pairs have the same volume, since
b i + b 2 k + 1 − i = 4 ( M + k ) 3 M 2 = 2 ( 2 + s ) 3 M , 1 ≤ i ≤ k . b_i+b_{2k+1-i}=\frac{4(M+k)}{3M^2}=\frac{2(2+s)}{3M},\qquad1\le i\le k. b i + b 2 k + 1 − i = 3 M 2 4 ( M + k ) = 3 M 2 ( 2 + s ) , 1 ≤ i ≤ k .
It remains to bound the contribution of the bags assigned alone. For each such bag, let I i = [ ( i − 1 ) / M , i / M ] I_i=[(i-1)/M,i/M] I i = [( i − 1 ) / M , i / M ] . The average of x x x over I i I_i I i is M b i Mb_i M b i . Jensen’s inequality for z ↦ z 2 z\mapsto z^2 z ↦ z 2 bounds its square by the average of x 2 x^2 x 2 :
( M b i ) 2 = ( 1 ∣ I i ∣ ∫ I i x ( t ) d t ) 2 ≤ 1 ∣ I i ∣ ∫ I i x ( t ) 2 d t = M ∫ I i x ( t ) 2 d t . (Mb_i)^2=\left(\frac{1}{|I_i|}\int_{I_i}x(t)\,dt\right)^2\le\frac{1}{|I_i|}\int_{I_i}x(t)^2\,dt=M\int_{I_i}x(t)^2\,dt. ( M b i ) 2 = ( ∣ I i ∣ 1 ∫ I i x ( t ) d t ) 2 ≤ ∣ I i ∣ 1 ∫ I i x ( t ) 2 d t = M ∫ I i x ( t ) 2 d t .
Dividing by M 2 M^2 M 2 and summing over the remaining bags, whose intervals partition [ s , 1 ] [s,1] [ s , 1 ] , gives
∑ i = 2 k + 1 M b i 2 ≤ 1 M ∫ s 1 x ( t ) 2 d t = 4 9 M ∫ s 1 ( 1 + t ) 2 d t . \sum_{i=2k+1}^{M}b_i^2\le\frac{1}{M}\int_s^1x(t)^2\,dt=\frac{4}{9M}\int_s^1(1+t)^2\,dt. i = 2 k + 1 ∑ M b i 2 ≤ M 1 ∫ s 1 x ( t ) 2 d t = 9 M 4 ∫ s 1 ( 1 + t ) 2 d t .
Using k / M = s / 2 k/M=s/2 k / M = s /2 and m / M = 1 − s / 2 m/M=1-s/2 m / M = 1 − s /2 , we obtain
R ( m ) = m ( k ( 2 ( 2 + s ) 3 M ) 2 + ∑ i = 2 k + 1 M b i 2 ) ≤ 4 9 ( 1 − s 2 ) ( s 2 ( 2 + s ) 2 + ∫ s 1 ( 1 + t ) 2 d t ) = 4 9 ( 1 − s 2 ) ( 7 3 + s + s 2 + s 3 6 ) = : H ( s ) . (1) \begin{aligned}
R(m)&=m\left(k\left(\frac{2(2+s)}{3M}\right)^2+\sum_{i=2k+1}^{M}b_i^2\right)\\
&\le\frac{4}{9}\left(1-\frac{s}{2}\right)\left(\frac{s}{2}(2+s)^2+\int_s^1(1+t)^2\,dt\right)\\
&=\frac{4}{9}\left(1-\frac{s}{2}\right)\left(\frac{7}{3}+s+s^2+\frac{s^3}{6}\right)=:H(s). \tag*{(1)}
\end{aligned} R ( m ) = m ( k ( 3 M 2 ( 2 + s ) ) 2 + i = 2 k + 1 ∑ M b i 2 ) ≤ 9 4 ( 1 − 2 s ) ( 2 s ( 2 + s ) 2 + ∫ s 1 ( 1 + t ) 2 d t ) = 9 4 ( 1 − 2 s ) ( 3 7 + s + s 2 + 6 s 3 ) =: H ( s ) . (1)
It remains to bound H ( s ) H(s) H ( s ) independently of s s s . Expanding and regrouping gives
H ( s ) = 28 27 − s 27 ( 2 ( 1 − s ) ( 1 − 2 s ) 2 + s ( 3 s − 2 ) 2 ) ≤ 28 27 , H(s)=\frac{28}{27}-\frac{s}{27}\left(2(1-s)(1-2s)^2+s(3s-2)^2\right)\le\frac{28}{27}, H ( s ) = 27 28 − 27 s ( 2 ( 1 − s ) ( 1 − 2 s ) 2 + s ( 3 s − 2 ) 2 ) ≤ 27 28 ,
because every term in parentheses is nonnegative for s ∈ [ 0 , 1 ] s\in[0,1] s ∈ [ 0 , 1 ] . Together with the merging argument, this proves the bound for every m ∈ [ M ] m\in[M] m ∈ [ M ] .
For m = M m=M m = M , assigning each bag to a separate machine is optimal and gives R ( M ) = 28 / 27 − 1 / ( 27 M 2 ) R(M)=28/27-1/(27M^2) R ( M ) = 28/27 − 1/ ( 27 M 2 ) . This tends to 28 / 27 28/27 28/27 as M → ∞ M\to\infty M → ∞ , proving that the factor is tight uniformly over M M M for these bag volumes. □ \square □
Lower bound for sand
Theorem 2. For sand and speeds in { 0 , 1 } \{0,1\} { 0 , 1 } , no algorithm for minimizing the total completion time achieves a robustness factor smaller than $31/30\approx 1.0333.
Proof. We prove the lower bound by choosing a fixed distribution over the number of available machines and showing that every bag construction has an expected ratio of at least 31 / 30 31/30 31/30 . Consequently, at least one machine count gives the claimed lower bound.
Fix M = 12 M = 12 M = 12 and any bag volumes b 1 ≥ ⋯ ≥ b 12 ≥ 0 b_1 \ge\cdots\ge b_{12} \ge0 b 1 ≥ ⋯ ≥ b 12 ≥ 0 with ∑ i = 1 12 b i = 1 \sum_{i=1}^{12} b_i = 1 ∑ i = 1 12 b i = 1 . Let R ( m ) R(m) R ( m ) denote the smallest ratio achievable by assigning these bags to m m m machines. We choose the number of available machines according to the distribution
Pr [ m = 8 ] = 15 45 , Pr [ m = 9 ] = 4 45 , Pr [ m = 10 ] = 6 45 , Pr [ m = 12 ] = 20 45 . \Pr[m = 8] = \frac{15}{45}, \quad\Pr[m = 9] = \frac{4}{45}, \quad\Pr[m = 10] = \frac{6}{45}, \quad\Pr[m = 12] = \frac{20}{45}. Pr [ m = 8 ] = 45 15 , Pr [ m = 9 ] = 45 4 , Pr [ m = 10 ] = 45 6 , Pr [ m = 12 ] = 45 20 .
This distribution is independent of the bag volumes.
We first establish two properties of an optimal assignment. For m ∈ { 8 , 9 , 10 } m \in\{8, 9, 10\} m ∈ { 8 , 9 , 10 } , we may assume that every machine receives at least one bag, possibly of volume zero. Indeed, moving a bag from a machine containing at least two bags to an empty machine cannot increase the sum of squared loads. At least v : = 2 m − 12 v := 2m - 12 v := 2 m − 12 machines then receive exactly one bag.
Moreover, we may assume that the v v v largest bags are assigned alone. Suppose that a singleton bag has volume b b b , while a bag of volume a ≥ b a \ge b a ≥ b shares its machine with other bags of total volume c c c . Exchanging the two bags changes the sum of squared loads by
a 2 + ( b + c ) 2 − b 2 − ( a + c ) 2 = 2 c ( b − a ) ≤ 0. a^2 + (b+c)^2 - b^2 - (a+c)^2 = 2c(b-a) \le0. a 2 + ( b + c ) 2 − b 2 − ( a + c ) 2 = 2 c ( b − a ) ≤ 0.
After setting aside the v v v largest bags and their machines, the remaining bags occupy m − v = 12 − m m-v = 12-m m − v = 12 − m machines. Applying Cauchy–Schwarz to these machines gives
R ( m ) ≥ m ( ∑ i = 1 v b i 2 + 1 12 − m ( ∑ i = v + 1 12 b i ) 2 ) . R(m) \ge m\left(\sum_{i=1}^{v} b_i^2 + \frac{1}{12-m}\left(\sum_{i=v+1}^{12} b_i\right)^2\right). R ( m ) ≥ m i = 1 ∑ v b i 2 + 12 − m 1 ( i = v + 1 ∑ 12 b i ) 2 .
For m = 8 , 9 , 10 m = 8, 9, 10 m = 8 , 9 , 10 , the values of v v v are 4 , 6 , 8 4, 6, 8 4 , 6 , 8 . We therefore partition the bags into the corresponding consecutive groups and write
X 1 : = ∑ i = 1 4 b i , X 2 : = b 5 + b 6 , X 3 : = b 7 + b 8 , X 4 : = ∑ i = 9 12 b i . X_1 := \sum_{i=1}^{4} b_i, \qquad X_2 := b_5+b_6, \qquad X_3 := b_7+b_8, \qquad X_4 := \sum_{i=9}^{12} b_i. X 1 := i = 1 ∑ 4 b i , X 2 := b 5 + b 6 , X 3 := b 7 + b 8 , X 4 := i = 9 ∑ 12 b i .
Their volumes sum to one. For m = 12 m = 12 m = 12 , assigning every bag to a separate machine is optimal. Applying Cauchy–Schwarz within the groups yields
R ( 8 ) ≥ 2 ( X 1 2 + ( X 2 + X 3 + X 4 ) 2 ) , R(8) \ge2\left(X_1^2 + (X_2+X_3+X_4)^2\right), R ( 8 ) ≥ 2 ( X 1 2 + ( X 2 + X 3 + X 4 ) 2 ) ,
R ( 9 ) ≥ 9 4 X 1 2 + 9 2 X 2 2 + 3 ( X 3 + X 4 ) 2 , R(9) \ge\frac{9}{4}X_1^2 + \frac{9}{2}X_2^2 + 3(X_3+X_4)^2, R ( 9 ) ≥ 4 9 X 1 2 + 2 9 X 2 2 + 3 ( X 3 + X 4 ) 2 ,
R(10) \ge\frac{5}{2}X_1^2 + 5(X__2^2 + X_3^2 + X_4^2),
R ( 12 ) ≥ 3 X 1 2 + 6 X 2 2 + 6 X 3 2 + 3 X 4 2 . R(12) \ge3X_1^2 + 6X_2^2 + 6X_3^2 + 3X_4^2. R ( 12 ) ≥ 3 X 1 2 + 6 X 2 2 + 6 X 3 2 + 3 X 4 2 .
These bounds capture the different effects of the machine counts. With fewer machines, more bags must share machines, and their combined volume contributes quadratically. With more machines, the individual bag volumes determine more of the cost. Averaging the four bounds according to the chosen distribution gives
E [ R ( m ) ] ≥ 38 15 X 1 2 + 2 3 ( 1 − X 1 ) 2 \mathbb{E}[R(m)] \ge\frac{38}{15}X_1^2 + \frac{2}{3}(1-X_1)^2 E [ R ( m )] ≥ 15 38 X 1 2 + 3 2 ( 1 − X 1 ) 2
+ 56 15 X 2 2 + 18 5 X 3 2 + 34 15 X 4 2 + 8 15 X 3 X 4 . {}+ \frac{56}{15}X_2^2 + \frac{18}{5}X_3^2 + \frac{34}{15}X_4^2 + \frac{8}{15}X_3X_4. + 15 56 X 2 2 + 5 18 X 3 2 + 15 34 X 4 2 + 15 8 X 3 X 4 .
We first combine X 3 X_3 X 3 and X 4 X_4 X 4 into their total volume, and then combine this volume with X 2 X_2 X 2 . This leaves a quadratic expression in X 1 X_1 X 1 and 1 − X 1 1-X_1 1 − X 1 , which we can bound independently of the bag volumes. For this, we use the weighted form of Cauchy–Schwarz: for α , β > 0 \alpha,\beta> 0 α , β > 0 ,
α u 2 + β v 2 ≥ ( u + v ) 2 1 / α + 1 / β . \alpha u^2+\beta v^2 \ge\frac{(u+v)^2}{1/\alpha+1/\beta}. α u 2 + β v 2 ≥ 1/ α + 1/ β ( u + v ) 2 .
Let Z : = X 3 + X 4 Z := X_3+X_4 Z := X 3 + X 4 . Completing a square gives
18 5 X 3 2 + 34 15 X 4 2 + 8 15 X 3 X 4 = 1 12 ( 5 X 3 − 3 X 4 ) 2 + 91 60 Z 2 ≥ 91 60 Z 2 . \frac{18}{5}X_3^2+\frac{34}{15}X_4^2+\frac{8}{15}X_3X_4
=\frac{1}{12}(5X_3-3X_4)^2+\frac{91}{60}Z^2
\ge\frac{91}{60}Z^2. 5 18 X 3 2 + 15 34 X 4 2 + 15 8 X 3 X 4 = 12 1 ( 5 X 3 − 3 X 4 ) 2 + 60 91 Z 2 ≥ 60 91 Z 2 .
Since X 2 + Z = 1 − X 1 X_2+Z=1-X_1 X 2 + Z = 1 − X 1 , the weighted inequality implies
56 15 X 2 2 + 91 60 Z 2 ≥ ( X 2 + Z ) 2 15 56 + 60 91 = 728 675 ( 1 − X 1 ) 2 . \frac{56}{15}X_2^2+\frac{91}{60}Z^2
\ge\frac{(X_2+Z)^2}{\frac{15}{56}+\frac{60}{91}}
=\frac{728}{675}(1-X_1)^2. 15 56 X 2 2 + 60 91 Z 2 ≥ 56 15 + 91 60 ( X 2 + Z ) 2 = 675 728 ( 1 − X 1 ) 2 .
Consequently,
E [ R ( m ) ] ≥ 38 15 X 1 2 + ( 2 3 + 728 675 ) ( 1 − X 1 ) 2 = 38 15 ( X 1 2 + 31 45 ( 1 − X 1 ) 2 ) ≥ 38 15 ( X 1 + ( 1 − X 1 ) ) 2 1 + 45 / 31 = 38 15 ⋅ 31 76 = 31 30 . \mathbb{E}[R(m)]\ge\frac{38}{15}X_1^2+\left(\frac{2}{3}+\frac{728}{675}\right)(1-X_1)^2
=\frac{38}{15}\left(X_1^2+\frac{31}{45}(1-X_1)^2\right)
\ge\frac{38}{15}\frac{(X_1+(1-X_1))^2}{1+45/31}
=\frac{38}{15}\cdot\frac{31}{76}
=\frac{31}{30}. E [ R ( m )] ≥ 15 38 X 1 2 + ( 3 2 + 675 728 ) ( 1 − X 1 ) 2 = 15 38 ( X 1 2 + 45 31 ( 1 − X 1 ) 2 ) ≥ 15 38 1 + 45/31 ( X 1 + ( 1 − X 1 ) ) 2 = 15 38 ⋅ 76 31 = 30 31 .
Thus, for every bag construction, the expected ratio under the chosen distribution is at least 31 / 30 31/30 31/30 . At least one of the four machine counts therefore forces this ratio, even with an optimal Phase II assignment. □
3:2-Cyclic algorithm for bricks and rocks
Theorem 3. For speeds in { 0 , 1 } \{0,1\} { 0 , 1 } , the 3:2-Cyclic algorithm is 13/12-robust for minimizing the total completion time of bricks and rocks.
Algorithm 1 gives a formal description of the algorithm from § 3 , and Figure 1 illustrates both phases. In Phase II, we first assign bags in complete forward cyclic rounds until all long bags have been assigned. We then reverse the cyclic order for the remaining bags. The assignment applies to all bag labels, including those of empty bags, and depends only on M M M and m m m .
Figure 1. Illustration of both phases for n = 21 n = 21 n = 21 bricks and M = 7 M = 7 M = 7 bags. Left: Phase I with L = 3 L = 3 L = 3 , x = 17 x = 17 x = 17 , and an incomplete second package (orange), resulting in unequal short bags. Right: Phase II for three machine numbers, with long bags (pink) and short bags (green).
We first prove the guarantee for bricks and then extend it to rocks using Lemma 1. Let M ≥ 3 M\ge3 M ≥ 3 , L : = ⌊ M / 2 ⌋ L:=\lfloor M/2\rfloor L := ⌊ M /2 ⌋ , and b i : = ∣ B i ∣ b_i:=|B_i| b i := ∣ B i ∣ for i ∈ [ M ] i\in[M] i ∈ [ M ] . We refer to B 1 , … , B L B_1,\ldots,B_L B 1 , … , B L as long bags and to the remaining bags as short bags. Recall that F ( k ) = k ( k + 1 ) / 2 F(k)=k(k+1)/2 F ( k ) = k ( k + 1 ) /2 gives the total completion time of k k k bricks on one machine.
Algorithm 1 3:2-Cyclic
Require: Phase I: n n n jobs, M M M bags
Require: Phase II: Number of machines m m m
Sort the jobs in non-increasing order of processing times.
Case M ≤ 2 M \le2 M ≤ 2 :
Phase I: Assign the jobs cyclically to the bags.
Phase II: Assign one bag to each machine if m = 2 m = 2 m = 2 , and all bags to the single machine otherwise. Schedule the jobs in SPT order.
Case M ≥ 3 M \ge3 M ≥ 3 :
Set L : = ⌊ M / 2 ⌋ L := \lfloor M/2\rfloor L := ⌊ M /2 ⌋ and x : = 2 M + L x := 2M + L x := 2 M + L .
Phase I:
Partition the given job sequence into consecutive packages of x x x jobs, with possibly fewer jobs in the last package.
For each package, assign its jobs cyclically to B 1 , … , B M B_1,\ldots,B_M B 1 , … , B M , starting with B 1 B_1 B 1 .
Phase II:
Assign B 1 , … , B L B_1,\ldots,B_L B 1 , … , B L cyclically to machines 1 , … , m 1,\ldots,m 1 , … , m , starting with machine 1.
Set h : = m ⌈ L / m ⌉ − L h := m\lceil L/m\rceil- L h := m ⌈ L / m ⌉ − L .
if h > 0 h > 0 h > 0 then
Assign B L + 1 , … , B L + h B_{L+1},\ldots,B_{L+h} B L + 1 , … , B L + h to machines m − h + 1 , … , m m-h+1,\ldots,m m − h + 1 , … , m , respectively.
end if
Assign the remaining bags in increasing index order, cyclically to machines m , m − 1 , … , 1 m,m-1,\ldots,1 m , m − 1 , … , 1 .
Schedule the jobs in SPT order on each machine.
By construction, the bag loads satisfy
b 1 ≥ ⋯ ≥ b M , b_1 \ge\cdots\ge b_M, b 1 ≥ ⋯ ≥ b M ,
b L + 1 − b M ≤ 1 , b_{L+1} - b_M \le1, b L + 1 − b M ≤ 1 ,
∣ b i − 3 2 b j ∣ ≤ 1 for all i ≤ L < j . (2) \left|b_i-\frac{3}{2}b_j\right| \le1 \qquad\text{for all } i \le L < j. \tag*{(2)} b i − 2 3 b j ≤ 1 for all i ≤ L < j . (2)
The first two inequalities follow from the cyclic assignment within each package. For the third inequality, each complete package adds three jobs to every long bag and two jobs to every short bag. Thus, these packages do not change b i − 3 2 b j b_i-\frac{3}{2}b_j b i − 2 3 b j . The contributions of the last, possibly incomplete package to a long bag and a short bag form one of the pairs
( 0 , 0 ) , ( 1 , 0 ) , ( 1 , 1 ) , ( 2 , 1 ) , ( 2 , 2 ) , ( 3 , 2 ) , (0,0),\ (1,0),\ (1,1),\ (2,1),\ (2,2),\ (3,2), ( 0 , 0 ) , ( 1 , 0 ) , ( 1 , 1 ) , ( 2 , 1 ) , ( 2 , 2 ) , ( 3 , 2 ) ,
where the first entry refers to the long bag. Each pair satisfies the claimed inequality.
We next bound the difference between machine loads. The forward rounds give non-increasing machine loads, whereas the reverse rounds add non-decreasing loads. We use these opposite orders to bound the final difference between machine loads.
Lemma 7. Let s : = b L + 1 s := b_{L+1} s := b L + 1 . The machine loads produced by the algorithm differ by at most max { 1 , s } \max\{1,s\} max { 1 , s } .
Proof. Write a : = b M a := b_M a := b M . By (2) , we have
b 1 − b M ≤ a 2 + 1. b_1-b_M \le\frac{a}{2}+1. b 1 − b M ≤ 2 a + 1.
Since the bag loads are integers, this implies
b 1 − b M ≤ max { 1 , a } ≤ max { 1 , s } . b_1-b_M \le\max\{1,a\} \le\max\{1,s\}. b 1 − b M ≤ max { 1 , a } ≤ max { 1 , s } .
Recall that K = m ⌈ L / m ⌉ K = m\lceil L/m\rceil K = m ⌈ L / m ⌉ is the number of bags assigned before the algorithm reverses the cyclic order. Then L ≤ K ≤ M L \le K \le M L ≤ K ≤ M . Indeed, if m ≤ L m \le L m ≤ L , then K < L + m ≤ 2 L ≤ M K < L+m \le2L \le M K < L + m ≤ 2 L ≤ M . Otherwise, K = m ≤ M K=m\le M K = m ≤ M .
Let y i 0 y_i^0 y i 0 denote the load assigned to machine i i i in the forward rounds. Since the bags are ordered by non-increasing load, we have y 1 0 ≥ ⋯ ≥ y m 0 y_1^0 \ge\cdots\ge y_m^0 y 1 0 ≥ ⋯ ≥ y m 0 and
y 1 0 − y m 0 = ∑ r = 0 K / m − 1 ( b r m + 1 − b ( r + 1 ) m ) ≤ b 1 − b K . y_1^0-y_m^0=\sum_{r=0}^{K/m-1}\left(b_{rm+1}-b_{(r+1)m}\right)\le b_1-b_K. y 1 0 − y m 0 = r = 0 ∑ K / m − 1 ( b r m + 1 − b ( r + 1 ) m ) ≤ b 1 − b K .
The inequality follows by adding the nonnegative gaps between consecutive rounds.
Let d i d_i d i denote the additional load assigned to machine i i i in the reverse rounds. These loads satisfy d 1 ≤ ⋯ ≤ d m d_1\le\cdots\le d_m d 1 ≤ ⋯ ≤ d m . Setting b j : = 0 b_j:=0 b j := 0 for j > M j>M j > M , the same argument gives
d m − d 1 = ∑ r ≥ 0 ( b K + r m + 1 − b K + ( r + 1 ) m ) ≤ b K + 1 . d_m-d_1=\sum_{r\ge0}\left(b_{K+rm+1}-b_{K+(r+1)m}\right)\le b_{K+1}. d m − d 1 = r ≥ 0 ∑ ( b K + r m + 1 − b K + ( r + 1 ) m ) ≤ b K + 1 .
For K = M K=M K = M , both sides are zero.
The final load of machine i i i is y i = y i 0 + d i y_i=y_i^0+d_i y i = y i 0 + d i . Consequently, for i < j i<j i < j ,
− b K + 1 ≤ y i − y j ≤ b 1 − b K . -b_{K+1}\le y_i-y_j\le b_1-b_K. − b K + 1 ≤ y i − y j ≤ b 1 − b K .
The claim follows from K ≥ L K\ge L K ≥ L , b K + 1 ≤ s b_{K+1}\le s b K + 1 ≤ s , and b 1 − b K ≤ b 1 − b M ≤ max { 1 , s } b_1-b_K\le b_1-b_M\le\max\{1,s\} b 1 − b K ≤ b 1 − b M ≤ max { 1 , s } .
For bricks on identical machines, an unrestricted optimal schedule has machine loads differing by at most one. Indeed, moving one job from a machine with at least two more jobs than another machine strictly decreases the total completion time. The following lemma bounds the cost when the loads differ by two.
Lemma 8. A schedule of bricks with machine loads in { β , β + 1 , β + 2 } \{\beta,\beta+1,\beta+2\} { β , β + 1 , β + 2 } , where β ≥ 2 \beta\ge2 β ≥ 2 , has cost at most 13 / 12 13/12 13/12 times the unrestricted optimum.
Proof. As long as there is a machine with load β \beta β and a machine with load β + 2 \beta+2 β + 2 , move one job from the latter to the former. Each such move decreases the total completion time by one. When no further move is possible, the loads differ by at most one, so the resulting schedule is optimal.
Let k k k be the number of moves. Then the original cost exceeds the optimum by k k k . Moreover, the resulting schedule has at least 2 k 2k 2 k machines of load β + 1 ≥ 3 \beta+1\ge3 β + 1 ≥ 3 , each contributing at least F ( 3 ) = 6 F(3)=6 F ( 3 ) = 6 . Thus, Opt m ≥ 12 k \operatorname{Opt}_m\ge12k Opt m ≥ 12 k , and the original cost is at most
Opt m + k ≤ 13 12 Opt m . \operatorname{Opt}_m+k\le\frac{13}{12}\operatorname{Opt}_m. Opt m + k ≤ 12 13 Opt m .
We now prove the robustness guarantee. If no short bag is assigned alone, every machine receives a long bag or at least two short bags. This gives a lower bound on its load compared with the possible difference between machine loads. If a short bag is assigned alone, all long bags are assigned alone as well. Their loads are close to the midpoint between the loads of one short bag and two short bags. We use these properties to bound the variance in the two cases.
Proof (Proof of Theorem 3). We first consider bricks. For M ≤ 2 M \le2 M ≤ 2 , the algorithm produces machine loads differing by at most one and is therefore optimal. Hence, assume M ≥ 3 M \ge3 M ≥ 3 and let s : = b L + 1 s := b_{L+1} s := b L + 1 .
If s ≤ 1 s \le1 s ≤ 1 , the machine loads differ by at most one by Lemma 7, so the algorithm is optimal. Suppose that s = 2 s = 2 s = 2 . By (2) , every short bag contains at least one job and every long bag contains at least two jobs. If every machine has load at least two, the claim follows from Lemmas 7 and 8.
Otherwise, some machine has load one and therefore receives a short bag alone. This requires m > L m > L m > L , since for m ≤ L m \le L m ≤ L every machine receives a long bag. For m > L m > L m > L , the first z : = 2 m − M z := 2m - M z := 2 m − M bags are assigned alone, and all remaining bags are assigned in pairs. Since one of the first z z z bags has load one and all bags are nonempty, we have b z = 1 b_z = 1 b z = 1 . Thus, all bags assigned in pairs have load one. Moreover, (2) , applied to a short bag of load one, implies that every long bag has load at most two. All machine loads therefore belong to { 1 , 2 } \{1, 2\} { 1 , 2 } , and the algorithm is optimal.
Henceforth, assume s ≥ 3 s \ge3 s ≥ 3 . Let y i y_i y i denote the load of machine i i i , and write
y ˉ : = n m , V : = 1 m ∑ i = 1 m ( y i − y ˉ ) 2 . \bar{y} := \frac{n}{m}, \qquad V := \frac{1}{m}\sum_{i=1}^{m}(y_i-\bar{y})^2. y ˉ := m n , V := m 1 i = 1 ∑ m ( y i − y ˉ ) 2 .
Since F ( k ) = k ( k + 1 ) / 2 F(k)=k(k+1)/2 F ( k ) = k ( k + 1 ) /2 , we have
Alg ( m , M ) = m 2 ( V + y ˉ 2 + y ˉ ) . \operatorname{Alg}(m,M)=\frac{m}{2}\left(V+\bar{y}^2+\bar{y}\right). Alg ( m , M ) = 2 m ( V + y ˉ 2 + y ˉ ) .
By convexity,
Opt m ≥ m 2 ( y ˉ 2 + y ˉ ) . \operatorname{Opt}_m \ge\frac{m}{2}\left(\bar{y}^2+\bar{y}\right). Opt m ≥ 2 m ( y ˉ 2 + y ˉ ) .
Consequently,
Alg ( m , M ) Opt m ≤ 1 + V y ˉ 2 + y ˉ . (3) \frac{\operatorname{Alg}(m,M)}{\operatorname{Opt}_m}\le1+\frac{V}{\bar{y}^2+\bar{y}}. \tag*{(3)} Opt m Alg ( m , M ) ≤ 1 + y ˉ 2 + y ˉ V . (3)
For the remaining cases, we either apply Lemma 8 or show that 12 V ≤ y ˉ 2 + y ˉ 12V \le\bar{y}^2+\bar{y} 12 V ≤ y ˉ 2 + y ˉ .
In each case, we will locate the machine loads in an interval and choose its midpoint c c c . We bound their squared distances from c c c and then account for the difference between c c c and the average load. Let
D c : = 1 m ∑ i = 1 m ( y i − c ) 2 , τ : = y ˉ − c . D_c:=\frac{1}{m}\sum_{i=1}^{m}(y_i-c)^2,\qquad\tau:=\bar{y}-c. D c := m 1 i = 1 ∑ m ( y i − c ) 2 , τ := y ˉ − c .
Then V = D c − τ 2 V=D_c-\tau^2 V = D c − τ 2 . Completing squares gives a lower bound on y ˉ 2 + y ˉ − 12 V \bar{y}^2+\bar{y}-12V y ˉ 2 + y ˉ − 12 V that depends only on c c c and D c D_c D c :
y ˉ 2 + y ˉ − 12 V = 12 ( τ + c 12 ) 2 + ( τ + 1 2 ) 2 + 11 12 c 2 + c − 12 D c − 1 4 \bar{y}^2+\bar{y}-12V
=12\left(\tau+\frac{c}{12}\right)^2+\left(\tau+\frac{1}{2}\right)^2+\frac{11}{12}c^2+c-12D_c-\frac{1}{4} y ˉ 2 + y ˉ − 12 V = 12 ( τ + 12 c ) 2 + ( τ + 2 1 ) 2 + 12 11 c 2 + c − 12 D c − 4 1
{#eq:4}
\ge \frac{11}{12}c^2+c-12D_c-\frac{1}{4}.
We distinguish whether a short bag is assigned alone.
Case 1: No short bag is assigned alone. Every machine receives a long bag or at least two short bags. By (2) , every long bag has load at least 3 s / 2 − 1 3s/2-1 3 s /2 − 1 , and every short bag has load at least s − 1 s-1 s − 1 . Thus, the minimum machine load β \beta β satisfies
β ≥ min { 3 2 s − 1 , 2 ( s − 1 ) } = 3 2 s − 1 , \beta\ge\min\left\{\frac{3}{2}s-1,2(s-1)\right\}=\frac{3}{2}s-1, β ≥ min { 2 3 s − 1 , 2 ( s − 1 ) } = 2 3 s − 1 ,
where the equality uses $s\ge 3. By Lemma 7, all machine loads belong to [ β , β + s ] [\beta,\beta+s] [ β , β + s ] . Choose
c : = β + s 2 ≥ 2 s − 1. c := \beta+ \frac{s}{2} \ge2s-1. c := β + 2 s ≥ 2 s − 1.
Then every machine load differs from c c c by at most s / 2 s/2 s /2 , so D c ≤ s 2 / 4 D_c \le s^2/4 D c ≤ s 2 /4 . Applying (4), we obtain
y ˉ 2 + y ˉ − 12 V ≥ 11 12 ( 2 s − 1 ) 2 + ( 2 s − 1 ) − 3 s 2 − 1 4 = 2 s 2 − 5 s − 1 3 > 0 , \bar{y}^{2}+\bar{y}-12V \ge\frac{11}{12}(2s-1)^2+(2s-1)-3s^2-\frac{1}{4}
= \frac{2s^2-5s-1}{3}>0, y ˉ 2 + y ˉ − 12 V ≥ 12 11 ( 2 s − 1 ) 2 + ( 2 s − 1 ) − 3 s 2 − 4 1 = 3 2 s 2 − 5 s − 1 > 0 ,
where the last inequality holds for s ≥ 3 s \ge3 s ≥ 3 . The claim follows from (3) .
Case 2: A short bag is assigned alone. Then m > L m>L m > L and z : = 2 m − M > L z:=2m-M>L z := 2 m − M > L . The first z z z bags are assigned alone, and the remaining bags are assigned in pairs. In particular, all L L L long bags are assigned alone.
Let a : = b z a:=b_z a := b z . Since B z B_z B z is a short bag, we have a ≥ s − 1 ≥ 2 a\ge s-1\ge2 a ≥ s − 1 ≥ 2 . The short bags assigned alone have loads in [ a , a + 1 ] [a,a+1] [ a , a + 1 ] . All bags assigned in pairs are short and have loads in [ a − 1 , a ] [a-1,a] [ a − 1 , a ] . Hence, every machine receiving two bags has load in
[ 2 a − 2 , 2 a ] ⊆ [ a , 2 a ] . [2a-2,2a]\subseteq[a,2a]. [ 2 a − 2 , 2 a ] ⊆ [ a , 2 a ] .
By (2) , the loads of the long bags belong to
[ 3 2 a − 1 , 3 2 a + 1 ] ⊆ [ a , 2 a ] . \left[\frac{3}{2}a-1,\frac{3}{2}a+1\right]\subseteq[a,2a]. [ 2 3 a − 1 , 2 3 a + 1 ] ⊆ [ a , 2 a ] .
If a = 2 a=2 a = 2 , all machine loads belong to { 2 , 3 , 4 } \{2,3,4\} { 2 , 3 , 4 } , and Lemma 8 proves the claim. Thus, assume a ≥ 3 a\ge3 a ≥ 3 and choose c : = 3 a / 2 c:=3a/2 c := 3 a /2 . The loads of the L L L machines receiving long bags differ from c c c by at most one. Every other machine has load in [ a , 2 a ] [a,2a] [ a , 2 a ] and therefore differs from c c c by at most a / 2 a/2 a /2 . Since
L m ≥ L M ≥ 1 3 and a 2 4 ≥ 1 , \frac{L}{m}\ge\frac{L}{M}\ge\frac{1}{3}
\qquad\text{and}\qquad
\frac{a^2}{4}\ge1, m L ≥ M L ≥ 3 1 and 4 a 2 ≥ 1 ,
we obtain
D c ≤ L m + ( 1 − L m ) a 2 4 ≤ 1 3 + a 2 6 . D_c\le\frac{L}{m}+\left(1-\frac{L}{m}\right)\frac{a^2}{4}\le\frac{1}{3}+\frac{a^2}{6}. D c ≤ m L + ( 1 − m L ) 4 a 2 ≤ 3 1 + 6 a 2 .
Applying (4) now gives
y ˉ 2 + y ˉ − 12 V ≥ 11 12 ( 3 2 a ) 2 + 3 2 a − 12 ( 1 3 + a 2 6 ) − 1 4 = a 2 16 + 3 2 a − 17 4 > 0 , \bar{y}^{2}+\bar{y}-12V\ge\frac{11}{12}\left(\frac{3}{2}a\right)^2+\frac{3}{2}a-12\left(\frac{1}{3}+\frac{a^2}{6}\right)-\frac{1}{4}
=\frac{a^2}{16}+\frac{3}{2}a-\frac{17}{4}>0, y ˉ 2 + y ˉ − 12 V ≥ 12 11 ( 2 3 a ) 2 + 2 3 a − 12 ( 3 1 + 6 a 2 ) − 4 1 = 16 a 2 + 2 3 a − 4 17 > 0 ,
where the last inequality holds for a ≥ 3 a\ge3 a ≥ 3 . Again, (3) proves the claim.
Finally, consider rocks with p 1 ≥ ⋯ ≥ p n p_1\ge\cdots\ge p_n p 1 ≥ ⋯ ≥ p n . In Phase I, the assignment of jobs to bag labels depends only on their indices and M M M . In Phase II, the assignment of all bag labels, including empty bags, depends only on M M M and m m m . Thus, for every r ∈ [ n ] r\in[n] r ∈ [ n ] , restricting the assignment to the first r r r jobs and setting their processing times to one gives the algorithm’s assignment for r r r bricks. The guarantee therefore holds for every prefix under the same assignment. Applying Lemma 1 completes the proof.
Lower bound for rocks
Theorem 4. For speeds in { 0 , 1 } \{0,1\} { 0 , 1 } , no deterministic algorithm for minimizing the total completion time of bricks achieves a robustness factor smaller than 13 / 12 13/12 13/12 . For rocks, the same lower bound holds for every n ≥ 6 n \ge6 n ≥ 6 .
Proof. The case n = 6 n = 6 n = 6 follows from the lower bound for bricks. For n ≥ 7 n \ge7 n ≥ 7 , fix M : = 3 M := 3 M := 3 , let k : = n − 6 k := n - 6 k := n − 6 , and add k k k jobs of size ε ∈ ( 0 , 1 ) \varepsilon\in(0,1) ε ∈ ( 0 , 1 ) to the six unit jobs.
Consider any partition of this instance into three bags. Restricting the bags to the unit jobs gives the same case distinction as in § 3 . If each bag contains two unit jobs, the adversary chooses m = 2 m = 2 m = 2 , and the unit jobs contribute at least 13. Otherwise, the adversary chooses m = 3 m = 3 m = 3 , and their contribution is at least 10. The additional jobs cannot decrease these contributions.
To bound the unrestricted optimum, start with an optimal schedule of the six unit jobs. Its cost is 12 for m = 2 m = 2 m = 2 and 9 for m = 3 m = 3 m = 3 . Place all additional jobs first on one machine. Their own completion times and the delay of at most three unit jobs increase the cost by at most
δ : = k ( k + 1 ) 2 ε + 3 k ε = k ( k + 7 ) 2 ε . \delta:= \frac{k(k+1)}{2}\varepsilon+ 3k\varepsilon= \frac{k(k+7)}{2}\varepsilon. δ := 2 k ( k + 1 ) ε + 3 k ε = 2 k ( k + 7 ) ε .
Consequently,
A L G O P T ≥ min { 13 12 + δ , 10 9 + δ } . \frac{\mathrm{ALG}}{\mathrm{OPT}} \ge\min\left\{\frac{13}{12+\delta},\frac{10}{9+\delta}\right\}. OPT ALG ≥ min { 12 + δ 13 , 9 + δ 10 } .
For every fixed n ≥ 7 n \ge7 n ≥ 7 , we have δ → 0 \delta\to0 δ → 0 as ε → 0 \varepsilon\to0 ε → 0 , and the right-hand side tends to 13 / 12 13/12 13/12 . Since this bound holds for every bag partition, no algorithm can guarantee a robustness factor smaller than 13 / 12 13/12 13/12 . □ \quad\Box □
Proofs for general speeds
Lower bound for sand
Theorem 5. For general speeds, no deterministic algorithm for minimizing the total completion time of sand achieves a robustness factor smaller than γ = ( 1 − 1 2 e − 3 / 2 ) − 2 > 1.2669 \gamma= \left(1 - \frac{1}{2}e^{-3/2}\right)^{-2} > 1.2669 γ = ( 1 − 2 1 e − 3/2 ) − 2 > 1.2669 , uniformly over the number of machines.
Proof. Fix M ≥ 2 M \ge2 M ≥ 2 and arbitrary bag volumes 0 ≤ b 1 ≤ ⋯ ≤ b M 0 \le b_1 \le\cdots\le b_M 0 ≤ b 1 ≤ ⋯ ≤ b M summing to one. Let W ( b ) W(b) W ( b ) denote the supremum, over all normalized speed vectors, of the ratio achieved by an optimal Phase II assignment of these bags. Recall that an assignment with machine loads y i y_i y i has ratio
R ( s ) = ∑ i = 1 m y i 2 s i , R(s) = \sum_{i=1}^{m}\frac{y_i^2}{s_i}, R ( s ) = i = 1 ∑ m s i y i 2 ,
since both the total volume and the total speed are one.
Set α = ( M − 1 ) / M \alpha= (M - 1)/M α = ( M − 1 ) / M . We first describe the minimum relaxed quadratic cost of selecting a prescribed total volume to be assigned to slow machines. Define q : [ 0 , 1 ] → R ≥ 0 q : [0,1] \to\mathbb{R}_{\ge0} q : [ 0 , 1 ] → R ≥ 0 by linearly interpolating points
( ∑ r = 1 k b r , ( M − 1 ) ∑ r = 1 k b r 2 ) , k = 0 , … , M . \left(\sum_{r=1}^{k} b_r, (M-1)\sum_{r=1}^{k} b_r^2\right), \qquad k = 0,\ldots,M. ( r = 1 ∑ k b r , ( M − 1 ) r = 1 ∑ k b r 2 ) , k = 0 , … , M .
For a prescribed volume of u u u , consider the relaxation
min { ( M − 1 ) ∑ r = 1 M z r b r 2 : ∑ r = 1 M z r b r = u , 0 ≤ z r ≤ 1 } . \min\left\{(M-1)\sum_{r=1}^{M}z_r b_r^2 : \sum_{r=1}^{M}z_r b_r = u,\quad0 \le z_r \le1\right\}. min { ( M − 1 ) r = 1 ∑ M z r b r 2 : r = 1 ∑ M z r b r = u , 0 ≤ z r ≤ 1 } .
The minimum is obtained by selecting the smallest bags first, with at most one bag selected fractionally. Hence, its value is exactly q ( u ) q(u) q ( u ) .
The segment corresponding to a positive bag volume b r b_r b r has length b r b_r b r and slope ( M − 1 ) b r (M-1)b_r ( M − 1 ) b r . Thus, q q q is convex, q ( 0 ) = 0 q(0)=0 q ( 0 ) = 0 , and
∫ 0 1 d u q ′ ( u ) = ∣ { r : b r > 0 } ∣ M − 1 ≤ 1 α . (4) \int_{0}^{1} \frac{du}{q'(u)} = \frac{|\{r:b_r>0\}|}{M-1} \le\frac{1}{\alpha}. \tag*{(4)} ∫ 0 1 q ′ ( u ) d u = M − 1 ∣ { r : b r > 0 } ∣ ≤ α 1 . (4)
Here and below, derivatives of piecewise differentiable functions are understood almost everywhere and bags with a volume of zero only contribute duplicate interpolation points.
We now relate this profile to a speed vector that forces a large ratio. More precisely, we show that
W ( b ) ≥ h 2 , h : = max 0 ≤ u ≤ 1 { q ( u ) + 1 − u } . (5) W(b) \ge h^2, \qquad h := \max_{0\le u\le1}\left\{\sqrt{q(u)}+1-u\right\}. \tag*{(5)} W ( b ) ≥ h 2 , h := 0 ≤ u ≤ 1 max { q ( u ) + 1 − u } . (5)
For 0 < σ ≤ α 0<\sigma\le\alpha 0 < σ ≤ α , give M − 1 M-1 M − 1 machines speed σ / ( M − 1 ) \sigma/(M-1) σ / ( M − 1 ) and the remaining machine a speed of 1 − σ 1-\sigma 1 − σ . Consider any assignment, and let T ⊆ [ M ] T\subseteq[M] T ⊆ [ M ] be the indices of the bags assigned to the slow machines. Dropping the cross terms between bags assigned to the same slow machine gives the lower bound
R ( s ) ≥ M − 1 σ ∑ r ∈ T b r 2 + ( 1 − ∑ r ∈ T b r ) 2 1 − σ . R(s) \ge\frac{M-1}{\sigma}\sum_{r\in T} b_r^2+\frac{\left(1-\sum_{r\in T}b_r\right)^2}{1-\sigma}. R ( s ) ≥ σ M − 1 r ∈ T ∑ b r 2 + 1 − σ ( 1 − ∑ r ∈ T b r ) 2 .
By relaxing the choice of T T T as above, we obtain
W ( b ) ≥ min 0 ≤ u ≤ 1 { q ( u ) σ + ( 1 − u ) 2 1 − σ } . (6) W(b) \ge\min_{0\le u\le1}\left\{\frac{q(u)}{\sigma}+\frac{(1-u)^2}{1-\sigma}\right\}. \tag*{(6)} W ( b ) ≥ 0 ≤ u ≤ 1 min { σ q ( u ) + 1 − σ ( 1 − u ) 2 } . (6)
For uniform speeds, assigning one bag to each machine is optimal, since combining bags only adds nonnegative cross terms. The resulting ratio is
U = M ∑ r = 1 M b r 2 = q ( 1 ) α . U=M\sum_{r=1}^{M}b_r^2=\frac{q(1)}{\alpha}. U = M r = 1 ∑ M b r 2 = α q ( 1 ) .
If U ≥ h 2 U\ge h^2 U ≥ h 2 , then (5) follows immediately. Otherwise, a maximizing point u ∗ u_* u ∗ in the definition of h h h lies in ( 0 , 1 ) (0,1) ( 0 , 1 ) : the squared values of the two endpoints are 1 1 1 and q ( 1 ) q(1) q ( 1 ) , both of which are at most U U U . Write
A = q ( u ∗ ) , B = 1 − u ∗ , h = A + B . A=\sqrt{q(u_*)}, \qquad B=1-u_*, \qquad h=A+B. A = q ( u ∗ ) , B = 1 − u ∗ , h = A + B .
In particular, A , B > 0 A,B>0 A , B > 0 . By definition of h h h , the graph of q q q lies below the parabola ( h − 1 + u ) 2 (h-1+u)^2 ( h − 1 + u ) 2 , with equality at u ∗ u_* u ∗ . Since q q q lies below the parabola and agrees with it at u ∗ u_* u ∗ , we have q − ′ ( u ∗ ) ≥ 2 A q'_-(u_*)\ge2A q − ′ ( u ∗ ) ≥ 2 A and q + ′ ( u ∗ ) ≤ 2 A q'_+(u_*)\le2A q + ′ ( u ∗ ) ≤ 2 A . Convexity gives q − ′ ( u ∗ ) ≤ q + ′ ( u ∗ ) q'_-(u_*)\le q'_+(u_*) q − ′ ( u ∗ ) ≤ q + ′ ( u ∗ ) , so both derivatives equal 2 A 2A 2 A . The corresponding tangent lies below q q q , so
q ( u ) ≥ A 2 + 2 A ( u − u ∗ ) for all u ∈ [ 0 , 1 ] . q(u)\ge A^2+2A(u-u_*) \qquad\text{for all }u\in[0,1]. q ( u ) ≥ A 2 + 2 A ( u − u ∗ ) for all u ∈ [ 0 , 1 ] .
In particular, q ( 1 ) ≥ A 2 + 2 A B ≥ A h q(1)\ge A^2+2AB\ge Ah q ( 1 ) ≥ A 2 + 2 A B ≥ A h . Hence, the choice
σ = A h ≤ q ( 1 ) h 2 < α \sigma=\frac{A}{h}\le\frac{q(1)}{h^2}<\alpha σ = h A ≤ h 2 q ( 1 ) < α
is admissible. Substituting the tangent bound gives
q ( u ) σ + ( 1 − u ) 2 1 − σ ≥ h 2 + h B ( u − u ∗ ) 2 ≥ h 2 for all u ∈ [ 0 , 1 ] . \frac{q(u)}{\sigma}+\frac{(1-u)^2}{1-\sigma}
\ge h^2+\frac{h}{B}(u-u_*)^2\ge h^2
\qquad\text{for all }u\in[0,1]. σ q ( u ) + 1 − σ ( 1 − u ) 2 ≥ h 2 + B h ( u − u ∗ ) 2 ≥ h 2 for all u ∈ [ 0 , 1 ] .
Together with (6) , this proves (5) .
We next use the restriction to M M M bags to derive a lower bound on h h h . The first segment of q q q has positive slope, so q ( u ) > u \sqrt{q(u)}>u q ( u ) > u for sufficiently small u > 0 u>0 u > 0 , and hence h > 1 h>1 h > 1 . If h ≥ 2 h\ge2 h ≥ 2 , the desired bound is immediate. We therefore assume that a : = h − 1 a:=h-1 a := h − 1 lies in ( 0 , 1 ) (0,1) ( 0 , 1 ) . The definition of h h h gives
q ( u ) ≤ ( u + a ) 2 for all u ∈ [ 0 , 1 ] . q(u)\le(u+a)^2 \qquad\text{for all }u\in[0,1]. q ( u ) ≤ ( u + a ) 2 for all u ∈ [ 0 , 1 ] .
Moreover, convexity and q ( 0 ) = 0 q(0)=0 q ( 0 ) = 0 imply
q ( u ) ≤ u a q ( a ) ≤ 4 a u for 0 ≤ u ≤ a . q(u)\le\frac{u}{a}q(a)\le4au \qquad\text{for }0\le u\le a. q ( u ) ≤ a u q ( a ) ≤ 4 a u for 0 ≤ u ≤ a .
Consequently, q ( u ) ≤ v ( u ) q(u)\le v(u) q ( u ) ≤ v ( u ) , where
v ( u ) = { 4 a u , 0 ≤ u ≤ a , ( u + a ) 2 , a ≤ u ≤ 1. v(u)=
\begin{cases}
4au, & 0\le u\le a,\\
(u+a)^2, & a\le u\le1.
\end{cases} v ( u ) = { 4 a u , ( u + a ) 2 , 0 ≤ u ≤ a , a ≤ u ≤ 1.
The function v v v follows the line from the origin tangent to the parabola at u = a u=a u = a , and then follows the parabola itself. In particular, v ′ v' v ′ is positive, continuous and non-decreasing.
We now claim that
∫ 0 1 d u q ′ ( u ) ≥ ∫ 0 1 d u v ′ ( u ) . \int_0^1 \frac{du}{q'(u)}\ge\int_0^1 \frac{du}{v'(u)}. ∫ 0 1 q ′ ( u ) d u ≥ ∫ 0 1 v ′ ( u ) d u .
To see this, set D = v − q ≥ 0 D=v-q\ge0 D = v − q ≥ 0 . Convexity of z ↦ 1 / z z\mapsto1/z z ↦ 1/ z gives, almost everywhere,
1 q ′ − 1 v ′ ≥ v ′ − q ′ ( v ′ ) 2 = D ′ ( v ′ ) 2 . \frac{1}{q'}-\frac{1}{v'}\ge\frac{v'-q'}{(v')^2}=\frac{D'}{(v')^2}. q ′ 1 − v ′ 1 ≥ ( v ′ ) 2 v ′ − q ′ = ( v ′ ) 2 D ′ .
Integrating by parts and using the definition of v v v gives
∫ 0 1 ( 1 q ′ ( u ) − 1 v ′ ( u ) ) d u ≥ D ( 1 ) 4 ( 1 + a ) 2 + ∫ a 1 D ( u ) 2 ( u + a ) 3 d u ≥ 0 , \int_0^1\left(\frac{1}{q'(u)}-\frac{1}{v'(u)}\right)du\ge\frac{D(1)}{4(1+a)^2}+\int_a^1\frac{D(u)}{2(u+a)^3}du\ge0, ∫ 0 1 ( q ′ ( u ) 1 − v ′ ( u ) 1 ) d u ≥ 4 ( 1 + a ) 2 D ( 1 ) + ∫ a 1 2 ( u + a ) 3 D ( u ) d u ≥ 0 ,
since D ≥ 0 D\ge0 D ≥ 0 .
Combining the comparison with (4) , we obtain
1 α ≥ ∫ 0 a d u 4 a + ∫ a 1 d u 2 ( u + a ) = 1 4 + 1 2 log 1 + a 2 a . \frac{1}{\alpha}\ge\int_0^a\frac{du}{4a}+\int_a^1\frac{du}{2(u+a)}=\frac{1}{4}+\frac{1}{2}\log\frac{1+a}{2a}. α 1 ≥ ∫ 0 a 4 a d u + ∫ a 1 2 ( u + a ) d u = 4 1 + 2 1 log 2 a 1 + a .
Substituting a = h − 1 a=h-1 a = h − 1 and rearranging gives
h ≥ ( 1 − 1 2 e 1 / 2 − 2 / α ) − 1 . h\ge\left(1-\frac{1}{2}e^{1/2-2/\alpha}\right)^{-1}. h ≥ ( 1 − 2 1 e 1/2 − 2/ α ) − 1 .
By (5) , every partition into M M M bags therefore satisfies
W ( b ) ≥ ( 1 − 1 2 exp ( 1 2 − 2 M M − 1 ) ) − 2 . W(b)\ge\left(1-\frac{1}{2}\exp\left(\frac{1}{2}-\frac{2M}{M-1}\right)\right)^{-2}. W ( b ) ≥ ( 1 − 2 1 exp ( 2 1 − M − 1 2 M ) ) − 2 .
Letting M → ∞ M\to\infty M → ∞ shows that no robustness factor valid for every number of machines can be smaller than
γ = ( 1 − 1 2 e − 3 / 2 ) − 2 = 1.2669187 … . \gamma=\left(1-\frac{1}{2}e^{-3/2}\right)^{-2}=1.2669187\ldots. γ = ( 1 − 2 1 e − 3/2 ) − 2 = 1.2669187 … .
Balanced and cyclic bags (Theorem 6)
Theorem 6. For general speeds, the balanced-bag algorithm for sand and the cyclic-bag algorithm for bricks and rocks are 25/16-robust for minimizing the total completion time. This bound is tight uniformly over the number of machines for these bag constructions, even with an optimal Phase II assignment.
The statement for sand was proved in § 4.2 . We first prove the upper bound for bricks and then extend it to rocks using Lemma 1. The tightness part is shown in Appendix § 8 .§ 3 .
Proof. Fix a speed vector s \boldsymbol{s} s with m ≤ M m \le M m ≤ M available machines and ∑ i = 1 m s i = 1 \sum_{i=1}^{m} s_i = 1 ∑ i = 1 m s i = 1 . Throughout this proof, sums over machines range over i ∈ [ m ] i \in[m] i ∈ [ m ] . Recall that the quadratic marginal assignment considers all M M M bag labels in the order B 1 , … , B M B_1,\ldots,B_M B 1 , … , B M , including empty bags. At each step, it chooses a machine minimizing ( 2 x i + 1 ) / s i (2x_i+1)/s_i ( 2 x i + 1 ) / s i , breaking ties according to the fixed machine order.
Let x i ( h ) x_i(h) x i ( h ) denote the number of bags assigned to machine i i i after h h h steps, and let λ h \lambda_h λ h be the value selected in step h h h . Set λ 0 = 0 \lambda_0=0 λ 0 = 0 . Since the marginal values on each machine increase, the selected values are non-decreasing. Comparing the last selected and the next unselected value on each machine gives
max { 0 , 2 x i ( h ) − 1 } ≤ λ h s i ≤ 2 x i ( h ) + 1 for all i ∈ [ m ] , 0 ≤ h ≤ M . (7) \max\{0,2x_i(h)-1\}\le\lambda_hs_i\le2x_i(h)+1 \qquad\text{for all }i\in[m],\ 0\le h\le M. \tag*{(7)} max { 0 , 2 x i ( h ) − 1 } ≤ λ h s i ≤ 2 x i ( h ) + 1 for all i ∈ [ m ] , 0 ≤ h ≤ M . (7)
If x i ( h ) = 0 x_i(h)=0 x i ( h ) = 0 , the lower bound is immediate and the upper bound follows because the first value 1 / s i 1/s_i 1/ s i remains unselected. These inequalities also hold when h = 0 h=0 h = 0 and in the presence of ties.
Bricks. Write n = q M + ℓ n=qM+\ell n = q M + ℓ , where 0 ≤ ℓ < M 0\le\ell<M 0 ≤ ℓ < M . Each complete round of the cyclic construction contributes one job to every bag, while the last round contributes one additional job to the first ℓ \ell ℓ bags. Set
x i : = x i ( M ) , u i : = x i ( ℓ ) , λ : = λ M , μ : = λ ℓ . x_i:=x_i(M),\qquad u_i:=x_i(\ell),\qquad\lambda:=\lambda_M,\qquad\mu:=\lambda_\ell. x i := x i ( M ) , u i := x i ( ℓ ) , λ := λ M , μ := λ ℓ .
The complete rounds contribute q x i qx_i q x i jobs to machine i i i , and the last round contributes u i u_i u i . Thus, its job count is k i = q x i + u i k_i=qx_i+u_i k i = q x i + u i . Recall that its cost is F ( k i ) / s i F(k_i)/s_i F ( k i ) / s i , where F ( k ) = k ( k + 1 ) / 2 F(k)=k(k+1)/2 F ( k ) = k ( k + 1 ) /2 .
Let z i z_i z i denote the number of jobs assigned to machine i i i in an unrestricted optimal schedule. The optimum may leave a machine unused even when the algorithm assigns jobs to it, so a separate multiplicative comparison on each machine is not possible. We therefore seek common nonnegative values P , G P,G P , G such that
F ( k i ) s i ≤ 25 16 F ( z i ) s i + P ( k i − z i ) + G ( 1 − x i ) . (8) \frac{F(k_i)}{s_i}\le\frac{25}{16}\frac{F(z_i)}{s_i}+P(k_i-z_i)+G(1-x_i). \tag*{(8)} s i F ( k i ) ≤ 16 25 s i F ( z i ) + P ( k i − z i ) + G ( 1 − x i ) . (8)
The terms P ( k i − z i ) P(k_i-z_i) P ( k i − z i ) compensate for different job counts and cancel when summed over all machines. The remaining correction gives an allowance G G G to each available machine and subtracts G G G for each assigned bag. Its total is G ( m − M ) ≤ 0 G(m-M)\le0 G ( m − M ) ≤ 0 .
Suppose first that q ≥ 1 q\ge1 q ≥ 1 . Apply Lemma 9 below with
t = λ s i , w = μ s i , x = x i , u = u i , z = z i . t=\lambda s_i,\qquad w=\mu s_i,\qquad x=x_i,\qquad u=u_i,\qquad z=z_i. t = λ s i , w = μ s i , x = x i , u = u i , z = z i .
Its assumptions follow from (7) , u i ≤ x i u_i\le x_i u i ≤ x i , and μ ≤ λ \mu\le\lambda μ ≤ λ . Dividing the resulting inequality by s i s_i s i gives (8) with
P = ( 5 q + 3 ) λ + 5 μ 8 , G = q ( q − 1 ) λ + 2 q μ 8 . P=\frac{(5q+3)\lambda+5\mu}{8},\qquad G=\frac{q(q-1)\lambda+2q\mu}{8}. P = 8 ( 5 q + 3 ) λ + 5 μ , G = 8 q ( q − 1 ) λ + 2 q μ .
Both values are nonnegative.
If n < M n<M n < M , every nonempty bag contains one job, so q = 0 q=0 q = 0 and k i = u i k_i=u_i k i = u i . We apply the same lemma with
( q , x , u , t , w , z ) = ( 1 , u i , 0 , μ s i , 0 , z i ) . (q,x,u,t,w,z)=(1,u_i,0,\mu s_i,0,z_i). ( q , x , u , t , w , z ) = ( 1 , u i , 0 , μ s i , 0 , z i ) .
This gives (8) with P = μ P=\mu P = μ and G = 0 G=0 G = 0 .
Summing (8) over all available machines yields
Alg ( s ) ≤ 25 16 Opt ( s ) + P ∑ i = 1 m ( k i − z i ) + G ∑ i = 1 m ( 1 − x i ) = 25 16 Opt ( s ) + G ( m − M ) ≤ 25 16 Opt ( s ) , \begin{aligned}
\operatorname{Alg}(s) \le\frac{25}{16}\operatorname{Opt}(s) + P\sum_{i=1}^{m}(k_i-z_i) + G\sum_{i=1}^{m}(1-x_i) \\
&= \frac{25}{16}\operatorname{Opt}(s) + G(m-M) \\
&\le\frac{25}{16}\operatorname{Opt}(s),
\end{aligned} Alg ( s ) ≤ 16 25 Opt ( s ) + P i = 1 ∑ m ( k i − z i ) + G i = 1 ∑ m ( 1 − x i ) = 16 25 Opt ( s ) + G ( m − M ) ≤ 16 25 Opt ( s ) ,
since ∑ i k i = ∑ i z i = n \sum_i k_i=\sum_i z_i=n ∑ i k i = ∑ i z i = n and ∑ i x i = M \sum_i x_i=M ∑ i x i = M .
Rocks. Fix an instance with p 1 ≥ ⋯ ≥ p n p_1 \ge\cdots\ge p_n p 1 ≥ ⋯ ≥ p n . The assignment of jobs to bag labels depends only on their indices and M M M . The assignment map π \pi π for all M M M bag labels depends only on M M M and s s s , including the fixed rule for breaking ties. Thus, for every r ∈ [ n ] r \in[n] r ∈ [ n ] , restricting the assignment to the first r r r jobs and setting their processing times to one gives precisely the algorithm’s assignment for r r r bricks. The preceding argument therefore gives the guarantee for every prefix under the same assignment. Applying Lemma 1 completes the proof. □
It remains to prove the comparison used for bricks. The following lemma combines the threshold inequalities for the complete rounds and the final partial round.
Lemma 9. Let q ≥ 1 q \ge1 q ≥ 1 and 0 ≤ u ≤ x 0 \le u \le x 0 ≤ u ≤ x be integers. Suppose that t , w ≥ 0 t,w \ge0 t , w ≥ 0 satisfy
max { 0 , 2 x − 1 } ≤ t ≤ 2 x + 1 , max { 0 , 2 u − 1 } ≤ w ≤ 2 u + 1 , w ≤ t . \max\{0,2x-1\} \le t \le2x+1,\qquad\max\{0,2u-1\} \le w \le2u+1,\qquad w \le t. max { 0 , 2 x − 1 } ≤ t ≤ 2 x + 1 , max { 0 , 2 u − 1 } ≤ w ≤ 2 u + 1 , w ≤ t . For k = q x + u k=qx+u k = q x + u and every integer z ≥ 0 z \ge0 z ≥ 0 , we have
F ( k ) ≤ 25 16 F ( z ) + ( 5 q + 3 ) t + 5 w 8 ( k − z ) + q ( q − 1 ) t + 2 q w 8 ( 1 − x ) . F(k) \le\frac{25}{16}F(z) + \frac{(5q+3)t+5w}{8}(k-z) + \frac{q(q-1)t+2qw}{8}(1-x). F ( k ) ≤ 16 25 F ( z ) + 8 ( 5 q + 3 ) t + 5 w ( k − z ) + 8 q ( q − 1 ) t + 2 q w ( 1 − x ) .
Proof. Set
P ^ : = ( 5 q + 3 ) t + 5 w , G ^ : = q ( q − 1 ) t + 2 q w , \widehat{P}:=(5q+3)t+5w,\qquad\widehat{G}:=q(q-1)t+2qw, P := ( 5 q + 3 ) t + 5 w , G := q ( q − 1 ) t + 2 q w ,
and write
H : = 25 16 F ( z ) − F ( k ) + P ^ 8 ( k − z ) + G ^ 8 ( 1 − x ) . H:=\frac{25}{16}F(z)-F(k)+\frac{\widehat{P}}{8}(k-z)+\frac{\widehat{G}}{8}(1-x). H := 16 25 F ( z ) − F ( k ) + 8 P ( k − z ) + 8 G ( 1 − x ) .
We show that H ≥ 0 H \ge0 H ≥ 0 . We first reduce the threshold variables to endpoints and the counts to their smallest compatible values. We then minimize the resulting quadratic in z z z and show that its minimum increases with the remaining parameters.
For fixed q , x , u , z q,x,u,z q , x , u , z , the expression H H H is affine in ( t , w ) (t,w) ( t , w ) , so it suffices to consider vertices of their feasible region. If u < x u<x u < x , the constraint w ≤ t w\le t w ≤ t is redundant because 2 u + 1 ≤ 2 x − 1 2u+1\le2x-1 2 u + 1 ≤ 2 x − 1 . If u = x u=x u = x , it cuts the corresponding square along its diagonal. Hence, every positive coordinate of a vertex is an odd integer. If t = 0 t=0 t = 0 , then w = x = u = 0 w=x=u=0 w = x = u = 0 and H = 25 F ( z ) / 16 ≥ 0 H=25F(z)/16\ge0 H = 25 F ( z ) /16 ≥ 0 . Thus, assume t ≥ 1 t\ge1 t ≥ 1 .
Suppose first that w > 0 w>0 w > 0 . Write
x = t − 1 2 + α , u = w − 1 2 + β , α , β ∈ { 0 , 1 } . x=\frac{t-1}{2}+\alpha,\qquad u=\frac{w-1}{2}+\beta,\qquad\alpha,\beta\in\{0,1\}. x = 2 t − 1 + α , u = 2 w − 1 + β , α , β ∈ { 0 , 1 } .
Let H 0 H_0 H 0 be the value obtained by setting α = β = 0 \alpha=\beta=0 α = β = 0 , with k = q x + u k=qx+u k = q x + u adjusted accordingly. Direct subtraction gives
8 ( H − H 0 ) = q α ( 4 t − w ) + β ( ( q + 3 ) t + w + 4 q − 4 ) − 8 q α β ≥ q ( 3 α + 5 β − 8 α β ) = q ( 3 α ( 1 − β ) + 5 β ( 1 − α ) ) ≥ 0. \begin{aligned}
8(H-H_0)=q\alpha(4t-w)+\beta\bigl((q+3)t+w+4q-4\bigr)-8q\alpha\beta\\
&\ge q(3\alpha+5\beta-8\alpha\beta) \\
&=q\bigl(3\alpha(1-\beta)+5\beta(1-\alpha)\bigr)\ge0.
\end{aligned} 8 ( H − H 0 ) = q α ( 4 t − w ) + β ( ( q + 3 ) t + w + 4 q − 4 ) − 8 q α β ≥ q ( 3 α + 5 β − 8 α β ) = q ( 3 α ( 1 − β ) + 5 β ( 1 − α ) ) ≥ 0.
Here, the first inequality follows from t ≥ w ≥ 1 t \ge w \ge1 t ≥ w ≥ 1 .
If w = 0 w = 0 w = 0 , then u = 0 u = 0 u = 0 and the two possible counts are x = ( t − 1 ) / 2 x = (t - 1)/2 x = ( t − 1 ) /2 and x = ( t + 1 ) / 2 x = (t + 1)/2 x = ( t + 1 ) /2 . Increasing x x x from the former to the latter increases H H H by q ( t − 1 ) / 2 ≥ 0 q(t - 1)/2 \ge0 q ( t − 1 ) /2 ≥ 0 . Again, let H 0 H_0 H 0 denote the value for the smaller count. Thus, in both cases it suffices to prove that H 0 ≥ 0 H_0 \ge0 H 0 ≥ 0 .
We first consider t = 1 t = 1 t = 1 . Then w ∈ { 0 , 1 } w \in\{0,1\} w ∈ { 0 , 1 } and both reduced counts are zero. Setting v : = q + w v := q + w v := q + w , we obtain
32 H 0 = ( 5 z − 2 v + 1 ) 2 + 3 z − 1. 32H_0 = (5z - 2v + 1)^2 + 3z - 1. 32 H 0 = ( 5 z − 2 v + 1 ) 2 + 3 z − 1.
This expression is positive for integer z ≥ 1 z \ge1 z ≥ 1 . For z = 0 z = 0 z = 0 , we have H 0 = v ( v − 1 ) / 8 ≥ 0 H_0 = v(v - 1)/8 \ge0 H 0 = v ( v − 1 ) /8 ≥ 0 , since v ≥ 1 v \ge1 v ≥ 1 .
It remains to consider t ≥ 3 t \ge3 t ≥ 3 . Suppose first that w ≥ 1 w \ge1 w ≥ 1 , and define
h ( q , t , w ) : = min z ∈ R H 0 . h(q,t,w) := \min_{z \in\mathbb{R}} H_0. h ( q , t , w ) := z ∈ R min H 0 .
Allowing real values of z z z can only decrease the minimum. The quadratic is minimized at
z ∗ = 4 P ^ − 25 50 . z_* = \frac{4\widehat{P} - 25}{50}. z ∗ = 50 4 P − 25 .
After substituting this value, we show that the minimum increases with q q q and w w w . Differentiating gives
∂ h ∂ q = 20 q ( t − 1 ) + 8 t 2 − 30 t + 25 w 80 ≥ 8 t 2 − 10 t + 5 80 > 0 , \frac{\partial h}{\partial q} = \frac{20q(t - 1) + 8t^2 - 30t + 25w}{80}
\ge\frac{8t^2 - 10t + 5}{80} > 0, ∂ q ∂ h = 80 20 q ( t − 1 ) + 8 t 2 − 30 t + 25 w ≥ 80 8 t 2 − 10 t + 5 > 0 ,
∂ h ∂ w = 25 q + 3 t + 10 w 80 > 0 , \frac{\partial h}{\partial w} = \frac{25q + 3t + 10w}{80} > 0, ∂ w ∂ h = 80 25 q + 3 t + 10 w > 0 ,
where we used q , w ≥ 1 q,w \ge1 q , w ≥ 1 and t ≥ 3 t \ge3 t ≥ 3 . Consequently,
h ( q , t , w ) ≥ h ( 1 , t , 1 ) . h(q,t,w) \ge h(1,t,1). h ( q , t , w ) ≥ h ( 1 , t , 1 ) .
The remaining function also increases with t ≥ 3 t \ge3 t ≥ 3 , since
d d t h ( 1 , t , 1 ) = 44 t − 85 400 > 0. \frac{d}{dt}h(1,t,1) = \frac{44t - 85}{400} > 0. d t d h ( 1 , t , 1 ) = 400 44 t − 85 > 0.
Hence, it suffices to consider q = 1 q = 1 q = 1 , t = 3 t = 3 t = 3 , and w = 1 w = 1 w = 1 . At these values, the reduced counts are x = 1 x = 1 x = 1 and u = 0 u = 0 u = 0 , and
H 0 = 25 z 2 − 91 z + 84 32 . H_0 = \frac{25z^2 - 91z + 84}{32}. H 0 = 32 25 z 2 − 91 z + 84 .
Its minimum is 119 / 3200 > 0 119/3200 > 0 119/3200 > 0 , so
H 0 ≥ h ( q , t , w ) ≥ h ( 1 , 3 , 1 ) = 119 3200 > 0. H_0 \ge h(q,t,w) \ge h(1,3,1) = \frac{119}{3200} > 0. H 0 ≥ h ( q , t , w ) ≥ h ( 1 , 3 , 1 ) = 3200 119 > 0.
Finally, suppose that w = 0 w = 0 w = 0 . Let h 0 ( q , t ) h_0(q,t) h 0 ( q , t ) denote the minimum of the corresponding expression H 0 H_0 H 0 over real z z z . The same quadratic minimization gives
h 0 ( q , t ) − h ( q , t , 1 ) = ( 5 q + 12 ) t − 5 q − 15 80 ≥ 0 , h_0(q,t) - h(q,t,1) = \frac{(5q + 12)t - 5q - 15}{80} \ge0, h 0 ( q , t ) − h ( q , t , 1 ) = 80 ( 5 q + 12 ) t − 5 q − 15 ≥ 0 ,
where the inequality uses t ≥ 3 t \ge3 t ≥ 3 . The preceding argument therefore yields H 0 ≥ h 0 ( q , t ) ≥ h ( q , t , 1 ) > 0 H_0 \ge h_0(q,t) \ge h(q,t,1) > 0 H 0 ≥ h 0 ( q , t ) ≥ h ( q , t , 1 ) > 0 .
Thus, H 0 ≥ 0 H_0 \ge0 H 0 ≥ 0 in every case. Since H ≥ H 0 H \ge H_0 H ≥ H 0 , the claim follows. □ \square □
Tightness for balanced and cyclic bags
We prove the tightness part of Theorem 6: for balanced bags for sand and cyclic bags for bricks and rocks, the robustness factor 25 / 16 25/16 25/16 cannot be improved uniformly over the number of machines, even with an optimal Phase II assignment.
Proof. Let M ≥ 2 M \ge2 M ≥ 2 and set q = 5 M − 2 q = 5M - 2 q = 5 M − 2 . Consider n = q M n = qM n = q M bricks and the speed vector
s 1 = 3 M 2 , s 2 = ⋯ = s M = 1. s_1 = \frac{3M}{2}, \qquad s_2 = \cdots= s_M = 1. s 1 = 2 3 M , s 2 = ⋯ = s M = 1.
Every cyclic bag contains exactly q q q jobs. We use unnormalized speeds, since scaling all speeds does not change the ratio. The choice of q q q will allow us to compare the bag assignment with an integral assignment of individual jobs in proportion to the speeds.
Consider the assignment of any Phase II algorithm, and let x i x_i x i be the number of bags assigned to machine i i i . Its total completion time is
Alg ( s ) = ∑ i = 1 M q x i ( q x i + 1 ) 2 s i ≥ q 2 2 ∑ i = 1 M x i 2 s i . \operatorname{Alg}(s) = \sum_{i=1}^{M} \frac{q x_i(q x_i + 1)}{2s_i} \ge\frac{q^2}{2} \sum_{i=1}^{M} \frac{x_i^2}{s_i}. Alg ( s ) = i = 1 ∑ M 2 s i q x i ( q x i + 1 ) ≥ 2 q 2 i = 1 ∑ M s i x i 2 .
Since the bag counts are nonnegative integers, x i 2 ≥ x i x_i^2 \ge x_i x i 2 ≥ x i . Using ∑ i x i = M \sum_i x_i = M ∑ i x i = M , we obtain
∑ i = 1 M x i 2 s i ≥ 2 x 1 2 3 M + ∑ i = 2 M x i = 2 x 1 2 3 M + M − x 1 = 5 M 8 + 2 3 M ( x 1 − 3 M 4 ) 2 ≥ 5 M 8 . \begin{aligned}
\sum_{i=1}^{M} \frac{x_i^2}{s_i}
&\ge\frac{2x_1^2}{3M} + \sum_{i=2}^{M} x_i \\
&= \frac{2x_1^2}{3M} + M - x_1 \\
&= \frac{5M}{8} + \frac{2}{3M}\left(x_1 - \frac{3M}{4}\right)^2 \\
&\ge\frac{5M}{8}.
\end{aligned} i = 1 ∑ M s i x i 2 ≥ 3 M 2 x 1 2 + i = 2 ∑ M x i = 3 M 2 x 1 2 + M − x 1 = 8 5 M + 3 M 2 ( x 1 − 4 3 M ) 2 ≥ 8 5 M .
Thus, every assignment of the bags has cost at least 5 q 2 M / 16 5q^2M/16 5 q 2 M /16 .
To upper-bound the unrestricted optimum, assign z i = 2 M s i z_i = 2Ms_i z i = 2 M s i jobs to machine i i i . These numbers are integers: the fast machine receives 3 M 2 3M^2 3 M 2 jobs, and each slow machine receives 2 M 2M 2 M jobs. Moreover, since ∑ i s i = q / 2 \sum_i s_i = q/2 ∑ i s i = q /2 , this assignment contains exactly M q = n Mq = n M q = n jobs. Its cost is
∑ i = 1 M z i ( z i + 1 ) 2 s i = 2 M 2 ∑ i = 1 M s i + M 2 = M 2 ( q + 1 ) . \sum_{i=1}^{M} \frac{z_i(z_i + 1)}{2s_i} = 2M^2 \sum_{i=1}^{M} s_i + M^2 = M^2(q + 1). i = 1 ∑ M 2 s i z i ( z i + 1 ) = 2 M 2 i = 1 ∑ M s i + M 2 = M 2 ( q + 1 ) .
Consequently,
Alg ( s ) Opt ( s ) ≥ 5 q 2 16 M ( q + 1 ) = 5 ( 5 M − 2 ) 2 16 M ( 5 M − 1 ) ⟶ 25 16 as M → ∞ . \frac{\operatorname{Alg}(s)}{\operatorname{Opt}(s)} \ge\frac{5q^2}{16M(q+1)} = \frac{5(5M-2)^2}{16M(5M-1)} \longrightarrow\frac{25}{16} \quad\text{as } M \to\infty. Opt ( s ) Alg ( s ) ≥ 16 M ( q + 1 ) 5 q 2 = 16 M ( 5 M − 1 ) 5 ( 5 M − 2 ) 2 ⟶ 16 25 as M → ∞.
Thus, the bound holds already for bricks and for every Phase II assignment, including an optimal one.
The same speed vector proves tightness for balanced sand bags. Its total speed is S = ( 5 M − 2 ) / 2 S = (5M - 2)/2 S = ( 5 M − 2 ) /2 , and every assignment of bags of volume 1 / M 1/M 1/ M satisfies
R ( s ) = S M 2 ∑ i = 1 M x i 2 s i ≥ 5 ( 5 M − 2 ) 16 M = 25 16 − 5 8 M ⟶ 25 16 . \begin{aligned}
R(s) = \frac{S}{M^2} \sum_{i=1}^{M} \frac{x_i^2}{s_i} \ge\frac{5(5M-2)}{16M} \\
&= \frac{25}{16} - \frac{5}{8M} \longrightarrow\frac{25}{16}.
\end{aligned} R ( s ) = M 2 S i = 1 ∑ M s i x i 2 ≥ 16 M 5 ( 5 M − 2 ) = 16 25 − 8 M 5 ⟶ 16 25 .
Imbalanced bags for sand (Theorem 7)
Theorem 7. For general speeds, the imbalanced-bag algorithm is 1681/1152-robust for minimizing the total completion time of sand, where 1681/1152 \approx 1.4592.
Proof. Fix a speed vector s \mathbf{s} s with m m m available machines and ∑ i = 1 m s i = 1 \sum_{i=1}^{m} s_i = 1 ∑ i = 1 m s i = 1 . Let b 1 ≤ ⋯ ≤ b M b_1 \le\cdots\le b_M b 1 ≤ ⋯ ≤ b M be the bag volumes in assignment order, let π \pi π be the resulting bag-to-machine assignment, and let x i x_i x i be the number of bags assigned to machine i i i .
Let λ \lambda λ be the largest selection score used when determining the bag counts. On each occupied machine, the last selected score is at most λ \lambda λ , and the next score is at least λ \lambda λ . Thus,
3 x i − 2 ≤ λ s i ≤ 3 x i + 1 if x i > 0 , λ s i ≤ 1 if x i = 0. 3x_i - 2 \le\lambda s_i \le3x_i + 1 \quad\text{if } x_i > 0, \qquad\lambda s_i \le1 \quad\text{if } x_i = 0. 3 x i − 2 ≤ λ s i ≤ 3 x i + 1 if x i > 0 , λ s i ≤ 1 if x i = 0.
For each bag r ∈ [ M ] r \in[M] r ∈ [ M ] , define
t r = max { 1 3 , x π ( r ) λ s π ( r ) } , g ( t ) = 3 2 t − 1 2 . t_r = \max\left\{\frac{1}{3}, \frac{x_{\pi(r)}}{\lambda s_{\pi(r)}}\right\}, \qquad g(t) = \frac{3}{2t} - \frac{1}{2}. t r = max { 3 1 , λ s π ( r ) x π ( r ) } , g ( t ) = 2 t 3 − 2 1 .
The threshold inequalities imply t r ∈ [ 1 / 3 , 1 ] t_r \in[1/3,1] t r ∈ [ 1/3 , 1 ] . Moreover, the algorithm assigns bags in non-decreasing volume order to machines in non-increasing x i / s i x_i/s_i x i / s i order. Since the definition of t r t_r t r preserves this ordering, we have
1 ≥ t 1 ≥ ⋯ ≥ t M ≥ 1 3 . 1 \ge t_1 \ge\cdots\ge t_M \ge\frac{1}{3}. 1 ≥ t 1 ≥ ⋯ ≥ t M ≥ 3 1 .
We first relate λ \lambda λ to these coefficients. All bags assigned to an occupied machine i i i have the same coefficient, and
∑ r : π ( r ) = i g ( t r ) = min { 4 x i , 3 λ s i − x i 2 } ≥ λ s i + x i − 1. \sum_{r:\pi(r)=i} g(t_r) = \min\left\{4x_i,\frac{3\lambda s_i-x_i}{2}\right\} \ge\lambda s_i+x_i-1. r : π ( r ) = i ∑ g ( t r ) = min { 4 x i , 2 3 λ s i − x i } ≥ λ s i + x i − 1.
Indeed, the first expression inside the minimum satisfies the inequality by λ s i ≤ 3 x i + 1 \lambda s_i \le3x_i+1 λ s i ≤ 3 x i + 1 , and the second by λ s i ≥ 3 x i − 2 \lambda s_i \ge3x_i-2 λ s i ≥ 3 x i − 2 . For an unused available machine, the same inequality holds because its left-hand side is zero and λ s i ≤ 1 \lambda s_i \le1 λ s i ≤ 1 . Summing over all available machines therefore gives
∑ r = 1 M g ( t r ) ≥ λ ∑ i = 1 m s i + ∑ i = 1 m x i − m = λ + M − m ≥ λ . (9) \sum_{r=1}^{M} g(t_r) \ge\lambda\sum_{i=1}^{m} s_i + \sum_{i=1}^{m} x_i - m = \lambda+ M - m \ge\lambda. \tag*{(9)} r = 1 ∑ M g ( t r ) ≥ λ i = 1 ∑ m s i + i = 1 ∑ m x i − m = λ + M − m ≥ λ . (9)
We next bound the ratio of the assignment. By Cauchy–Schwarz on each occupied machine,
R ( s ) = ∑ i : x i > 0 ( ∑ r : π ( r ) = i b r ) 2 s i ≤ ∑ i : x i > 0 x i s i ∑ r : π ( r ) = i b r 2 ≤ λ ∑ r = 1 M t r b r 2 . \begin{aligned}
R(\mathbf{s}) &= \sum_{i:x_i>0} \frac{\left(\sum_{r:\pi(r)=i} b_r\right)^2}{s_i} \\
&\le\sum_{i:x_i>0} \frac{x_i}{s_i}\sum_{r:\pi(r)=i} b_r^2 \\
&\le\lambda\sum_{r=1}^{M} t_r b_r^2.
\end{aligned} R ( s ) = i : x i > 0 ∑ s i ( ∑ r : π ( r ) = i b r ) 2 ≤ i : x i > 0 ∑ s i x i r : π ( r ) = i ∑ b r 2 ≤ λ r = 1 ∑ M t r b r 2 .
The last inequality follows from the definition of t r t_r t r . Together with (10), this yields
R ( s ) ≤ ( ∑ r = 1 M g ( t r ) ) ( ∑ r = 1 M t r b r 2 ) . (10) R(\mathbf{s}) \le\left(\sum_{r=1}^{M} g(t_r)\right)\left(\sum_{r=1}^{M} t_r b_r^2\right). \tag*{(10)} R ( s ) ≤ ( r = 1 ∑ M g ( t r ) ) ( r = 1 ∑ M t r b r 2 ) . (10)
It remains to bound the product on the right-hand side. We maximize it over all ordered coefficients 1 ≥ t 1 ≥ ⋯ ≥ t M ≥ 1 / 3 1 \ge t_1 \ge\cdots\ge t_M \ge1/3 1 ≥ t 1 ≥ ⋯ ≥ t M ≥ 1/3 , keeping the bag volumes fixed. This relaxation can only increase the upper bound. We show that it suffices to consider coefficients taking only the values 1 / 3 1/3 1/3 and 1 1 1 .
Choose a value v ∈ ( 1 / 3 , 1 ) v \in(1/3,1) v ∈ ( 1/3 , 1 ) occurring among the coefficients, and let
G = { r : t r = v } , q = ∣ G ∣ . G=\{r:t_r=v\},\qquad q=|G|. G = { r : t r = v } , q = ∣ G ∣.
Since the coefficients are ordered, G G G consists of consecutive indices. Replace their common value by u u u , keeping all other coefficients fixed. To preserve the ordering, u u u may vary between the nearest smaller and larger coefficient values, using the boundary 1 / 3 1/3 1/3 or 1 1 1 if no such value exists.
Define
A = ∑ r ∉ G g ( t r ) , B = ∑ r ∉ G t r b r 2 , W = ∑ r ∈ G b r 2 . A=\sum_{r\notin G}g(t_r),\qquad B=\sum_{r\notin G}t_rb_r^2,\qquad W=\sum_{r\in G}b_r^2. A = r ∈ / G ∑ g ( t r ) , B = r ∈ / G ∑ t r b r 2 , W = r ∈ G ∑ b r 2 .
Thus, A A A and B B B are the fixed contributions to the two factors from indices outside G G G . The indices in G G G contribute q g ( u ) qg(u) q g ( u ) to the first factor and u W uW u W to the second. Hence, the product becomes
Φ ( u ) = ( A + q g ( u ) ) ( B + u W ) = ( A + 3 q 2 u − q 2 ) ( B + u W ) . \Phi(u)=(A+qg(u))(B+uW)=\left(A+\frac{3q}{2u}-\frac{q}{2}\right)(B+uW). Φ ( u ) = ( A + q g ( u )) ( B + u W ) = ( A + 2 u 3 q − 2 q ) ( B + u W ) .
The only nonlinear term depending on u u u is 3 q B / ( 2 u ) 3qB/(2u) 3 q B / ( 2 u ) . Since B ≥ 0 B\ge0 B ≥ 0 , the function Φ \Phi Φ is convex. We may therefore move u u u to an endpoint of its admissible interval without decreasing the product.
Such a move either merges G G G with a neighboring group of equal coefficients or gives its coordinates the value 1 / 3 1/3 1/3 or 1 1 1 . In either case, one distinct value in ( 1 / 3 , 1 ) (1/3,1) ( 1/3 , 1 ) disappears. Repeating this step leaves, for some k ∈ { 0 , … , M } k\in\{0,\ldots,M\} k ∈ { 0 , … , M } , the first k k k coefficients equal to 1 1 1 and the remaining M − k M-k M − k coefficients equal to 1 / 3 1/3 1/3 .
Set
θ = k M , Q = ∑ r = 1 M b r 2 , Q k = ∑ r = 1 k b r 2 . \theta=\frac{k}{M},\qquad Q=\sum_{r=1}^{M}b_r^2,\qquad Q_k=\sum_{r=1}^{k}b_r^2. θ = M k , Q = r = 1 ∑ M b r 2 , Q k = r = 1 ∑ k b r 2 .
Since g ( 1 ) = 1 g(1)=1 g ( 1 ) = 1 and g ( 1 / 3 ) = 4 g(1/3)=4 g ( 1/3 ) = 4 , the product at these coefficients is
( ∑ r = 1 M g ( t r ) ) ( ∑ r = 1 M t r b r 2 ) = ( 4 M − 3 k ) ( Q k + Q − Q k 3 ) = ( 4 3 − θ ) ( M Q + 2 M Q k ) . \begin{aligned}
\left(\sum_{r=1}^{M}g(t_r)\right)\left(\sum_{r=1}^{M}t_rb_r^2\right)=(4M-3k)\left(Q_k+\frac{Q-Q_k}{3}\right) \\
&=\left(\frac{4}{3}-\theta\right)(MQ+2MQ_k).
\end{aligned} ( r = 1 ∑ M g ( t r ) ) ( r = 1 ∑ M t r b r 2 ) = ( 4 M − 3 k ) ( Q k + 3 Q − Q k ) = ( 3 4 − θ ) ( M Q + 2 M Q k ) .
Recall that the construction uses ⌊ M / 2 ⌋ \lfloor M/2\rfloor ⌊ M /2 ⌋ bags of volume 3 / ( 4 M ) 3/(4M) 3/ ( 4 M ) and the same number of bags of volume 5 / ( 4 M ) 5/(4M) 5/ ( 4 M ) , together with one bag of volume 1 / M 1/M 1/ M if M M M is odd. Direct summation gives
M Q ≤ 17 16 , M Q k ≤ { 9 θ / 16 , θ ≤ 1 / 2 , 25 θ / 16 − 1 / 2 , θ ≥ 1 / 2. MQ\le\frac{17}{16},\qquad MQ_k\le
\begin{cases}
9\theta/16, & \theta\le1/2,\\
25\theta/16-1/2, & \theta\ge1/2.
\end{cases} M Q ≤ 16 17 , M Q k ≤ { 9 θ /16 , 25 θ /16 − 1/2 , θ ≤ 1/2 , θ ≥ 1/2.
For even M M M , both bounds hold with equality. For odd M M M , we have M Q = 17 / 16 − 1 / ( 16 M ) MQ=17/16-1/(16M) M Q = 17/16 − 1/ ( 16 M ) . The bound for M Q k MQ_k M Q k is an equality when θ ≤ 1 / 2 \theta\le1/2 θ ≤ 1/2 , while for θ ≥ 1 / 2 \theta\ge1/2 θ ≥ 1/2 its value is 1 / ( 16 M ) 1/(16M) 1/ ( 16 M ) below the displayed upper bound. Thus, the same bounds apply in both cases.
It remains to bound the two resulting quadratics. Completing the square gives
( 4 3 − θ ) ( 17 16 + 9 θ 8 ) = 1681 1152 − 9 8 ( θ − 7 36 ) 2 , ( 4 3 − θ ) ( 1 16 + 25 θ 8 ) = 41209 28800 − 25 8 ( θ − 197 300 ) 2 . \begin{aligned}
\left(\frac{4}{3}-\theta\right)\left(\frac{17}{16}+\frac{9\theta}{8}\right)&=\frac{1681}{1152}-\frac{9}{8}\left(\theta-\frac{7}{36}\right)^2,\\
\left(\frac{4}{3}-\theta\right)\left(\frac{1}{16}+\frac{25\theta}{8}\right)&=\frac{41209}{28800}-\frac{25}{8}\left(\theta-\frac{197}{300}\right)^2.
\end{aligned} ( 3 4 − θ ) ( 16 17 + 8 9 θ ) ( 3 4 − θ ) ( 16 1 + 8 25 θ ) = 1152 1681 − 8 9 ( θ − 36 7 ) 2 , = 28800 41209 − 8 25 ( θ − 300 197 ) 2 .
Since 41209 / 28800 < 1681 / 1152 41209/28800 < 1681/1152 41209/28800 < 1681/1152 , both expressions are at most 1681 / 1152 1681/1152 1681/1152 . Applying (10) therefore yields
R ( s ) ≤ 1681 1152 . R(s) \le\frac{1681}{1152}. R ( s ) ≤ 1152 1681 .
Additional variants (mentioned in § 1.1 )
The non-adaptive model
We consider the non-adaptive variant of our two-stage scheduling problem for an unknown number of identical machines. An instance consists of n n n jobs with processing times p j > 0 p_j > 0 p j > 0 , j ∈ [ n ] j \in[n] j ∈ [ n ] , and the number M M M of bags. All jobs are available at time zero.
In Phase I, the algorithm partitions the jobs into M M M bags, some of which may be empty. An adversary then reveals the number m ∈ [ M ] m \in[M] m ∈ [ M ] of available unit-speed machines. In Phase II, the algorithm assigns every bag as a whole to a machine and chooses the order of the bags on each machine. Within each bag, jobs are processed in SPT order, which is optimal for any assignment and ordering of the bags. The difference from the original model is that bags must be scheduled contiguously.
For a fixed instance, let Alg ( m , M ) \operatorname{Alg}(m,M) Alg ( m , M ) denote the total completion time of the algorithm’s schedule and let Opt m \operatorname{Opt}_m Opt m denote the minimum total completion time when the number m m m of machines is known in advance and jobs may be assigned individually, without bag constraints. An algorithm is ρ \rho ρ -robust if Alg ( m , M ) ≤ ρ Opt m \operatorname{Alg}(m,M) \le\rho\operatorname{Opt}_m Alg ( m , M ) ≤ ρ Opt m for every instance and every m ∈ [ M ] m \in[M] m ∈ [ M ] . The optimal robustness factor is the infimum of the robustness factors of all deterministic algorithms.
Let k k k denote the number of distinct processing times. Writing M + k − 1 = k r + s M+k-1=kr+s M + k − 1 = k r + s , where r ≥ 1 r \ge1 r ≥ 1 and 0 ≤ s < k 0 \le s < k 0 ≤ s < k , we define
ρ M , k : = M k ( s r + 1 + k − s r ) . \rho_{M,k} := \frac{M}{k}\left(\frac{s}{r+1}+\frac{k-s}{r}\right). ρ M , k := k M ( r + 1 s + r k − s ) .
For M , k ≥ 2 M,k \ge2 M , k ≥ 2 , we show that ρ M , k \rho_{M,k} ρ M , k is the optimal deterministic robustness factor for M M M bags and instances with k k k distinct processing times. The lower bound is proved in Theorem 8, and a matching algorithm is given in Theorem 9.
Since s ( r + 1 ) + ( k − s ) r = M + k − 1 s(r+1)+(k-s)r=M+k-1 s ( r + 1 ) + ( k − s ) r = M + k − 1 and r = ⌈ M / k ⌉ r=\lceil M/k\rceil r = ⌈ M / k ⌉ , the Cauchy–Schwarz inequality and the definition of ρ M , k \rho_{M,k} ρ M , k give
M k M + k − 1 ≤ ρ M , k ≤ M r ≤ min { M , k } . \frac{Mk}{M+k-1} \le\rho_{M,k} \le\frac{M}{r} \le\min\{M,k\}. M + k − 1 M k ≤ ρ M , k ≤ r M ≤ min { M , k } .
For the lower bound, the adversary only needs to choose between one and M M M available machines. We construct job classes with increasingly separated processing times. On one machine, processing a fixed positive fraction of a longer class before a fixed positive fraction of a shorter class leads to a total completion time that is unbounded compared to that of SPT. Since bags must be processed contiguously, bounded robustness on one machine forces the limiting assignment to respect SPT order across the bags. This restricts how widely classes can be distributed among bags. When all M M M machines are available, however, an unrestricted schedule can distribute every class evenly. Comparing the resulting costs yields the lower bound.
Towards this, we first establish a structural property. Index the processing-time classes J 1 , … , J k J_1,\ldots,J_k J 1 , … , J k in increasing order, and let x i b x_{ib} x ib denote the fraction of class J i J_i J i assigned to bag B b B_b B b , with ∑ b = 1 M x i b = 1 \sum_{b=1}^{M}x_{ib}=1 ∑ b = 1 M x ib = 1 for every i ∈ [ k ] i \in[k] i ∈ [ k ] . The following lemma bounds the sum, over all classes, of the number of bags containing a positive fraction of that class. In the lower-bound proof, we apply the lemma to the limiting assignment.
Lemma 10. Assume that the bags are ordered such that x j a x i b = 0 x_{ja}x_{ib}=0 x j a x ib = 0 for every i < j i<j i < j and a < b a<b a < b . Denote by
z i : = ∣ { b ∈ [ M ] : x i b > 0 } ∣ z_i := \left|\{b \in[M] : x_{ib} > 0\}\right| z i := ∣ { b ∈ [ M ] : x ib > 0 } ∣ the number of bags containing a positive fraction of class J i J_i J i . Then
∑ i = 1 k z i ≤ M + k − 1. \sum_{i=1}^{k} z_i \le M+k-1. i = 1 ∑ k z i ≤ M + k − 1.
Proof. For every class J i J_i J i , let
a i : = min { b ∈ [ M ] : x i b > 0 } , b i : = max { b ∈ [ M ] : x i b > 0 } a_i := \min\{b \in[M] : x_{ib} > 0\}, \qquad b_i := \max\{b \in[M] : x_{ib} > 0\} a i := min { b ∈ [ M ] : x ib > 0 } , b i := max { b ∈ [ M ] : x ib > 0 }
denote the first and last bags containing jobs from J i J_i J i , respectively. The assumption implies b i ≤ a i + 1 b_i \le a_{i+1} b i ≤ a i + 1 for every i ∈ [ k − 1 ] i \in[k-1] i ∈ [ k − 1 ] , since otherwise x i + 1 , a i + 1 x i , b i > 0 x_{i+1,a_{i+1}}x_{i,b_i} > 0 x i + 1 , a i + 1 x i , b i > 0 .
Since only bags between a i a_i a i and b i b_i b i can contain jobs from J i J_i J i , we get z i ≤ b i − a i + 1 z_i \le b_i-a_i+1 z i ≤ b i − a i + 1 . Summing over all classes yields
∑ i = 1 k z i ≤ ∑ i = 1 k ( b i − a i + 1 ) = k + b k − a 1 + ∑ i = 1 k − 1 ( b i − a i + 1 ) ≤ M + k − 1 , \sum_{i=1}^{k} z_i \le\sum_{i=1}^{k}(b_i-a_i+1)=k+b_k-a_1+\sum_{i=1}^{k-1}(b_i-a_{i+1})\le M+k-1, i = 1 ∑ k z i ≤ i = 1 ∑ k ( b i − a i + 1 ) = k + b k − a 1 + i = 1 ∑ k − 1 ( b i − a i + 1 ) ≤ M + k − 1 ,
where the last inequality follows from a 1 ≥ 1 a_1 \ge1 a 1 ≥ 1 , b k ≤ M b_k \le M b k ≤ M , and b i ≤ a i + 1 b_i \le a_{i+1} b i ≤ a i + 1 for every i ∈ [ k − 1 ] i \in[k-1] i ∈ [ k − 1 ] .
We now construct instances for which bounded robustness on one machine forces the ordering condition of Lemma 10 in the limit.
Theorem 8. Let M , k ≥ 1 M,k \ge1 M , k ≥ 1 . For every deterministic non-adaptive algorithm using M M M bags and every ε > 0 \varepsilon> 0 ε > 0 , there exists an instance with exactly k k k distinct processing times on which the adversary can force a ratio of at least ρ M , k − ε \rho_{M,k}-\varepsilon ρ M , k − ε by choosing either one or M M M identical machines.
Proof. The claim is immediate if M = 1 M=1 M = 1 or k = 1 k=1 k = 1 , since ρ M , k = 1 \rho_{M,k}=1 ρ M , k = 1 . Therefore, assume M , k ≥ 2 M,k \ge2 M , k ≥ 2 , and fix a deterministic algorithm and ε > 0 \varepsilon> 0 ε > 0 .
For every integer T ≥ 2 T \ge2 T ≥ 2 , let q = M T q=MT q = M T and construct an instance with k i = T k − i q k_i=T^{k-i}q k i = T k − i q jobs of processing time ℓ i = T 2 ( i − 1 ) \ell_i=T^{2(i-1)} ℓ i = T 2 ( i − 1 ) for every i ∈ [ k ] i \in[k] i ∈ [ k ] . Then ℓ 1 < ⋯ < ℓ k \ell_1<\cdots<\ell_k ℓ 1 < ⋯ < ℓ k , and M ∣ k i M \mid k_i M ∣ k i for every i i i . Write Alg T ( m , M ) \operatorname{Alg}_T(m,M) Alg T ( m , M ) and Opt m , T \operatorname{Opt}_{m,T} Opt m , T for the algorithm’s cost and the unrestricted optimum on this instance, respectively. All asymptotic statements below refer to T → ∞ T\to\infty T → ∞ , with M M M and k k k fixed.
Let W : = T 2 k − 2 q 2 W:=T^{2k-2}q^2 W := T 2 k − 2 q 2 . By construction, we have ℓ i k i 2 = W \ell_i k_i^2=W ℓ i k i 2 = W for every class i ∈ [ k ] i\in[k] i ∈ [ k ] . Moreover, the linear terms satisfy
ℓ i k i = W k i ≤ W q = o ( W ) . \ell_i k_i=\frac{W}{k_i}\le\frac{W}{q}=o(W). ℓ i k i = k i W ≤ q W = o ( W ) . For every i < j i<j i < j , the cross-contribution in SPT order satisfies
ℓ i k i k j = W T i − j ≤ W T = o ( W ) . (11) \ell_i k_i k_j=WT^{i-j}\le\frac{W}{T}=o(W). \tag*{(11)} ℓ i k i k j = W T i − j ≤ T W = o ( W ) . (11) Thus, all classes have the same leading contribution, while the linear terms and cross-contributions in SPT order are of lower order.
Each pair in which a job of class J j J_j J j precedes a job of class J i J_i J i , where i < j i<j i < j , incurs an additional cost of ℓ j − ℓ i \ell_j-\ell_i ℓ j − ℓ i compared with SPT order. Moreover,
( ℓ j − ℓ i ) k i k j W = T j − i − T i − j ⟶ ∞ . (12) \frac{(\ell_j-\ell_i)k_i k_j}{W}=T^{j-i}-T^{i-j}\longrightarrow\infty. \tag*{(12)} W ( ℓ j − ℓ i ) k i k j = T j − i − T i − j ⟶ ∞. (12)
Hence, a fraction bounded away from zero of such inverted pairs incurs an unbounded cost relative to W W W .
Suppose, for contradiction, that the claimed lower bound does not hold for this algorithm and ε \varepsilon ε . Then, for every integer T ≥ 2 T \ge2 T ≥ 2 and every m ∈ { 1 , M } m \in\{1,M\} m ∈ { 1 , M } ,
A L G T ( m , M ) O P T m , T < ρ M , k − ε . (13) \frac{\mathrm{ALG}_{T}(m,M)}{\mathrm{OPT}_{m,T}} < \rho_{M,k} - \varepsilon. \tag*{(13)} OPT m , T ALG T ( m , M ) < ρ M , k − ε . (13)
For every T T T , relabel the bags B 1 , … , B M B_1,\ldots,B_M B 1 , … , B M according to the order in which the algorithm processes them when m = 1 m=1 m = 1 . Let x i b ( T ) x_{ib}^{(T)} x ib ( T ) denote the fraction of class J i J_i J i assigned to bag B b B_b B b . Thus,
x i b ( T ) ≥ 0 , ∑ b = 1 M x i b ( T ) = 1. x_{ib}^{(T)} \ge0,\qquad\sum_{b=1}^{M} x_{ib}^{(T)} = 1. x ib ( T ) ≥ 0 , b = 1 ∑ M x ib ( T ) = 1.
Since the vectors ( x i b ( T ) ) i ∈ [ k ] , b ∈ [ M ] (x_{ib}^{(T)})_{i\in[k],b\in[M]} ( x ib ( T ) ) i ∈ [ k ] , b ∈ [ M ] lie in the compact set [ 0 , 1 ] k M [0,1]^{kM} [ 0 , 1 ] k M , we may pass to a subsequence of integers T → ∞ T \to\infty T → ∞ such that
x i b ( T ) ⟶ x i b ∗ (14) x_{ib}^{(T)} \longrightarrow x_{ib}^{*} \tag*{(14)} x ib ( T ) ⟶ x ib ∗ (14)
for every i ∈ [ k ] i \in[k] i ∈ [ k ] and b ∈ [ M ] b \in[M] b ∈ [ M ] . The limiting fractions satisfy x i b ∗ ≥ 0 x_{ib}^{*} \ge0 x ib ∗ ≥ 0 and ∑ b x i b ∗ = 1 \sum_b x_{ib}^{*}=1 ∑ b x ib ∗ = 1 . In the remainder, all limits are taken along this subsequence.
First, let m = 1 m=1 m = 1 . Since an optimal schedule processes the jobs in SPT order, the preceding estimates yield
O P T 1 , T = k W 2 + o ( W ) . \mathrm{OPT}_{1,T} = \frac{kW}{2} + o(W). OPT 1 , T = 2 k W + o ( W ) .
Suppose that x j a ∗ x i b ∗ > 0 x_{ja}^{*}x_{ib}^{*}>0 x j a ∗ x ib ∗ > 0 for some i < j i<j i < j and a < b a<b a < b . Every job of class J j J_j J j in bag B a B_a B a precedes every job of class J i J_i J i in bag B b B_b B b . By (12) ,
A L G T ( 1 , M ) − O P T 1 , T W ≥ ( T j − i − T i − j ) x j a ( T ) x i b ( T ) ⟶ ∞ . \frac{\mathrm{ALG}_{T}(1,M)-\mathrm{OPT}_{1,T}}{W}
\ge(T^{j-i}-T^{i-j})x_{ja}^{(T)}x_{ib}^{(T)} \longrightarrow\infty. W ALG T ( 1 , M ) − OPT 1 , T ≥ ( T j − i − T i − j ) x j a ( T ) x ib ( T ) ⟶ ∞.
This contradicts (13) , since O P T 1 , T / W → k / 2 \mathrm{OPT}_{1,T}/W \to k/2 OPT 1 , T / W → k /2 . Thus, x j a ∗ x i b ∗ = 0 x_{ja}^{*}x_{ib}^{*}=0 x j a ∗ x ib ∗ = 0 for every i < j i<j i < j and a < b a<b a < b .
Let
z i : = ∣ { b ∈ [ M ] : x i b ∗ > 0 } ∣ z_i := \lvert\{b\in[M]:x_{ib}^{*}>0\}\rvert z i := ∣{ b ∈ [ M ] : x ib ∗ > 0 }∣
denote the number of bags containing a positive fraction of class J i J_i J i in the limiting assignment. By Lemma 10,
∑ i = 1 k z i ≤ M + k − 1. (15) \sum_{i=1}^{k} z_i \le M+k-1. \tag*{(15)} i = 1 ∑ k z i ≤ M + k − 1. (15)
Now, let m = M m=M m = M . Since M ∣ k i M\mid k_i M ∣ k i for every i i i , we may assign exactly k i / M k_i/M k i / M jobs of each class to every machine and process them in SPT order. Hence,
O P T M , T ≤ ∑ i = 1 k ( ℓ i k i 2 2 M + ℓ i k i 2 ) + 1 M ∑ 1 ≤ i < j ≤ k ℓ i k i k j = k W 2 M + o ( W ) . (16) \begin{aligned}
\mathrm{OPT}_{M,T} &\le\sum_{i=1}^{k}\left(\frac{\ell_i k_i^2}{2M}+\frac{\ell_i k_i}{2}\right)+\frac{1}{M}\sum_{1\le i<j\le k}\ell_i k_i k_j \\
&= \frac{kW}{2M}+o(W). \tag*{(16)}
\end{aligned} OPT M , T ≤ i = 1 ∑ k ( 2 M ℓ i k i 2 + 2 ℓ i k i ) + M 1 1 ≤ i < j ≤ k ∑ ℓ i k i k j = 2 M k W + o ( W ) . (16)
The quadratic self-contribution of class J i J_i J i within bag B b B_b B b is
ℓ i 2 ( k i x i b ( T ) ) 2 = W 2 ( x i b ( T ) ) 2 . \frac{\ell_i}{2}(k_i x_{ib}^{(T)})^2=\frac{W}{2}(x_{ib}^{(T)})^2. 2 ℓ i ( k i x ib ( T ) ) 2 = 2 W ( x ib ( T ) ) 2 .
All remaining contributions are nonnegative, independently of how the bags are assigned and ordered in Phase II. Therefore,
Alg T ( M , M ) ≥ W 2 ∑ i = 1 k ∑ b = 1 M ( x i b ( T ) ) 2 . \operatorname{Alg}_{T}(M,M) \ge\frac{W}{2}\sum_{i=1}^{k}\sum_{b=1}^{M}\left(x_{ib}^{(T)}\right)^2. Alg T ( M , M ) ≥ 2 W i = 1 ∑ k b = 1 ∑ M ( x ib ( T ) ) 2 .
Together with (14) and (16) , this yields
lim inf T → ∞ Alg T ( M , M ) Opt M , T ≥ M k ∑ i = 1 k ∑ b = 1 M ( x i b ∗ ) 2 . \liminf_{T\to\infty}\frac{\operatorname{Alg}_{T}(M,M)}{\operatorname{Opt}_{M,T}} \ge\frac{M}{k}\sum_{i=1}^{k}\sum_{b=1}^{M}\left(x_{ib}^{*}\right)^2. T → ∞ lim inf Opt M , T Alg T ( M , M ) ≥ k M i = 1 ∑ k b = 1 ∑ M ( x ib ∗ ) 2 .
For every i ∈ [ k ] i \in[k] i ∈ [ k ] , the Cauchy–Schwarz inequality gives
1 = ( ∑ b : x i b ∗ > 0 x i b ∗ ) 2 ≤ z i ∑ b = 1 M ( x i b ∗ ) 2 . 1=\left(\sum_{b:x_{ib}^{*}>0}x_{ib}^{*}\right)^2\le z_i\sum_{b=1}^{M}\left(x_{ib}^{*}\right)^2. 1 = b : x ib ∗ > 0 ∑ x ib ∗ 2 ≤ z i b = 1 ∑ M ( x ib ∗ ) 2 .
Consequently,
lim inf T → ∞ Alg T ( M , M ) Opt M , T ≥ M k ∑ i = 1 k 1 z i . \liminf_{T\to\infty}\frac{\operatorname{Alg}_{T}(M,M)}{\operatorname{Opt}_{M,T}} \ge\frac{M}{k}\sum_{i=1}^{k}\frac{1}{z_i}. T → ∞ lim inf Opt M , T Alg T ( M , M ) ≥ k M i = 1 ∑ k z i 1 .
It remains to minimize ∑ i 1 / z i \sum_i 1/z_i ∑ i 1/ z i over integers 1 ≤ z i ≤ M 1\le z_i\le M 1 ≤ z i ≤ M satisfying (15) . Since 1 / z 1/z 1/ z is decreasing and M + k − 1 ≤ k M M+k-1\le kM M + k − 1 ≤ k M , the minimum is attained when ∑ i z i = M + k − 1 \sum_i z_i=M+k-1 ∑ i z i = M + k − 1 . By convexity, in a minimizing choice the values z i z_i z i differ by at most one. Thus, such a choice has exactly s s s values equal to r + 1 r+1 r + 1 and k − s k-s k − s values equal to r r r , where M + k − 1 = k r + s M+k-1=kr+s M + k − 1 = k r + s and 0 ≤ s < k 0\le s<k 0 ≤ s < k . It follows that
∑ i = 1 k 1 z i ≥ s r + 1 + k − s r . \sum_{i=1}^{k}\frac{1}{z_i}\ge\frac{s}{r+1}+\frac{k-s}{r}. i = 1 ∑ k z i 1 ≥ r + 1 s + r k − s .
Hence,
lim inf T → ∞ Alg T ( M , M ) Opt M , T ≥ M k ( s r + 1 + k − s r ) = ρ M , k . \liminf_{T\to\infty}\frac{\operatorname{Alg}_{T}(M,M)}{\operatorname{Opt}_{M,T}} \ge\frac{M}{k}\left(\frac{s}{r+1}+\frac{k-s}{r}\right)=\rho_{M,k}. T → ∞ lim inf Opt M , T Alg T ( M , M ) ≥ k M ( r + 1 s + r k − s ) = ρ M , k .
This contradicts (13) and proves the claim. □
For k ≥ 2 k\ge2 k ≥ 2 , the lower bound can be matched by the following algorithm. In Phase I, sort all jobs in SPT order and partition this sequence into M M M consecutive bags, allowing empty bags, to minimize their total completion time when processed on separate unit-speed machines. In Phase II, choose a bag assignment whose cost is at most the uniform average over all assignments in which the numbers of bags per machine differ by at most one. Here, empty bags are counted, and the bags on each machine are processed in their order along the SPT sequence. We call this algorithm SPT-Cut.
Both phases can be implemented in polynomial time. For Phase I, a dynamic-programming state records a prefix of the SPT sequence and the number of bags. A transition chooses the beginning of the last bag, which may be empty. After precomputing the cost of every consecutive block of jobs, this gives a running time of O ( M n 2 ) O(Mn^2) O ( M n 2 ) .
For Phase II, fix balanced bag counts h 1 , … , h m h_1,\ldots,h_m h 1 , … , h m and consider a uniformly random assignment respecting these counts. By symmetry of the identical machines, its expected cost equals the average over all balanced assignments. We assign the bags successively, each time choosing a machine with a free bag position that minimizes the conditional expected final cost. Since the current conditional expectation is a weighted average over the possible choices, this step never increases it. The final assignment therefore has cost at most the initial average.
To compute these conditional expectations, observe that the contribution within each bag is fixed. For two bags B a , B b B_a, B_b B a , B b with a < b a < b a < b , assigning them to the same machine adds the contribution
w a b : = ( ∑ j ∈ B a p j ) ∣ B b ∣ . w_{ab} := \left(\sum_{j \in B_a} p_j\right)|B_b|. w ab := j ∈ B a ∑ p j ∣ B b ∣.
Suppose that R R R bags remain unassigned and machine i i i has d i d_i d i free bag positions. An unassigned bag shares a machine with a bag already assigned to machine i i i with probability d i / R d_i/R d i / R . Two unassigned bags share a machine with probability
∑ i = 1 m d i ( d i − 1 ) R ( R − 1 ) \frac{\sum_{i=1}^{m}d_i(d_i-1)}{R(R-1)} R ( R − 1 ) ∑ i = 1 m d i ( d i − 1 )
if R ≥ 2 R \ge2 R ≥ 2 .
Thus, each conditional expected cost can be computed by summing the fixed contributions within bags and the expected contributions between pairs of bags.
On one machine, processing the bags in their original order preserves the unrestricted SPT order and is therefore optimal. When all M M M machines are available, the chosen cuts minimize the cost among partitions into consecutive bags. For intermediate numbers of machines, averaging over balanced assignments bounds the additional delay caused by processing several bags on the same machine.
Theorem 9. For M M M , k ≥ 2 k \ge2 k ≥ 2 , algorithm SPT-Cut is ρ M , k \rho_{M,k} ρ M , k -robust in the non-adaptive model with M M M bags and an unknown number of identical machines, on instances with k k k distinct processing times.
Proof. Fix an instance and a revealed number m ∈ [ M ] m \in[M] m ∈ [ M ] of machines. Let J i J_i J i contain k i k_i k i jobs of processing time ℓ i \ell_i ℓ i , where ℓ 1 < ⋯ < ℓ k \ell_1 < \cdots< \ell_k ℓ 1 < ⋯ < ℓ k , and put
c : = ρ M , k M . c := \frac{\rho_{M,k}}{M}. c := M ρ M , k . By the bounds on ρ M , k \rho_{M,k} ρ M , k , we have 0 < c ≤ 1 0 < c \le1 0 < c ≤ 1 .
We distinguish the jobs’ own processing times from the delays caused by other jobs. More precisely, let
P : = ∑ i = 1 k ℓ i k i , K : = ∑ i = 1 k ℓ i ( k i 2 ) + ∑ i < j ℓ i k i k j . P := \sum_{i=1}^{k} \ell_i k_i,\qquad K := \sum_{i=1}^{k} \ell_i \binom{k_i}{2}+\sum_{i<j}\ell_i k_i k_j. P := i = 1 ∑ k ℓ i k i , K := i = 1 ∑ k ℓ i ( 2 k i ) + i < j ∑ ℓ i k i k j . Thus, the total completion time of the one-machine SPT schedule is P + K P+K P + K . Each pair of jobs contributes the processing time of its shorter job to K K K .
Let C C C denote the total completion time when each bag constructed in Phase I is processed on a separate unit-speed machine. We first show that
C ≤ P + c K . (17) C \le P+cK. \tag*{(17)} C ≤ P + cK . (17) For this, we construct a random comparison partition of the SPT sequence into M M M consecutive bags. Splitting class J i J_i J i into z i z_i z i parts uses z i − 1 z_i-1 z i − 1 cuts. Thus, the M − 1 M-1 M − 1 available cuts give the same sum ∑ i z i = M + k − 1 \sum_i z_i=M+k-1 ∑ i z i = M + k − 1 , the same total that appears in the lower-bound minimization. We distribute these parts as evenly as possible among the classes.
Recall that M + k − 1 = k r + s M+k-1=kr+s M + k − 1 = k r + s , where 0 ≤ s < k 0\le s<k 0 ≤ s < k . Choose s s s classes uniformly at random and set z i = r + 1 z_i=r+1 z i = r + 1 for these classes and z i = r z_i=r z i = r for the others. Then
∑ i = 1 k z i = M + k − 1 , E [ 1 z i ] = 1 k ( s r + 1 + k − s r ) = c \sum_{i=1}^{k}z_i=M+k-1,\qquad\mathbb{E}\left[\frac{1}{z_i}\right]=\frac{1}{k}\left(\frac{s}{r+1}+\frac{k-s}{r}\right)=c i = 1 ∑ k z i = M + k − 1 , E [ z i 1 ] = k 1 ( r + 1 s + r k − s ) = c for every i ∈ [ k ] i\in[k] i ∈ [ k ] .
Split each class J i J_i J i into z i z_i z i parts whose sizes differ by at most one, and order these parts uniformly at random within the class. Place a cut between consecutive parts of the same class. This gives $\sum_i(z_i-1)=M-1
cuts and hence M M M consecutive bags. Observe that parts and bags may be empty. In particular, coinciding cuts create empty bags.
Consider first the contribution of pairs within a class J i J_i J i . If its part sizes are a 1 , … , a z i a_1,\ldots,a_{z_i} a 1 , … , a z i , then
∑ h = 1 z i ( a h 2 ) ≤ k i 2 ( k i z i − 1 ) ≤ 1 z i ( k i 2 ) . \sum_{h=1}^{z_i}\binom{a_h}{2}\le\frac{k_i}{2}\left(\frac{k_i}{z_i}-1\right)\le\frac{1}{z_i}\binom{k_i}{2}. h = 1 ∑ z i ( 2 a h ) ≤ 2 k i ( z i k i − 1 ) ≤ z i 1 ( 2 k i ) .
Thus, the expected waiting-time contribution within this class is at most c ℓ i ( k i 2 ) c\ell_i\binom{k_i}{2} c ℓ i ( 2 k i ) .
Now consider two classes J i J_i J i and J j J_j J j with i < j i<j i < j . Only the last part of J i J_i J i can share a bag with jobs of J j J_j J j . Conditional on z i z_i z i , this part has expected size k i / z i k_i/z_i k i / z i . Hence, the expected contribution between these classes is at most
E [ ℓ i k i k j z i ] = c ℓ i k i k j . \mathbb{E}\left[\frac{\ell_i k_i k_j}{z_i}\right]=c\ell_i k_i k_j. E [ z i ℓ i k i k j ] = c ℓ i k i k j .
The contribution P P P of the jobs’ own processing times remains unchanged. Summing over all classes and pairs of classes, the expected cost of the comparison partition is at most P + c K P+cK P + cK . Since Phase I chooses a minimum-cost partition, (17) follows.
We next consider Phase II. Since the bags are consecutive parts of the SPT sequence, processing them in their original order gives an SPT schedule on each machine. Contributions within bags are always paid, while a contribution between two different bags is paid precisely when these bags share a machine. We aim to bound the probability that two fixed bags share a machine under a uniformly random balanced assignment.
Let β \beta β be the probability that two fixed distinct bags are assigned to the same machine. If the machine bag counts are h 1 , … , h m h_1,\ldots,h_m h 1 , … , h m , then
β = ∑ a = 1 m h a ( h a − 1 ) M ( M − 1 ) ≤ ⌈ M / m ⌉ ( M − m ) M ( M − 1 ) ≤ 2 ( M − m ) m ( M − 1 ) . \beta=\frac{\sum_{a=1}^{m}h_a(h_a-1)}{M(M-1)}
\le\frac{\lceil M/m\rceil(M-m)}{M(M-1)}
\le\frac{2(M-m)}{m(M-1)}. β = M ( M − 1 ) ∑ a = 1 m h a ( h a − 1 ) ≤ M ( M − 1 ) ⌈ M / m ⌉ ( M − m ) ≤ m ( M − 1 ) 2 ( M − m ) .
Here, we used 1 ≤ h a ≤ ⌈ M / m ⌉ 1\le h_a\le\lceil M/m\rceil 1 ≤ h a ≤ ⌈ M / m ⌉ , ∑ a ( h a − 1 ) = M − m \sum_a(h_a-1)=M-m ∑ a ( h a − 1 ) = M − m , and ⌈ M / m ⌉ ≤ 2 M / m \lceil M/m\rceil\le2M/m ⌈ M / m ⌉ ≤ 2 M / m .
The algorithm chooses an assignment whose cost is at most this average. Therefore,
Alg ( m , M ) ≤ C + β ( P + K − C ) ≤ P + ( c + ( 1 − c ) β ) K , (18) \begin{aligned}
\operatorname{Alg}(m,M)&\le C+\beta(P+K-C)\\
&\le P+\bigl(c+(1-c)\beta\bigr)K, \tag*{(18)}
\end{aligned} Alg ( m , M ) ≤ C + β ( P + K − C ) ≤ P + ( c + ( 1 − c ) β ) K , (18)
where the second inequality follows from (17) and β ≤ 1 \beta\le1 β ≤ 1 .
It remains to compare this bound with the optimum. Let ℓ 0 = 0 \ell_0=0 ℓ 0 = 0 and N i : = ∑ j = i k k j N_i:=\sum_{j=i}^{k}k_j N i := ∑ j = i k k j . Using the layer decomposition from the proof of Lemma 1, we obtain
P = ∑ i = 1 k ( ℓ i − ℓ i − 1 ) N i , K = ∑ i = 1 k ( ℓ i − ℓ i − 1 ) ( N i 2 ) . P=\sum_{i=1}^{k}(\ell_i-\ell_{i-1})N_i,\qquad
K=\sum_{i=1}^{k}(\ell_i-\ell_{i-1})\binom{N_i}{2}. P = i = 1 ∑ k ( ℓ i − ℓ i − 1 ) N i , K = i = 1 ∑ k ( ℓ i − ℓ i − 1 ) ( 2 N i ) .
In each layer, the machine job counts sum to N i N_i N i . By Cauchy–Schwarz, their squared counts sum to at least N i 2 / m N_i^2/m N i 2 / m . Consequently,
Opt m ≥ ∑ i = 1 k ( ℓ i − ℓ i − 1 ) ( N i 2 2 m + N i 2 ) = K m + m + 1 2 m P . (19) \begin{aligned}
\operatorname{Opt}_m&\ge\sum_{i=1}^{k}(\ell_i-\ell_{i-1})\left(\frac{N_i^2}{2m}+\frac{N_i}{2}\right)\\
&=\frac{K}{m}+\frac{m+1}{2m}P. \tag*{(19)}
\end{aligned} Opt m ≥ i = 1 ∑ k ( ℓ i − ℓ i − 1 ) ( 2 m N i 2 + 2 N i ) = m K + 2 m m + 1 P . (19)
Finally, Cauchy–Schwarz and k ≥ 2 k\ge2 k ≥ 2 imply
c ≥ k M + k − 1 ≥ 2 M + 1 . c\ge\frac{k}{M+k-1}\ge\frac{2}{M+1}. c ≥ M + k − 1 k ≥ M + 1 2 .
In particular, 2 ( 1 − c ) / ( M − 1 ) ≤ c 2(1-c)/(M-1) \le c 2 ( 1 − c ) / ( M − 1 ) ≤ c , and hence
c + ( 1 − c ) β ≤ c + 2 ( 1 − c ) ( M − m ) m ( M − 1 ) ≤ c + c ( M − m ) m = ρ M , k m . c+(1-c)\beta\le c+\frac{2(1-c)(M-m)}{m(M-1)}
\le c+\frac{c(M-m)}{m}=\frac{\rho_{M,k}}{m}. c + ( 1 − c ) β ≤ c + m ( M − 1 ) 2 ( 1 − c ) ( M − m ) ≤ c + m c ( M − m ) = m ρ M , k .
Moreover, since m ≤ M m \le M m ≤ M ,
ρ M , k = M c ≥ 2 M M + 1 ≥ 2 m m + 1 . \rho_{M,k}=Mc\ge\frac{2M}{M+1}\ge\frac{2m}{m+1}. ρ M , k = M c ≥ M + 1 2 M ≥ m + 1 2 m .
Combining these inequalities with (18) and (19) , we obtain
Alg ( m , M ) ≤ P + ρ M , k m K ≤ ρ M , k ( K m + m + 1 2 m P ) ≤ ρ M , k Opt m . \operatorname{Alg}(m,M)\le P+\frac{\rho_{M,k}}{m}K
\le\rho_{M,k}\left(\frac{K}{m}+\frac{m+1}{2m}P\right)
\le\rho_{M,k}\operatorname{Opt}_m. Alg ( m , M ) ≤ P + m ρ M , k K ≤ ρ M , k ( m K + 2 m m + 1 P ) ≤ ρ M , k Opt m .
This holds for every m ∈ [ M ] m \in[M] m ∈ [ M ] and proves the claim.
For k ≥ M k \ge M k ≥ M , we have r = 1 r=1 r = 1 and s = M − 1 s=M-1 s = M − 1 , so
ρ M , k = M − M ( M − 1 ) 2 k . \rho_{M,k}=M-\frac{M(M-1)}{2k}. ρ M , k = M − 2 k M ( M − 1 ) .
Thus, for fixed M M M , the optimal robustness factor converges to M M M as k k k increases. Conversely, for fixed k ≥ 2 k \ge2 k ≥ 2 , it approaches k k k as M M M increases. Without restricting the number of distinct processing times, the optimal robustness factor for M M M bags is therefore M M M . This is attained even by the trivial algorithm that places all jobs in SPT order into a single bag.
For k = 1 k=1 k = 1 , the formula gives only the trivial lower bound ρ M , 1 = 1 \rho_{M,1}=1 ρ M , 1 = 1 . All jobs have the same processing time, so requiring bags to be processed contiguously does not change the cost of any bag assignment. Thus, this case coincides with the bricks setting considered in § 3 .
A stronger adversary: failures after job assignment
Liu, Zhang, and Zhao [10 ] study machine failures for makespan minimization under a weak and a strong adversary. In their model, jobs are assigned directly to machines in Phase I, and up to k k k machines may fail afterwards. A strong adversary determines which machines fail, whereas a weak adversary determines only their number, and the algorithm chooses which machines fail. Jobs on surviving machines cannot be reassigned, while jobs from failed machines may be reassigned individually. We adopt this model for total completion time, where the jobs on each machine may be reordered in Phase II, and allow up to M − 1 M-1 M − 1 failures. For general speeds, the adversary chooses the speed of each machine after Phase I, and only jobs on machines of speed zero may be reassigned.
We first show that extending the strong-adversary model to speed-robust scheduling with general machine speeds leads to unbounded robustness, already for M = 2 M=2 M = 2 .
Theorem 10. For general speeds, no deterministic algorithm for minimizing the total completion time of sand under a strong adversary achieves a bounded robustness factor.
Proof. Choose M = 2 M=2 M = 2 and let y 1 ≥ y 2 ≥ 0 y_1 \ge y_2 \ge0 y 1 ≥ y 2 ≥ 0 with y 1 + y 2 = 1 y_1+y_2=1 y 1 + y 2 = 1 denote the machine loads after Phase I. The adversary chooses speeds s 1 = ε s_1=\varepsilon s 1 = ε and s 2 = 1 − ε s_2=1-\varepsilon s 2 = 1 − ε for some ε ∈ ( 0 , 1 ) \varepsilon\in(0,1) ε ∈ ( 0 , 1 ) . Since both speeds are positive, no machine fails and no reassignment is allowed. By § 2 , we have ALG ( s ) = ( y 1 2 / s 1 + y 2 2 / s 2 ) / 2 \operatorname{ALG}(\boldsymbol{s})=(y_1^2/s_1+y_2^2/s_2)/2 ALG ( s ) = ( y 1 2 / s 1 + y 2 2 / s 2 ) /2 and, since s 1 + s 2 = 1 s_1+s_2=1 s 1 + s 2 = 1 , OPT ( s ) = 1 / 2 \operatorname{OPT}(\boldsymbol{s})=1/2 OPT ( s ) = 1/2 . Moreover, y 1 ≥ 1 / 2 y_1\ge1/2 y 1 ≥ 1/2 , and thus the robustness ratio satisfies
ALG ( s ) OPT ( s ) = y 1 2 s 1 + y 2 2 s 2 ≥ y 1 2 ε ≥ 1 4 ε . \frac{\operatorname{ALG}(\boldsymbol{s})}{\operatorname{OPT}(\boldsymbol{s})}=\frac{y_1^2}{s_1}+\frac{y_2^2}{s_2}\ge\frac{y_1^2}{\varepsilon}\ge\frac{1}{4\varepsilon}. OPT ( s ) ALG ( s ) = s 1 y 1 2 + s 2 y 2 2 ≥ ε y 1 2 ≥ 4 ε 1 .
As ε → 0 \varepsilon\to0 ε → 0 , the ratio becomes arbitrarily large, proving the claim. □ \square □
We therefore restrict attention to machine speeds in { 0 , 1 } \{0,1\} { 0 , 1 } , for which an optimal algorithm exists.
Theorem 11. For speeds in { 0 , 1 } \{0,1\} { 0 , 1 } , there exists an optimal deterministic algorithm for minimizing the total completion time of bricks, rocks, and sand under a strong adversary.
Proof. For sand, distribute the volume equally among the M M M machines in Phase I. If m m m machines survive, distribute the volume of failed machines equally among them. Every surviving machine then has load 1 / m 1/m 1/ m , which is optimal.
For bricks and rocks, index the jobs such that p 1 ≤ … ≤ p n p_1\le\ldots\le p_n p 1 ≤ … ≤ p n . In Phase I, assign the jobs 1 , … , n 1,\ldots,n 1 , … , n cyclically to the M M M machines. In Phase II, fix an arbitrary set of surviving machines, and let m ≤ M m\le M m ≤ M denote its size. For i = 1 , … , ⌈ n / m ⌉ i=1,\ldots,\lceil n/m\rceil i = 1 , … , ⌈ n / m ⌉ , let G i G_i G i be the set of jobs j j j with ⌈ ( n − j + 1 ) / m ⌉ = i \lceil(n-j+1)/m\rceil=i ⌈( n − j + 1 ) / m ⌉ = i , i.e., the i i i -th group of m m m jobs in non-increasing order of size (the last group may be smaller).
Since two jobs assigned to the same machine in Phase I have indices differing by at least M M M , and each group consists of at most m ≤ M m\le M m ≤ M consecutive jobs, no machine contains two jobs from the same group. For each group G i G_i G i , consider the jobs of the failed machines. Assign each of these jobs to an available machine that does not yet contain a job from G i G_i G i . This is always possible since ∣ G i ∣ ≤ m |G_i|\le m ∣ G i ∣ ≤ m and the jobs already assigned to available machines occupy distinct machines. Thus, each full group has exactly one job on each available machine, while the last group has at most one job per machine. On each machine, process the jobs in SPT order and, among jobs of equal size, the job from the group with larger index first.
It remains to show that the resulting schedule is optimal. An optimal schedule on m m m machines processes each machine in SPT order. In such a schedule, a job j j j contributes a j p j a_jp_j a j p j to the objective, where a j a_j a j is the number of jobs processed no earlier than job j j j on its machine, including j j j itself.
Since each coefficient occurs at most once per machine, it occurs at most m m m times in total. By the rearrangement inequality, the objective is therefore bounded from below by assigning coefficient 1 to the m m m largest jobs, coefficient 2 to the next m m m largest jobs, and so on. This yields
OPT m ≥ ∑ j = 1 n ⌈ n − j + 1 m ⌉ p j . \operatorname{OPT}_m\ge\sum_{j=1}^{n}\left\lceil\frac{n-j+1}{m}\right\rceil p_j. OPT m ≥ j = 1 ∑ n ⌈ m n − j + 1 ⌉ p j .
In our schedule, each job in G i G_i G i is followed by exactly i − 1 i-1 i − 1 jobs on its machine, one from each preceding group. Hence, its coefficient is i i i . Consequently,
ALG ( m , M ) = ∑ i = 1 ⌈ n / m ⌉ i ∑ j ∈ G i p j = ∑ j = 1 n ⌈ n − j + 1 m ⌉ p j ≤ OPT m . \begin{aligned}
\operatorname{ALG}(m,M)&=\sum_{i=1}^{\lceil n/m\rceil}i\sum_{j\in G_i}p_j\\
&=\sum_{j=1}^{n}\left\lceil\frac{n-j+1}{m}\right\rceil p_j\le\operatorname{OPT}_m.
\end{aligned} ALG ( m , M ) = i = 1 ∑ ⌈ n / m ⌉ i j ∈ G i ∑ p j = j = 1 ∑ n ⌈ m n − j + 1 ⌉ p j ≤ OPT m .
Since ALG ( m , M ) ≥ OPT m \operatorname{ALG}(m,M)\ge\operatorname{OPT}_m ALG ( m , M ) ≥ OPT m holds trivially, the algorithm is optimal. □ \square □
Finally, we consider an indivisible strong adversary . Here, the adversary decides which machines fail, and all jobs from the same failed machine must be reassigned together to a single surviving machine. For general machine speeds, the unboundedness result carries over to the indivisible strong adversary, since the adversary may also choose not to fail any machine. We now establish an upper bound for sand using the algorithm that distributes the volume equally among all machines. Afterward, we derive lower bounds for bricks, rocks, and sand.
Theorem 12. For speeds in { 0 , 1 } \{0,1\} { 0 , 1 } , the algorithm that distributes sand equally among the machines in Phase I and optimally reassigns the volumes of failed machines in Phase II is 9/8-robust for minimizing the total completion time under an indivisible strong adversary. This bound is tight for the algorithm.
Proof. Let M M M be the number of initial machines and let m ≤ M m \le M m ≤ M machines remain available. In Phase I, each machine receives volume 1 / M 1/M 1/ M . Since the volumes of failed machines are reassigned as a whole, every surviving machine ends up with load k i / M k_i/M k i / M , where k i ≥ 1 k_i \ge1 k i ≥ 1 is the number of bags it holds and ∑ i = 1 m k i = M \sum_{i=1}^{m} k_i=M ∑ i = 1 m k i = M . As ∑ i k i 2 \sum_i k_i^2 ∑ i k i 2 is minimized by balanced vectors, an optimal reassignment yields k i ∈ { ⌊ M / m ⌋ , ⌈ M / m ⌉ } k_i \in\{\lfloor M/m \rfloor,\lceil M/m\rceil\} k i ∈ {⌊ M / m ⌋ , ⌈ M / m ⌉} .
Write M = q m + r M=qm+r M = q m + r with 0 ≤ r < m 0 \le r<m 0 ≤ r < m . Thus, m − r m-r m − r machines have final load q / M q/M q / M , while r r r machines have load ( q + 1 ) / M (q+1)/M ( q + 1 ) / M . Since Opt m = 1 / ( 2 m ) \operatorname{Opt}_m=1/(2m) Opt m = 1/ ( 2 m ) , the robustness ratio is
R ( m ) = m M 2 ( ( m − r ) q 2 + r ( q + 1 ) 2 ) = 1 + r ( m − r ) M 2 . R(m)=\frac{m}{M^2}\left((m-r)q^2+r(q+1)^2\right)=1+\frac{r(m-r)}{M^2}. R ( m ) = M 2 m ( ( m − r ) q 2 + r ( q + 1 ) 2 ) = 1 + M 2 r ( m − r ) . Since q ≥ 1 q \ge1 q ≥ 1 , we have M ≥ m + r M \ge m+r M ≥ m + r . Moreover, ( m + r ) 2 − 8 r ( m − r ) = ( m − 3 r ) 2 ≥ 0 (m+r)^2-8r(m-r)=(m-3r)^2\ge0 ( m + r ) 2 − 8 r ( m − r ) = ( m − 3 r ) 2 ≥ 0 , and hence
R ( m ) ≤ 1 + r ( m − r ) ( m + r ) 2 ≤ 1 + 1 8 = 9 8 . R(m)\le1+\frac{r(m-r)}{(m+r)^2}\le1+\frac{1}{8}=\frac{9}{8}. R ( m ) ≤ 1 + ( m + r ) 2 r ( m − r ) ≤ 1 + 8 1 = 8 9 . The bound is attained for M = 4 M=4 M = 4 and m = 3 m=3 m = 3 , where the final machine loads are ( 2 , 1 , 1 ) / 4 (2,1,1)/4 ( 2 , 1 , 1 ) /4 and R ( m ) = 9 / 8 R(m)=9/8 R ( m ) = 9/8 .
Theorem 13. For speeds in { 0 , 1 } \{0,1\} { 0 , 1 } , no deterministic algorithm for minimizing the total completion time under an indivisible strong adversary achieves a robustness factor smaller than 7/6 for bricks or rocks, or ( 60 − 6 2 ) / 49 > 1.0513 (60-6\sqrt{2})/49>1.0513 ( 60 − 6 2 ) /49 > 1.0513 for sand.
Proof. For bricks, consider an instance with four unit-size jobs and three machines. If at least one machine receives no job, the adversary keeps all three machines available. The algorithm incurs a cost of at least 6, whereas the optimum has cost 5, yielding a ratio of at least 6 / 5 > 7 / 6 6/5>7/6 6/5 > 7/6 .
Otherwise, two machines receive one job, while one machine receives two jobs. The adversary lets the machine with two jobs fail. Hence, the machine loads are ( 3 , 1 ) (3,1) ( 3 , 1 ) with cost 7, while the optimum ( 2 , 2 ) (2,2) ( 2 , 2 ) has cost 6. Thus, the ratio is 7 / 6 7/6 7/6 . Since bricks are a special case of rocks, the same lower bound applies to rocks.
For sand, consider an instance with three machines. Let a ≥ b ≥ c ≥ 0 a\ge b\ge c\ge0 a ≥ b ≥ c ≥ 0 denote their volumes on the three machines with a + b + c = 1 a+b+c=1 a + b + c = 1 . The adversary considers two scenarios. First, if all machines remain available, no reassignment is allowed. Using a + c = 1 − b a+c=1-b a + c = 1 − b , we obtain a lower bound on the ratio solely in terms of the median load b b b :
R ( 3 ) = 3 ( a 2 + b 2 + c 2 ) = 1 + 18 ( b − 1 3 ) 2 + 6 ( a − b ) ( b − c ) R(3)=3(a^2+b^2+c^2)=1+18\left(b-\frac{1}{3}\right)^2+6(a-b)(b-c) R ( 3 ) = 3 ( a 2 + b 2 + c 2 ) = 1 + 18 ( b − 3 1 ) 2 + 6 ( a − b ) ( b − c ) ≥ 1 + 18 ( b − 1 3 ) 2 . \ge1+18\left(b-\frac{1}{3}\right)^2. ≥ 1 + 18 ( b − 3 1 ) 2 . Second, the adversary lets the machine with load a a a fail. Since its load must be reassigned as a whole, assigning it to the less loaded surviving machine is optimal. Thus,
R ( 2 ) ≥ 2 ( b 2 + ( a + c ) 2 ) = 1 + ( 1 − 2 b ) 2 . R(2)\ge2\left(b^2+(a+c)^2\right)=1+(1-2b)^2. R ( 2 ) ≥ 2 ( b 2 + ( a + c ) 2 ) = 1 + ( 1 − 2 b ) 2 .
Let β = 4 + 2 14 \beta= \frac{4+\sqrt{2}}{14} β = 14 4 + 2 and ρ ⋆ = 60 − 6 2 49 \rho^{\star} = \frac{60-6\sqrt{2}}{49} ρ ⋆ = 49 60 − 6 2 . If b ≤ β b \le\beta b ≤ β , then R ( 2 ) ≥ 1 + ( 1 − 2 β ) 2 = ρ ⋆ R(2) \ge1 + (1 - 2\beta)^2 = \rho^{\star} R ( 2 ) ≥ 1 + ( 1 − 2 β ) 2 = ρ ⋆ . Otherwise, we have b > β > 1 / 3 b > \beta> 1/3 b > β > 1/3 , implying R ( 3 ) ≥ 1 + 18 ( β − 1 3 ) 2 = ρ ⋆ R(3) \ge1 + 18\left(\beta- \frac{1}{3}\right)^2 = \rho^{\star} R ( 3 ) ≥ 1 + 18 ( β − 3 1 ) 2 = ρ ⋆ .
Thus, the adversary can always enforce a robustness ratio of at least ρ ⋆ \rho^{\star} ρ ⋆ . For M = 3 M = 3 M = 3 , this bound is best possible: consider the initial distribution ( a , b , c ) = ( β , β , 1 − 2 β ) (a,b,c) = (\beta,\beta,1 - 2\beta) ( a , b , c ) = ( β , β , 1 − 2 β ) . If all machines remain available, then R ( 3 ) = ρ ⋆ R(3) = \rho^{\star} R ( 3 ) = ρ ⋆ . If exactly one machine fails, an optimal reassignment yields loads ( β , 1 − β ) (\beta,1 - \beta) ( β , 1 − β ) , giving R ( 2 ) = 1 + ( 1 − 2 β ) 2 = ρ ⋆ R(2) = 1 + (1 - 2\beta)^2 = \rho^{\star} R ( 2 ) = 1 + ( 1 − 2 β ) 2 = ρ ⋆ . If only one machine survives, the ratio is one. Hence, this distribution achieves worst-case robustness ρ ⋆ \rho^{\star} ρ ⋆ . □ \square □