betaFeedback

WorksComputer Science

Speed-Robust Scheduling for Total Completion Time

Abstract

We study two-stage speed-robust scheduling for minimizing total completion time. Jobs must be partitioned into MM bags before an adversary reveals the speeds of at most MM machines. Each bag is then assigned to one available machine, and the jobs on each machine may be processed in any order independent of the bags. We compare with an optimal schedule that knows the speeds in advance and assigns jobs individually. This model has been studied for makespan minimization. We initiate its study for total completion time, as suggested by Stein and Zhong (TALG 2020). For an unknown number of identical machines, we show that the optimal deterministic robustness factor is exactly~13/1213/12, both for unit-size jobs and for arbitrary processing times. For infinitesimally small jobs, the factor lies between 31/30≈1.033331/30\approx1.0333 and 28/27≈1.037028/27\approx1.0370, well below the optimal makespan factor of about 1.20711.2071. General speeds make the problem strictly harder: no deterministic algorithm is better than 1.26691.2669-robust, already for infinitesimally small jobs. We give a 25/1625/16-robust algorithm for arbitrary processing times and improve the guarantee to 1681/1152≈1.45921681/1152\approx1.4592 for infinitesimally small jobs. Our main tools are a layer decomposition that extends guarantees from unit-size jobs to arbitrary processing times when one assignment satisfies them for every prefix in non-increasing processing-time order, and a threshold analysis of the bag counts produced by greedy assignment rules.

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 MM groups, called bags. An adversary then reveals either a number 1≤m≤M1 \le m \le M of identical machines (*speeds in {0,1}\{0,1\}) or a nonnegative speed for each of the MM 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)-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 and 4/34/3, respectively. For general speeds, they determined the optimal factor for sand, which tends to e/(e−1)≈1.5820e/(e-1) \approx1.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 MM of bags: upper bounds hold for every MM, while lower bounds rule out smaller guarantees valid for every MM. All upper bounds are attained by deterministic polynomial-time algorithms and lower bounds assume deterministic algorithms. Table 1 summarizes the bounds.

JobsSpeeds in {0,1}\{0,1\} Lower boundSpeeds in {0,1}\{0,1\} Upper boundGeneral speeds Lower boundGeneral speeds Upper bound
Sand31/30 ≈ 1.0333<br>Theorem 228/27 ≈ 1.0370<br>Theorem 11.2669<br>Theorem 51681/1152 ≈ 1.4592<br>Theorem 7
Bricks and rocks13/12 ≈ 1.0833<br>Theorems 3 and 41.2669<br>Theorem 525/16 = 1.5625<br>Theorem 6

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\} 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=12M = 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\}-speeds, and by Observation 2 the bound carries over to bricks and rocks. The adversary uses one fast machine and M−1M - 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 MM 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/1625/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.45921681/1152 \approx1.4592 (Theorem 7), clearly below the makespan benchmark of 1.58201.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 MM bags is better than MM-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 MM 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 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 nn jobs with processing times pj>0p_j > 0, j∈[n]j \in[n], and the number MM 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 B1,…,BMB_1,\ldots,B_M, some of which may be empty. Then, an adversary reveals a speed vector s∈R≥0M∖{0}\boldsymbol{s}\in\mathbb{R}_{\ge0}^{M}\setminus\{\boldsymbol{0}\}: a job jj on a machine of speed si>0s_i>0 takes pj/sip_j/s_i time units, and a machine of speed zero is unavailable. Let m:=∣{i∈[M]:si>0}∣m:=|\{i\in[M]:s_i>0\}|, and relabel the machines so that the available machines are indexed by 1,…,m1,\ldots,m. We call the unrestricted choice of s\boldsymbol{s} the setting of general speeds. For speeds in {0,1}\{0,1\}, the adversary chooses only the number m∈[M]m\in[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] where several bags may share a machine. Machine ii then processes the jobs Ji:=⋃r:π(r)=iBrJ_i:=\bigcup_{r:\pi(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]Cj\sum_{j\in[n]}C_j, where CjC_j is the completion time of job jj. For an instance II and a speed vector s\boldsymbol{s}, let Alg⁡(I,s)\operatorname{Alg}(I,\boldsymbol{s}) denote the cost of the algorithm’s schedule, and let Opt⁡(I,s)\operatorname{Opt}(I,\boldsymbol{s}) denote the minimum total completion time of a schedule that knows s\boldsymbol{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}) for every instance II and every feasible speed vector s\boldsymbol{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 MM of bags, we define the corresponding robustness factors by restricting to instances with MM bags. We omit the instance II from the notation whenever it is clear.

Sand, bricks, and rocks For sand, we normalize the total volume to one. Let brb_r denote the volume of bag BrB_r and yi:=∑r:π(r)=ibry_i:=\sum_{r:\pi(r)=i}b_r the volume assigned to machine ii. 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. We therefore multiply algorithmic and optimal costs by δ\delta, preserving their ratio and obtaining a finite limit. If machine ii receives kik_i jobs of total volume yi=kiδy_i=k_i\delta, its scaled total completion time is

δ∑h=1kihδsi=yi2+δyi2si⟶yi22sias δ→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.

We therefore use 12∑iyi2/si\frac{1}{2}\sum_i y_i^2/s_i as the objective for sand. Write S:=∑i=1msiS:=\sum_{i=1}^{m}s_i. By Cauchy–Schwarz, ∑i=1myi2/si≥(∑i=1myi)2/S=1/S\sum_{i=1}^{m}y_i^2/s_i\geq(\sum_{i=1}^{m}y_i)^2/S=1/S, with equality for yi=si/Sy_i=s_i/S. Hence, the unrestricted optimum for sand has cost 1/(2S)1/(2S), and the ratio between the cost of an assignment with loads yiy_i and this optimum is

R(s):=S∑i=1myi2si.R(\boldsymbol{s}):=S\sum_{i=1}^{m}\frac{y_i^2}{s_i}.

For speeds in {0,1}\{0,1\}, we write R(m):=m∑i=1myi2R(m):=m\sum_{i=1}^{m}y_i^2 for this ratio. For bricks, a machine of speed sis_i processing kk unit-size jobs contributes F(k)/siF(k)/s_i, where F(k):=k(k+1)/2F(k):=k(k+1)/2. For speeds in {0,1}\{0,1\}, the linear part of the total cost is always n/2n/2; for general speeds, it depends on the assignment.

Transferring guarantees Write p1≥⋯≥pnp_1\geq\cdots\geq p_n and set pn+1=0p_{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 pr−pr+1p_r-p_{r+1} for the prefix 1,…,r1,\ldots,r. Thus, a guarantee for bricks transfers to rocks if the same assignment satisfies it for every prefix.

Lemma 1. Fix an instance II with p1≥⋯≥pnp_1\geq\cdots\geq p_n and speeds s\boldsymbol{s}. Consider an algorithm’s assignment AA on (I,s)(I,\boldsymbol{s}). Suppose that, for every r∈[n]r\in[n], restricting AA to the jobs 1,…,r1,\ldots,r and setting their processing times to one gives a schedule of cost at most α\alpha times the unrestricted optimum for rr unit-size jobs and speeds s\boldsymbol{s}. Then Alg⁡(I,s)≤αOpt⁡(I,s)\operatorname{Alg}(I,\boldsymbol{s})\leq\alpha\operatorname{Opt}(I,\boldsymbol{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\}

We first consider speeds in {0,1}\{0,1\}, where the adversary only chooses the number m≤Mm \le M of available machines, all running at unit speed. Since SPT is optimal for m=1m = 1, and assigning jobs cyclically in non-increasing order of size to the bags is optimal for M=2M = 2, the challenge arises for M≥3M \ge3: the bags should be nearly balanced for m=Mm = 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/2728/27, and no algorithm achieves a factor smaller than 31/3031/30 (Theorems 1 and 2).

For bricks and rocks, we give a 13/1213/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=1Mbi=1\sum_{i=1}^{M} b_i = 1, and denote the resulting machine loads by y1,…,ymy_1,\ldots,y_m. By § 2, the ratio of a bag assignment on mm machines is R(m):=m∑i=1myi2R(m) := m\sum_{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)/M2≤9/8R(m) = 1 + r(m-r)/M^2 \le9/8, where M=qm+rM = qm + r with 0≤r<m0 \le r < m. This is tight for M=4M = 4 and $m = 3 (Observation 5 in App. § 7.§ 1).

For M/2<m<MM/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/(3M)2/(3M) to 4/(3M)4/(3M).

Theorem 1. For sand and speeds in {0,1}\{0,1\}, the linear-profile algorithm has an asymptotically tight robustness factor of 28/27≈1.037028/27 \approx1.0370.

References

  1. [1]Balkanski, E., Ou, T., Stein, C., Wei, H.T.: Scheduling with speed predictions. Theory Comput. Syst. 69(1), 16 (2025). https://doi.org/10.1007/S00224-024-10200-7
  2. [2]Bruno, J.L., Coffman, Jr., E.G., Sethi, R.: Scheduling independent tasks to reduce mean finishing time. Commun. ACM 17(7), 382–387 (1974). https://doi.org/10.1145/361011.361064
  3. [3]Buchem, M., Eberle, F., Kasuya Rosado, H.K., Schewior, K., Wiese, A.: Scheduling on a stochastic number of machines. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). pp. 14:1–14:15 (2024). https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2024.14
  4. [4]Eberle, F., Hoeksma, R., Megow, N., Nölke, L., Schewior, K., Simon, B.: Speed-robust scheduling: sand, bricks, and rocks. Math. Program. 197(2), 1009–1048 (2023). https://doi.org/10.1007/s10107-022-01829-0
  5. [5]Epstein, L.: Online speed-robust scheduling. Discrete Optim. 61, 100954 (2026). https://doi.org/10.1016/J.DISOPT.2026.100954
  6. [6]Epstein, L.: Variants and objectives for ordinal scheduling. Central Eur. J. Oper. Res. 34(3), 951–986 (2026). https://doi.org/10.1007/s10100-025-00698-x
  7. [7]Epstein, L., Levin, A.: Efficient approximation schemes for scheduling on a stochastic number of machines. In: 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). pp. 31:1–31:18 (2025). https://doi.org/10.4230/LIPIcs.STACS.2025.31
  8. [8]Epstein, L., Levin, A., Marchetti-Spaccamela, A., Megow, N., Mestre, J., Skutella, M., Stougie, L.: Universal sequencing on an unreliable machine. SIAM J. Comput. 41(3), 565–586 (2012). https://doi.org/10.1137/110842210
  9. [9]Horn, W.A.: Technical note—minimizing average flow time with parallel machines. Oper. Res. 21(3), 846–847 (1973). https://doi.org/10.1287/opre.21.3.846
  10. [10]Liu, Z., Zhang, G., Zhao, Y.: Robust scheduling against machine failures. In: Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence (IJCAI-26). pp. 6175–6182 (2026). https://doi.org/10.24963/ijcai.2026/687
  11. [11]Minaík, J., Sgall, J.: Speed-robust scheduling revisited. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). pp. 8:1–8:20 (2024). https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2024.8
  12. [12]Smith, W.E.: Various optimizers for single-stage production. Nav. Res. Logist. Q. 3(1–2), 59–66 (1956). https://doi.org/10.1002/nav.3800030106
  13. [13]Stein, C., Zhong, M.: Scheduling when you do not know the number of machines. ACM Trans. Algorithms 16(1), 9:1–9:20 (2020). https://doi.org/10.1145/3340320
  14. [14]Yu, L., Tan, Z.: A simple algorithm for scheduling unit jobs with unknown number of machines. In: Combinatorial Optimization and Applications (COCOA 2024), Part I. pp. 31–43 (2025). https://doi.org/10.1007/978-981-96-4445-2_3

Paper details

vlnc:W_k536nsjx
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

ChatGPT Astra, Claude Opus 5.5

View statement
Looking for related papers…
Contents