betaFeedback

WorksComputer Science

Below Three: A 2.8027-Approximation for Moldable Precedence Scheduling

Abstract

We study makespan minimisation for nonpreemptive moldable jobs with arbitrary precedence constraints on identical processors. Each job runs on a chosen number of processors that remains fixed throughout its execution. Allocating more processors to a job can shorten its execution, but may increase total work and delay other jobs. We assume nonincreasing processing times, nondecreasing work, and a convex duration–work relation after dominated allocations are removed. This model includes jobs with concave speedup, for which Jansen and Zhang obtained a 3.291919…3.291919\ldots-approximation. Independently and concurrently with our work, Chen obtained a 3.016208…3.016208\ldots-approximation for the full convex model and a 2.973912…2.973912\ldots-approximation for concave speedup. We give a deterministic polynomial-time 2.80272.8027-approximation for the full convex model and every number of processors. Our result breaks the factor-three barrier for this model and also improves the approximation guarantee for concave speedup.

Funding. Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) – Project number 453769249.

Introduction

Parallel applications combine two forms of concurrency: several jobs may run at the same time, and a single job may use several processors. A scheduler must decide how to divide the available processors between these alternatives. Allocating more processors to a job can shorten a chain of dependent jobs, but imperfect speedup may increase the total processor time consumed. With precedence constraints, a locally attractive allocation can therefore delay other jobs and increase the overall completion time. The central difficulty is to choose allocations that balance precedence-path lengths and total work, and then turn those allocations into a feasible schedule.

We study nonpreemptive moldable scheduling in the following model.

Definition 1 (Moldable Scheduling with Precedence Constraints). An instance consists of a directed acyclic graph G=(J,E)G = (J, E), mm identical processors, and positive rational processing times tj(p)t_j(p) for every job j∈Jj \in J and every integer 1≤p≤m1 \le p \le m. A schedule chooses an allocation pjp_j and a start time Sj≥0S_j \ge0 for each job. Job jj occupies pjp_j processors throughout [Sj,Sj+tj(pj))[S_j, S_j + t_j(p_j)). At every time, the total number of occupied processors is at most mm, and Sj≥Si+ti(pi)S_j \ge S_i + t_i(p_i) for every (i,j)∈E(i, j) \in E. The objective is to minimise the makespan Cmax⁡=max⁡j{Sj+tj(pj)}C_{\max} = \max_j\{S_j + t_j(p_j)\}.

Allocations remain fixed during execution, jobs cannot be preempted, and processor indices need not be contiguous. The input explicitly contains the processing-time tables. Earlier papers also use the term nonpreemptive malleable for this fixed-allocation model [JZ12]; we use moldable to distinguish it from models in which allocations may change during execution.

We assume that processing time is nonincreasing and that work, the product of allocation and processing time, is nondecreasing. Thus, for every job jj and 1≤p<m1 \le p < m,

tj(p+1)≤tj(p),p tj(p)≤(p+1)tj(p+1).t_j(p+1) \le t_j(p), \qquad p\,t_j(p) \le(p+1)t_j(p+1).

After discarding allocations that have the same duration as a smaller allocation, we additionally assume that the piecewise-linear curve through all remaining duration–work points is convex. This model includes the concave-speedup setting of Jansen and Zhang [JZ12] and permits duration plateaus without imposing a particular speedup formula. Definition 3 formalises this convexity condition.

Our Result. We give an approximation guarantee below 2.803 for every number of processors, including instances with arbitrarily many jobs and arbitrary precedence constraints.

Theorem 2. For moldable jobs with the preceding monotonicity and convexity properties and arbitrary precedence constraints, there is a deterministic polynomial-time ρ\rho-approximation for every number of processors, where

ρ=2802671106=2.802671<2.8027.(1)\rho= \frac{2802671}{10^6} = 2.802671 < 2.8027. \tag*{(1)}

The algorithm solves one linear program and constructs a fixed finite family of schedules from the solution to this linear program. Each schedule is obtained by rounding the fractional solution using specific parameters and applying list scheduling. The algorithm returns the shortest resulting schedule. The rounding parameters are specified by constants independent of the instance, and the algorithm is deterministic.

The separation between choosing allocations and scheduling the resulting parallel jobs has a long history. Turek, Wolf, and Yu [TWY92] used this framework for independent parallelisable tasks. With precedence constraints, the allocation problem also resembles the discrete time-cost tradeoff problem: selecting a faster execution mode increases its cost, while the duration of every path must be controlled. Skutella’s bicriteria approximation algorithms [Sku98] address this tradeoff. In moldable scheduling, the work plays the role of cost, and the chosen modes must additionally be scheduled subject to the processors’ instantaneous capacity. List scheduling analyses connect these two stages through path-length and workload bounds, following the classical reasoning of Graham [4].

Under the two monotonicity assumptions alone, Lepère, Trystram, and Woeginger [LTW02] obtained a (3+5)(3+\sqrt{5})-approximation for arbitrary precedence constraints. Jansen and Zhang [JZ06] improved this factor to 4.730598…4.730598\ldots by refining the relaxation and rounding analysis. Chen [2] subsequently studied an iterative LP method for this general monotone model, reporting a factor of 4.48414.4841 after two iterations and factors approaching 2+22+\sqrt{2} as the number of iterations increases. These results do not assume the convex duration–work frontiers required here.

Additional structure in the processing-time tables supports stronger bounds. Jansen and Zhang [JZ12] showed that concave speedup implies convexity of the duration–work relation and obtained a 3.291919…3.291919\ldots-approximation by LP rounding, processor capping, and list scheduling. Their rounding rule uses the interpolation weight between adjacent durations. Chen and Chu [1] considered convex work as a function of duration and proved a (2+2)(2+\sqrt{2})-approximation. Their paper also reported a factor of 2.9549 for strictly decreasing processing times; Chen’s recent preprint [3] identifies an invalid elimination step in that argument and corrects that claim.

Independent and Concurrent Work. Chen’s arXiv preprint [3] studies the same convex-frontier model and uses similar ideas: a rounding decision based on the slower duration relative to the fractional duration, followed by processor capping and list scheduling. Our results and Chen’s were obtained independently and concurrently. Chen proves an optimal pointwise time-work tradeoff for this rounding rule and obtains a 13(30+493)/225=3.016208…13(30+\sqrt{493})/225 = 3.016208\ldots-approximation for the general convex-frontier model and a 2.973912…2.973912\ldots-approximation for concave speedup. Our improvement comes from averaging work and schedule bounds across a family of threshold-cap pairs and from excluding path work from the waiting-time charge. The factor in (1) is smaller than both of these guarantees and applies to the full model considered here.

Organisation. Section 2 presents the LP relaxation, followed by rounding and list scheduling with parameters left unspecified. Section 3 gives the parameterised analysis, and Section 4 explains the optimisation, the numerical search, and an exactly certified choice. Section 5 completes the approximation and running-time analysis. The main algorithm and its parameter selection concern m≥6m \ge6; Appendix § 7 handles m≤5m \le5 with a stronger bound. Algebraic proofs and the details of the exact certificate are deferred to the appendix. The basic relaxation and list-scheduling lemmas remain valid for every positive mm.

The Algorithm

Write [k]={1,…,k}[k] = \{1,\ldots,k\}, and let OPT denote the minimum makespan. Polynomial time refers to the binary encoding length of the explicit tables and the precedence graph. Paths are nonempty; a single job is a path. We exclude empty instances, whose optimum is zero.

We describe the algorithm for m≥6m \ge6; Appendix § 7 handles fewer processors.

In this section, we first solve a linear program that assigns each job a fractional duration and work value. It relaxes the processor capacity constraints to a total-work bound and uses completion-time variables to bound every precedence path without listing the paths explicitly.

If two allocations give the same duration, the smaller allocation dominates the larger one. For each job jj, define the set of retained allocations

Aj={1}∪{p∈{2,…,m}:tj(p)<tj(p−1)}.A_j = \{1\} \cup\{p \in\{2,\ldots,m\}: t_j(p) < t_j(p-1)\}.

These are the smallest allocations attaining each duration, so the values tj(p)t_j(p) for p∈Ajp \in A_j are distinct. We preserve the original processor counts: consecutive elements of AjA_j need not be consecutive integers. The original processing-time table remains available for capping. Restricting each job to its retained allocations preserves the optimum: replacing a discarded allocation by the retained allocation of the same duration only reduces its processor requirement.

Definition 3 (Convex Duration-Work Frontier). The duration-work frontier FjF_j is the continuous piecewise-linear interpolation through the points (tj(p),ptj(p))(t_j(p),pt_j(p)) for p∈Ajp \in A_j. We call the table convex if FjF_j is convex on [tj(m),tj(1)][t_j(m),t_j(1)]. A one-point frontier is convex by convention.

Figure 1 illustrates the preprocessing and the resulting interpolation. Points between retained durations represent fractional LP choices, rather than additional processor allocations.

Processing-time table and convex duration–work frontier

Figure 1. A processing-time table and its convex duration–work frontier. Allocation p=3p = 3 is dominated by p=2p = 2, which has the same duration and less work. The black points correspond to Aj={1,2,4,5}A_j = \{1, 2, 4, 5\}; the segments interpolate between them. For example, duration 77 combines allocations p=2p = 2 and p=4p = 4 with equal weights and has fractional work Fj(7)=20F_j(7) = 20, shown by the grey point.

We assume throughout that every frontier is convex. Jansen and Zhang [JZ12, Theorem 2.2] derive this convexity from the stronger assumption of concave speedup. Our model also allows interior duration plateaus, retaining the smallest allocation on each plateau.

For each job j∈Jj \in J and each retained allocation p∈Ajp \in A_j, introduce a weight θj,p≥0\theta_{j,p} \ge0. Let djd_j and wjw_j be the fractional duration and work, respectively, and let cjc_j be a completion-time bound. We use the assignment relaxation of Jansen and Zhang [JZ12, Section 3.1, equation (10)], written for the retained allocations:

min⁡T∑p∈Ajθj,p=1(j∈J),dj=∑p∈Ajθj,ptj(p)(j∈J),wj=∑p∈Ajθj,pp tj(p)(j∈J),cj≥dj(j∈J),cj≥ci+dj((i,j)∈E),cj≤T(j∈J),∑j∈Jwj≤mT.(2)\begin{aligned} \min\quad&T\\ \sum_{p\in A_j}\theta_{j,p} &= 1 &&(j\in J),\\ d_j &= \sum_{p\in A_j}\theta_{j,p}t_j(p) &&(j\in J),\\ w_j &= \sum_{p\in A_j}\theta_{j,p}p\,t_j(p) &&(j\in J),\\ c_j &\ge d_j &&(j\in J),\\ c_j &\ge c_i+d_j &&((i,j)\in E),\\ c_j &\le T &&(j\in J),\\ \sum_{j\in J}w_j &\le mT. \tag*{(2)} \end{aligned}

The constraints cj≥djc_j \ge d_j are included explicitly, also for source jobs. Together with the precedence constraints, they imply that the sum of the fractional durations along any directed path is at most TT; Lemma 4 proves this implication. The LP has polynomial size.

Take an optimal LP solution and consider each job’s duration djd_j. As a convex combination of retained durations, djd_j need not itself equal a retained duration. If dj=tj(s)d_j = t_j(s) for some s∈Ajs \in A_j, replace the job’s weights by weight one on allocation ss and call the job integral. Otherwise, there is a unique pair s<fs < f of consecutive elements of AjA_j satisfying tj(s)>dj>tj(f)t_j(s) > d_j > t_j(f). Set

θj,s=dj−tj(f)tj(s)−tj(f),θj,f=1−θj,s,\theta_{j,s} = \frac{d_j - t_j(f)}{t_j(s) - t_j(f)}, \qquad\theta_{j,f} = 1 - \theta_{j,s},

and set all other weights to zero; call this job fractional. This replacement preserves djd_j and, by convexity, does not increase wjw_j, as proved in Lemma 4. Hence it remains optimal. From now on, wjw_j denotes the work after this replacement.

For a fractional job jj, the allocations s<fs < f are its slower and faster retained allocations, respectively. Write θ=θj,s\theta= \theta_{j,s}, so that θj,f=1−θ\theta_{j,f} = 1 - \theta. The corresponding durations and LP values satisfy

tj(s)=⋯=tj(f−1)>tj(f),1≤s<f≤m,dj=θtj(s)+(1−θ)tj(f),wj=θstj(s)+(1−θ)ftj(f),0<θ<1.(3)\begin{aligned} t_j(s) &= \cdots= t_j(f-1) > t_j(f), \qquad1 \le s < f \le m,\\ d_j &= \theta t_j(s) + (1-\theta)t_j(f),\\ w_j &= \theta s t_j(s) + (1-\theta)f t_j(f), \qquad0 < \theta< 1. \tag*{(3)} \end{aligned}

The slower duration plateau runs from allocation ss through f−1f-1. When considering several jobs, we write sjs_j and fjf_j for their retained allocations. Monotonicity of work at allocations f−1f-1 and ff gives

tj(f)tj(s)≥f−1f.(4)\frac{t_j(f)}{t_j(s)} \ge\frac{f-1}{f}. \tag*{(4)}

This estimate is the reason for requiring consecutive retained allocations.

Rounding, Capping, and List Scheduling

We construct a finite family of NN schedules from the same optimal LP solution, represented as above. Choose thresholds αi>1\alpha_i > 1 and cap parameters 2<ri<32 < r_i < 3, indexed by i∈[N]i \in[N]. We leave these pairs and the family size NN unspecified until § 4. Define

Bi=⌈mri⌉,B⋆=min⁡i∈[N]Bi,αi′=max⁡{αi,1+1B⋆}.(5)B_i = \left\lceil\frac{m}{r_i} \right\rceil, \qquad B_\star= \min_{i \in[N]} B_i, \qquad\alpha'_i = \max\left\{\alpha_i, 1 + \frac{1}{B_\star}\right\}. \tag*{(5)}

For a single run i∈[N]i \in[N], write α=αi′\alpha= \alpha'_i and B=BiB = B_i. We round and cap the LP solution as follows. For an integral job jj, let ss be its retained allocation. For a fractional job jj, use its slower and faster retained allocations ss and ff from (3). The final allocation is

pj={min⁡{s,B},if j is integral,min⁡{s,B},if j is fractional and tj(s)≤αdj,min⁡{f,B},if j is fractional and tj(s)>αdj.(6)p_j = \begin{cases} \min\{s,B\}, & \text{if } j \text{ is integral},\\ \min\{s,B\}, & \text{if } j \text{ is fractional and } t_j(s) \le\alpha d_j,\\ \min\{f,B\}, & \text{if } j \text{ is fractional and } t_j(s) > \alpha d_j. \end{cases} \tag*{(6)}

Once the allocations are fixed, we use an event-driven list schedule. At time zero and at each completion event, repeatedly start a ready job that fits on the idle processors until no such job remains. A job is ready when all of its immediate predecessors have completed. Fix any job ordering to break ties, making the rule deterministic. If unfinished jobs remain and none is running, the precedence graph has a ready job, and that job fits because its allocation is at most mm. Thus the procedure always makes progress. Every event starts a job or completes one, so there are polynomially many events.

For each run, we apply this rule to the rounded and capped jobs and return the shortest of the NN schedules. Algorithm 1 summarises the complete algorithm.

Algorithm 1 Threshold Rounding with Processor Caps

Require: An instance with m≥6m \ge6; pairs (αi,ri)i=1N(\alpha_i,r_i)_{i=1}^{N} with αi>1\alpha_i > 1 and 2<ri<32 < r_i < 3

  1. Remove dominated allocations and solve the LP (2).

  2. Compute BiB_i, B⋆B_{\star}, and αi′\alpha_i' from (5).

  3. for i=1,…,Ni = 1,\ldots,N do

  4. Round jobs to allocations pip_i using (6).

  5. Construct a list schedule SiS_i using durations tj(pj)t_j(p_j).

  6. end for

  7. return a schedule of minimum makespan among S1,…,SNS_1,\ldots,S_N.

Parameterised Analysis

The analysis has three steps. The LP bounds fractional path lengths and total work. The list rule converts rounded durations and work into a makespan bound. Finally, suitable weights combine these bounds over the threshold-cap family. All LP quantities below refer to an optimal solution in which each job uses one retained allocation or a convex combination of two consecutive retained allocations.

The next lemma bounds the durations and work in an LP solution and justifies restricting each job to two consecutive retained allocations.

Lemma 4. The optimum of (2) satisfies T≤OPTT \le\mathrm{OPT}. Every feasible solution satisfies

∑j∈Pdj≤Tfor every directed path P,\sum_{j \in P} d_j \le T \quad\text{for every directed path } P,
tj(1)≤wj≤mdj,∑jwj≤mT.(7)t_j(1) \le w_j \le m d_j,\qquad\sum_j w_j \le mT. \tag*{(7)}

A solution can be adjusted, without changing its durations or increasing its work, so that each job uses one retained allocation or a convex combination of two consecutive retained allocations.

Proof. A feasible schedule supplies an allocation per job, its completion times, and its makespan. Replacing an allocation by the retained allocation of the same duration only reduces processor usage, preserving feasibility. Integrating processor usage bounds total work by mm times the makespan, so these values are LP feasible and T≤OPTT \le\mathrm{OPT}.

For a directed path P=(j1,…,jk)P = (j_1,\ldots,j_k), the LP constraints give cj1≥dj1c_{j_1} \ge d_{j_1} and cjℓ−cjℓ−1≥djℓc_{j_\ell} - c_{j_{\ell-1}} \ge d_{j_\ell} for 2≤ℓ≤k2 \le\ell\le k. Adding these inequalities yields

∑ℓ=1kdjℓ≤cj1+∑ℓ=2k(cjℓ−cjℓ−1)=cjk≤T.\sum_{\ell=1}^{k} d_{j_\ell} \le c_{j_1} + \sum_{\ell=2}^{k}(c_{j_\ell} - c_{j_{\ell-1}}) = c_{j_k} \le T.

For each retained allocation p∈Ajp \in A_j, monotonicity of work and p≤mp \le m give tj(1)≤ptj(p)≤mtj(p)t_j(1) \le p t_j(p) \le m t_j(p). Taking the convex combination specified by the LP proves the individual work bounds; the total-work bound is an LP constraint.

An LP duration djd_j is a convex combination of retained durations and need not itself be a retained duration. If dj=tj(p)d_j = t_j(p) for some p∈Ajp \in A_j, assign weight one to allocation pp. Otherwise, choose the unique consecutive elements s<fs < f of AjA_j satisfying tj(s)>dj>tj(f)t_j(s) > d_j > t_j(f) and assign weights

λ=dj−tj(f)tj(s)−tj(f),1−λ\lambda= \frac{d_j - t_j(f)}{t_j(s) - t_j(f)}, \qquad1-\lambda

to allocations ss and ff, respectively. This preserves djd_j. Let FjF_j be the piecewise-linear duration-work function from Definition 3. Its convexity gives, for the original weights,

Fj(dj)≤∑p∈Ajθj,pFj(tj(p))=wj.F_j(d_j) \le\sum_{p\in A_j} \theta_{j,p}F_j(t_j(p)) = w_j.

The new weights attain Fj(dj)F_j(d_j), so work does not increase and all LP constraints remain valid. Finding the consecutive retained allocations and computing the new weights use polynomially many rational operations.

We first bound the makespan in terms of a precedence path and the work of jobs outside that path. We then derive a bound that no longer depends on the path.

Fix an integer cap 1≤B≤m1 \le B \le m and processor allocations pj≤Bp_j \le B, and use the list scheduling rule from § 2.1. Write CC for the resulting makespan, and define

Q=m−B+1,Uj=pjtj(pj),Q = m - B + 1,\qquad U_j = p_jt_j(p_j),

where UjU_j is the work of job jj at its assigned allocation.

Lemma 5. There is a directed path PP such that

C≤∑j∈Ptj(pj)+1Q∑j∉PUj.(8)C \le\sum_{j\in P} t_j(p_j) + \frac{1}{Q}\sum_{j\notin P} U_j. \tag*{(8)}

Proof. Choose a last-finishing job and trace backwards, choosing for each non-source job an immediate predecessor whose completion time is latest. This gives a directed path PP. Consider the intervals before the first path job starts and between successive executions of path jobs. Throughout each such interval, the next path job is ready: the first path job is a source, and the chosen predecessor of every later path job finishes no earlier than any of its other immediate predecessors.

After the list-scheduling procedure has processed an event, any ready job that has not started does not fit. Since the next path job has allocation p≤Bp \le B, at least m−p+1≥Qm-p+1 \ge Q processors are busy. All jobs executing in the intervals under consideration lie outside PP. By an area argument, the total length of these intervals is at most ∑j∉PUj/Q\sum_{j\notin P} U_j/Q. The remaining part of [0,C][0,C] consists of the executions of the path jobs, proving the claim.

The next lemma removes the path from the makespan bound. We first define the two classes of jobs used throughout the remaining analysis. Recall that B⋆=min⁡iBiB_\star= \min_i B_i is the smallest processor cap in (5). Using the faster retained allocation fjf_j of each fractional job, define

T={j∈J:j is fractional and fj≤B⋆},W=J∖T.(9)\mathcal{T} = \{j \in J : j\text{ is fractional and } f_j \le B_\star\},\qquad\mathcal{W} = J \setminus\mathcal{T}. \tag*{(9)}

We call the jobs in T\mathcal{T} thin and those in W\mathcal{W} wide. A thin job has both retained allocations at most B⋆B_\star. The wide jobs are exactly the integral jobs and the fractional jobs with fj>B⋆f_j > B_\star. In particular, an integral job belongs to W\mathcal{W} regardless of its processor allocation. The partition depends only on the LP solution and B⋆B_\star, so it is the same in every run.

Consider a single run with threshold α≥1+1/B⋆\alpha\ge1 + 1/B_\star and integer cap B⋆≤B≤mB_\star\le B \le m. Write p^j\widehat{p}_j for the allocation selected by threshold rounding (before the min-operation in (6)) and pj=min⁡{p^j,B}p_j = \min\{\widehat{p}_j,B\} for the final allocation. A job is capped precisely when p^j>B\widehat{p}_j > B. Using the notation above for these final allocations, put

c=1−1Q,WW=∑j∈Wwj,UT=∑j∈TUj.c = 1 - \frac{1}{Q},\qquad W_{\mathcal{W}} = \sum_{j\in\mathcal{W}} w_j,\qquad U_{\mathcal{T}} = \sum_{j\in\mathcal{T}} U_j.

Thus WWW_{\mathcal{W}} is the LP work of the wide jobs, whereas UTU_{\mathcal{T}} is the actual final work of the thin jobs in this run.

Lemma 6. For the partition and rounding defined above, the resulting list schedule has makespan

C≤cαT+max⁡{1Q,1B−cαm}WW+UTQ.(10)C \le c\alpha T + \max\left\{\frac{1}{Q},\frac{1}{B}-\frac{c\alpha}{m}\right\}W_W+\frac{U_T}{Q}. \tag*{(10)}

Proof. A thin job satisfies p^j≤B⋆≤B\hat{p}_j \le B_\star\le B, so it is never capped. For a fractional wide job, the notation in (3) and the adjacency bound give

tj(sj)dj≤tj(sj)tj(fj)≤fjfj−1≤1+1B⋆<α.\frac{t_j(s_j)}{d_j} \le\frac{t_j(s_j)}{t_j(f_j)} \le\frac{f_j}{f_j-1} \le1+\frac{1}{B_\star} < \alpha.

It therefore selects its slower allocation, whose work is at most wjw_j. An integral job has work wjw_j before capping. Since capping cannot increase work, every wide job has final work Uj≤wjU_j \le w_j.

Define vj=Ujv_j=U_j for thin jobs and vj=wjv_j=w_j for wide jobs. Then Uj≤vjU_j \le v_j in both cases. Apply Lemma 5, replace each off-path work term by vjv_j, and write the off-path sum as the total sum minus the path sum:

C≤∑j∈Ptj(pj)+1Q∑j∉Pvj=∑j∈P(tj(pj)−vjQ)+1Q∑jvj=∑j∈P(tj(pj)−vjQ)+WW+UTQ.\begin{aligned} C &\le\sum_{j\in P}t_j(p_j)+\frac{1}{Q}\sum_{j\notin P}v_j\\ &=\sum_{j\in P}\left(t_j(p_j)-\frac{v_j}{Q}\right)+\frac{1}{Q}\sum_jv_j\\ &=\sum_{j\in P}\left(t_j(p_j)-\frac{v_j}{Q}\right)+\frac{W_W+U_T}{Q}. \end{aligned}

For a thin job j∈Pj\in P, vj=pjtj(pj)≥tj(pj)v_j=p_jt_j(p_j)\ge t_j(p_j), and its allocation is unchanged by the cap. Threshold rounding therefore gives tj(pj)≤αdjt_j(p_j)\le\alpha d_j, so its contribution in parentheses is at most cαdjc\alpha d_j. The same bound holds for a wide job whose selected allocation is at most BB: its allocation is also unchanged, and vj=wj≥pjtj(pj)≥tj(pj)v_j=w_j\ge p_jt_j(p_j)\ge t_j(p_j).

Every remaining path job is capped and wide. Its final allocation is BB, so the final-work bound just proved gives Btj(B)≤wjBt_j(B)\le w_j. Its contribution in parentheses is therefore at most (1/B−1/Q)wj(1/B-1/Q)w_j. Since wj≤mdjw_j\le md_j, this is at most

cαdj+max⁡{0,1B−1Q−cαm}wj.c\alpha d_j+\max\left\{0,\frac{1}{B}-\frac{1}{Q}-\frac{c\alpha}{m}\right\}w_j.

Sum over the path, apply its duration bound in (7), and bound the additional capped-path work by WWW_W. Adding WW/QW_W/Q gives (10).

Averaging across Runs

We analyse the work obtained by rounding each job with the NN threshold choices. Let Uj(i)U_j(i) be the work of job jj after rounding with the original threshold αi\alpha_i, before capping. Assign nonnegative weights νi\nu_i to the threshold choices, with ∑iνi=1\sum_i\nu_i=1, and use the same weights for every job. For a fixed job jj, these weights define an average of its work across the NN threshold choices. Our aim is to find conditions under which

∑iνiUj(i)≤βwjfor every job j,\sum_i\nu_iU_j(i)\le\beta w_j\qquad\text{for every job }j,

where β>1\beta>1 is a target work factor. Throughout this analysis, sums over ii range over [N][N] unless explicitly restricted.

An integral job has work wjw_j under every threshold. For a fractional job jj, use the notation in (3): threshold αi\alpha_i selects the faster allocation precisely when αi<tj(s)/dj\alpha_i < t_j(s)/d_j, and selects the slower allocation otherwise. Its weighted work therefore depends only on the total weight ∑i:αi<tj(s)/djνi\sum_{i:\alpha_i<t_j(s)/d_j}\nu_i assigned to the faster choice. We control this quantity by bounding the weight of thresholds below each value yy by a function F(y)F(y). The next two lemmas show that the function below gives a sufficient bound for every feasible pair of retained allocations and durations. Raising the thresholds to αi′\alpha'_i and imposing the processor caps cannot increase work, so the resulting work guarantee also applies to the actual runs.

Write D=β−1D=\beta-1 and, for y>1y>1, define

A(y)=β(1−1/y),A(y)=\beta(1-1/y),
F(y)=min⁡{(2A(y)+D)2, inf⁡k∈Z≥1((k+2)A(y)+Dk)}.(11)F(y)=\min\left\{\left(\sqrt{2A(y)}+\sqrt{D}\right)^2,\ \inf_{k\in\mathbb{Z}_{\ge1}}\left((k+2)A(y)+\frac{D}{k}\right)\right\}. \tag*{(11)}

and set F(1)=0F(1)=0. The function FF is nondecreasing, because A(y)A(y) and every expression in the minimum are nondecreasing.

The expression in the next lemma arises from rearranging the target work inequality, as shown in the proof of Lemma 8. Bounding it from below uniformly over the possible allocations and duration ratios yields the sufficient bound F(y)F(y) on the weight assigned to faster choices.

Lemma 7 (8K). For all A,D>0A,D>0, every integer b≥2b\ge2, and every 1−1/b≤r<11-1/b\le r<1 with br>1br>1, we have

A1−r+Dbr−1≥min⁡{(2A+D)2, inf⁡k∈Z≥1((k+2)A+Dk)}.(12)\frac{A}{1-r}+\frac{D}{br-1}\ge\min\left\{\left(\sqrt{2A}+\sqrt{D}\right)^2,\ \inf_{k\in\mathbb{Z}_{\ge1}}\left((k+2)A+\frac{D}{k}\right)\right\}. \tag*{(12)}

We can now bound the weighted average of each job’s work across the threshold choices. The following lemma gives a sufficient condition for this average to be at most β\beta times the job’s LP work, where β>1\beta>1 is the target work factor used to define FF.

Lemma 8. Let H>1H>1 satisfy F(H)=1F(H)=1. Suppose thresholds αi>1\alpha_i>1 and nonnegative weights νi\nu_i satisfy

∑iνi=1,∑i:αi<yνi≤F(y)for 1<y≤H.(13)\sum_i\nu_i=1,\qquad\sum_{i:\alpha_i<y}\nu_i\le F(y)\quad\text{for }1<y\le H. \tag*{(13)}

Then, for every job jj,

∑iνiUj(i)≤βwj.(14)\sum_i\nu_iU_j(i)\le\beta w_j. \tag*{(14)}

This inequality remains valid if any thresholds are increased.

Proof. An integral job has work wjw_j in every rounding, so its weighted work is wj≤βwjw_j\le\beta w_j, as required by (14). For a fractional job jj, use (3) and put

r=tj(f)tj(s),x=djtj(s),u=∑i:αi<1/xνi.r=\frac{t_j(f)}{t_j(s)},\qquad x=\frac{d_j}{t_j(s)},\qquad u=\sum_{i:\alpha_i<1/x}\nu_i.

The slower allocation has work s tj(s)s\,t_j(s), while the faster allocation has work f tj(f)=fr tj(s)f\,t_j(f)=fr\,t_j(s). The faster allocation is chosen precisely for the thresholds counted by uu; the remaining weight 1−u1-u selects the slower allocation. Dividing the weighted rounded work by tj(s)t_j(s) therefore gives

∑iνiUj(i)tj(s)=(1−u)s+u fr=s+(fr−s)u.(15)\frac{\sum_i\nu_iU_j(i)}{t_j(s)}=(1-u)s+u\,fr=s+(fr-s)u. \tag*{(15)}

In the LP representation (3), the weights on the slower and faster allocations are θ\theta and 1−θ1-\theta. Dividing the LP duration equation by tj(s)t_j(s) yields

x=θ+(1−θ)r=1−(1−θ)(1−r).x=\theta+(1-\theta)r=1-(1-\theta)(1-r).

Since r<1r<1, the LP weight on the faster allocation is 1−θ=(1−x)/(1−r)1-\theta=(1-x)/(1-r). Using these weights to compute the LP work and then dividing by tj(s)t_j(s), we obtain

wj=θs tj(s)+(1−θ)f tj(f),⟺wjtj(s)=θs+(1−θ)fr=s+(fr−s)1−x1−r.(16)\begin{aligned} w_j&=\theta s\,t_j(s)+(1-\theta)f\,t_j(f),\\ \Longleftrightarrow\quad\frac{w_j}{t_j(s)}&=\theta s+(1-\theta)fr=s+(fr-s)\frac{1-x}{1-r}. \tag*{(16)} \end{aligned}

Equations (15) and (16) express both normalised work quantities as weighted averages of the same two values, ss and frfr. The faster allocation has weight uu after rounding and (1−x)/(1−r)(1-x)/(1-r) in the LP; in each case, the slower allocation receives the remaining weight.

Since s<fs<f, monotonicity of work gives s tj(s)≤f tj(f)s\,t_j(s)\leq f\,t_j(f), and hence fr≥sfr\geq s. If fr=sfr=s, both retained allocations have the same work. Therefore

∑iνiUj(i)=wj=s tj(s)≤βwj.\sum_i \nu_iU_j(i)=w_j=s\,t_j(s)\leq\beta w_j.

Thus the target inequality (14) holds regardless of the rounding choices.

Now suppose fr>s≥1fr>s\geq1. Our goal is ∑iνiUj(i)≤βwj\sum_i\nu_iU_j(i)\leq\beta w_j, as stated in (14). Dividing this inequality by tj(s)>0t_j(s)>0 and substituting (15) and (16) shows that it is equivalent to

s+(fr−s)u≤β(s+(fr−s)1−x1−r).(17)s+(fr-s)u\leq\beta\left(s+(fr-s)\frac{1-x}{1-r}\right). \tag*{(17)}

Subtracting ss from both sides of (17) and dividing by fr−s>0fr-s>0 gives, with D=β−1D=\beta-1,

u≤β(1−x)1−r+Dsfr−s.(18)u\leq\frac{\beta(1-x)}{1-r}+D\frac{s}{fr-s}. \tag*{(18)}

Since s≥1s\geq1, we have s/(fr−s)≥1/(fr−1)s/(fr-s)\geq1/(fr-1). Also r≥1−1/fr\geq1-1/f by (4). If 1/x≤H1/x\leq H, condition (13) and Lemma 7, with b=fb=f and A=β(1−x)=A(1/x)A=\beta(1-x)=A(1/x), prove (18). If 1/x>H1/x>H, apply the same lemma with b=fb=f and A=A(H)A=A(H). Its right-hand side equals F(H)=1F(H)=1, and β(1−x)>A(H)\beta(1-x)>A(H). Consequently the right-hand side of (18) is at least 1≥u1\geq u. Finally, increasing a threshold cannot increase the rounded work.

We now combine the work bound with a weighted average of the constructed schedules’ makespans. The weights νi\nu_i average job work, while πi\pi_i average schedule makespans. The algorithm returns the shortest schedule, whose makespan is at most this average.

Fix rational thresholds αi>1\alpha_i>1 and cap parameters 2<ri<32<r_i<3, indexed by i∈[N]i\in[N]. Let πi,νi≥0\pi_i,\nu_i\geq0 be rational weights with ∑iπi=∑iνi=1\sum_i\pi_i=\sum_i\nu_i=1. For a real number zz, write (z)+=max⁡{z,0}(z)_+=\max\{z,0\}, and define

ki=riri−1,rmax⁡=max⁡iri,μ=∑iπiαi,δ3=∑iπi(4/3−αi)+,k_i=\frac{r_i}{r_i-1},\qquad r_{\max}=\max_i r_i,\qquad\mu=\sum_i\pi_i\alpha_i,\qquad\delta_3=\sum_i\pi_i(4/3-\alpha_i)_+,
V=∑iπimax⁡{αi+ki,ri}.V=\sum_i\pi_i\max\{\alpha_i+k_i,r_i\}.

Lemma 9. Assume that ∑iνiUj(i)≤βwj\sum_i \nu_i U_j(i) \le\beta w_j for every job jj, and that a number κ>0\kappa> 0 satisfies

πiki≤κνifor every i,3(rmax⁡−1)δ3≤μ,\pi_i k_i \le\kappa\nu_i \quad\text{for every } i,\qquad3(r_{\max}-1)\delta_3 \le\mu,
4(rmax⁡−1)3rmax⁡−2≤min⁡i(ri−ki).(19)\frac{4(r_{\max}-1)}{3r_{\max}-2} \le\min_i(r_i-k_i). \tag*{(19)}

For every m≥6m \ge6, the algorithm of § 2 with these threshold-cap pairs returns a schedule of makespan at most

max⁡{μ+βκ,V}T.\max\{\mu+\beta\kappa,V\}T.

Proof. For each run ii, we apply the makespan bound (10) from Lemma 6. We then average these bounds with weights πi\pi_i. Let BiB_i, B⋆B_\star, and αi′\alpha'_i be as in (5), and abbreviate

Qi=m−Bi+1,ci=1−1Qi.Q_i=m-B_i+1,\qquad c_i=1-\frac{1}{Q_i}.

Since m≥6m\ge6 and rmax⁡<3r_{\max}<3, we have B⋆≥3B_\star\ge3.

Use the fixed partition T,W\mathcal{T},\mathcal{W} from (9). Since Bi≥B⋆B_i\ge B_\star and αi′≥1+1/B⋆\alpha'_i\ge1+1/B_\star, Lemma 6 applies to every run with this same partition. In particular, thin jobs are uncapped and wide jobs have final work at most wjw_j in every run.

Since Bi=⌈m/ri⌉B_i=\lceil m/r_i\rceil, we have m/ri≤Bi<m/ri+1m/r_i\le B_i<m/r_i+1. Thus

mBi≤ri,Qi=m−Bi+1>m(1−1ri)=mki,(20)\frac{m}{B_i}\le r_i,\qquad Q_i=m-B_i+1>m\left(1-\frac{1}{r_i}\right)=\frac{m}{k_i}, \tag*{(20)}

and hence m/Qi<kim/Q_i<k_i. We also have B⋆=⌈m/rmax⁡⌉B_\star=\lceil m/r_{\max}\rceil, so m−B⋆≤(rmax⁡−1)B⋆m-B_\star\le(r_{\max}-1)B_\star. Since Bi≥B⋆B_i\ge B_\star, we have Qi≤m−B⋆+1Q_i\le m-B_\star+1 and therefore

ci≤c⋆:=m−B⋆m−B⋆+1.(21)c_i\le c_\star:=\frac{m-B_\star}{m-B_\star+1}. \tag*{(21)}

To prepare for averaging the makespan bounds, set

x=∑j∈WwjmT,y=∑j∈TwjmT.x=\frac{\sum_{j\in\mathcal{W}}w_j}{mT},\qquad y=\frac{\sum_{j\in\mathcal{T}}w_j}{mT}.

Then x,y≥0x,y\ge0 and x+y≤1x+y\le1. In the makespan bound (10), the duration term and the wide-job work term, after division by TT, can be rewritten as

ciαi′+xmax⁡{m/Qi,m/Bi−ciαi′}=(1−x)ciαi′+xmax⁡{ciαi′+m/Qi,m/Bi}.(22)\begin{aligned} c_i\alpha'_i+x\max\{m/Q_i,m/B_i-c_i\alpha'_i\} &=(1-x)c_i\alpha'_i+x\max\{c_i\alpha'_i+m/Q_i,m/B_i\}. \tag*{(22)} \end{aligned}

The following two claims will bound the weighted averages of the coefficients of 1−x1-x and xx by μ\mu and VV, respectively.

Claim 1. The weighted average of the threshold coefficients satisfies

∑iπiciαi′≤μ.\sum_i\pi_i c_i\alpha'_i\le\mu.

Proof of Claim 1. Raising the thresholds from αi\alpha_i to αi′=max⁡{αi,1+1/B⋆}\alpha'_i=\max\{\alpha_i,1+1/B_\star\} increases their weighted average by

Δ=∑iπi(1+1/B⋆−αi)+,∑iπiαi′=μ+Δ.\Delta=\sum_i\pi_i(1+1/B_\star-\alpha_i)_+,\qquad\sum_i\pi_i\alpha'_i=\mu+\Delta.

We show that the factors ci<1c_i < 1 compensate for this increase. Because B⋆≥3B_\star\ge3 and αi>1\alpha_i > 1,

B⋆Δ=∑iπi(1−B⋆(αi−1))+≤∑iπi(1−3(αi−1))+=3∑iπi(4/3−αi)+=3δ3.B_\star\Delta= \sum_i \pi_i\left(1-B_\star(\alpha_i-1)\right)_+ \le\sum_i \pi_i\left(1-3(\alpha_i-1)\right)_+ =3\sum_i \pi_i(4/3-\alpha_i)_+ =3\delta_3.

Combining m−B⋆≤(rmax⁡−1)B⋆m-B_\star\le(r_{\max}-1)B_\star with B⋆Δ≤3δ3B_\star\Delta\le3\delta_3 and the second condition in (19), we obtain

(m−B⋆)Δ≤(rmax⁡−1)B⋆Δ≤3(rmax⁡−1)δ3≤μ.(m-B_\star)\Delta\le(r_{\max}-1)B_\star\Delta\le3(r_{\max}-1)\delta_3 \le\mu.

Using (21), we therefore obtain

∑iπiciαi′≤c⋆(μ+Δ)=(m−B⋆)(μ+Δ)m−B⋆+1=(m−B⋆+1)μ+(m−B⋆)Δ−μm−B⋆+1=μ+(m−B⋆)Δ−μm−B⋆+1≤μ.(23)\begin{aligned} \sum_i \pi_i c_i\alpha_i' &\le c_\star(\mu+\Delta)\\ &=\frac{(m-B_\star)(\mu+\Delta)}{m-B_\star+1}\\ &=\frac{(m-B_\star+1)\mu+(m-B_\star)\Delta-\mu}{m-B_\star+1}\\ &=\mu+\frac{(m-B_\star)\Delta-\mu}{m-B_\star+1}\le\mu. \tag*{(23)} \end{aligned}

This proves the claim, since (m−B⋆)Δ≤μ(m-B_\star)\Delta\le\mu. ■

Claim 2. For every run i∈[N]i\in[N],

max⁡{ciαi′+m/Qi,m/Bi}≤max⁡{αi+ki,ri}.(24)\max\{c_i\alpha_i' + m/Q_i,m/B_i\}\le\max\{\alpha_i+k_i,r_i\}. \tag*{(24)}

Proof of Claim 2. If αi≥1+1/B⋆\alpha_i\ge1+1/B_\star, the threshold is unchanged, so αi′=αi\alpha_i'=\alpha_i. Since ci≤1c_i\le1 and m/Qi≤kim/Q_i\le k_i,

ciαi′+m/Qi=ciαi+m/Qi≤αi+ki,m/Bi≤ri.c_i\alpha_i' + m/Q_i=c_i\alpha_i+m/Q_i\le\alpha_i+k_i,\qquad m/B_i\le r_i.

Taking the maximum proves (24) in this case. If αi<1+1/B⋆\alpha_i<1+1/B_\star, the threshold is raised to αi′=1+1/B⋆\alpha_i'=1+1/B_\star. In this case we show that both entries of the maximum are at most rir_i. Since m/Qi≤kim/Q_i\le k_i, it suffices to show that ciαi′≤ri−kic_i\alpha_i'\le r_i-k_i. By (21),

ciαi′≤m−B⋆m−B⋆+1(1+1B⋆)≤(rmax⁡−1)(B⋆+1)(rmax⁡−1)B⋆+1≤4(rmax⁡−1)3rmax⁡−2≤ri−ki.c_i\alpha_i'\le\frac{m-B_\star}{m-B_\star+1}\left(1+\frac{1}{B_\star}\right) \le\frac{(r_{\max}-1)(B_\star+1)}{(r_{\max}-1)B_\star+1} \le\frac{4(r_{\max}-1)}{3r_{\max}-2}\le r_i-k_i.

The second inequality uses m−B⋆≤(rmax⁡−1)B⋆m-B_\star\le(r_{\max}-1)B_\star. For the third, the preceding fraction equals 1+(rmax⁡−2)/((rmax⁡−1)B⋆+1)1+(r_{\max}-2)/((r_{\max}-1)B_\star+1), which decreases with B⋆B_\star because rmax⁡>2r_{\max}>2; we use B⋆≥3B_\star\ge3. The last inequality is the final condition in (19). Thus ciαi′+m/Qi≤ric_i\alpha_i'+m/Q_i\le r_i whenever the threshold is raised. Since also m/Bi≤rim/B_i\le r_i, both entries of the maximum are at most rir_i, proving (24) in the remaining case. ■

We now bound the average contribution of thin jobs and then average the makespan bounds. Let UT,iU_{T,i} be the final work of the thin jobs in run ii. Recall that Uj(i)U_j(i) is the work of job jj after rounding with the original threshold αi\alpha_i, before capping. Raising the threshold to αi′\alpha_i' can only leave the selected allocation unchanged or switch it from the faster to the slower allocation. Since work is nondecreasing in the allocation, this cannot increase a job’s work. Thin jobs are uncapped, so UT,i≤∑j∈TUj(i)U_{\mathcal{T},i} \le\sum_{j\in\mathcal{T}} U_j(i). Multiplying by νi≥0\nu_i \ge0, summing over runs, and then applying the assumed work bound to each job in the fixed set T\mathcal{T} gives

∑iνiUT,i≤∑j∈T∑iνiUj(i)≤β∑j∈Twj.\sum_i \nu_i U_{\mathcal{T},i} \le\sum_{j\in\mathcal{T}}\sum_i \nu_i U_j(i) \le\beta\sum_{j\in\mathcal{T}} w_j.

The makespan bounds use the schedule weights πi\pi_i and the coefficients 1/Qi1/Q_i. We relate them to this work average as follows:

∑iπiUT,iQi≤1m∑iπikiUT,i≤κm∑iνiUT,i≤βκm∑j∈Twj.(25)\sum_i \pi_i \frac{U_{\mathcal{T},i}}{Q_i} \le\frac{1}{m}\sum_i \pi_i k_i U_{\mathcal{T},i} \le\frac{\kappa}{m}\sum_i \nu_i U_{\mathcal{T},i} \le\frac{\beta\kappa}{m}\sum_{j\in\mathcal{T}} w_j. \tag*{(25)}

The first inequality uses 1/Qi≤ki/m1/Q_i \le k_i/m, which follows from the cap bound (20). The second uses πiki≤κνi\pi_i k_i \le\kappa\nu_i, the first condition in (19); it converts the schedule weights into the work weights. Both inequalities apply term by term because the weights and work values are nonnegative. The last inequality applies the bound on ∑iνiUT,i\sum_i \nu_i U_{\mathcal{T},i} just proved.

Let CiC_i be the makespan of the schedule from run ii. Dividing (10) by TT and using the rewriting (22) gives, for every run,

CiT≤(1−x)ciαi′+xmax⁡{ciαi′+m/Qi,m/Bi}+UT,iQiT.\frac{C_i}{T} \le(1-x)c_i\alpha_i' + x\max\{c_i\alpha_i' + m/Q_i,m/B_i\} + \frac{U_{\mathcal{T},i}}{Q_iT}.

The algorithm returns the shortest of these schedules. Since πi≥0\pi_i \ge0 and ∑iπi=1\sum_i \pi_i = 1, its makespan is at most their weighted average: min⁡iCi≤∑iπiCi\min_i C_i \le\sum_i \pi_i C_i. Moreover, xx is the same in every run because it is defined using the LP work of the fixed set W\mathcal{W}. Multiplying the per-run bounds by πi\pi_i and summing therefore gives

min⁡iCiT≤∑iπiCiT≤(1−x)∑iπiciαi′+x∑iπimax⁡{ciαi′+m/Qi,m/Bi}+1T∑iπiUT,iQi.\frac{\min_i C_i}{T} \le\sum_i \pi_i\frac{C_i}{T} \le(1-x)\sum_i \pi_i c_i\alpha_i' + x\sum_i \pi_i\max\{c_i\alpha_i' + m/Q_i,m/B_i\} + \frac{1}{T}\sum_i \pi_i\frac{U_{\mathcal{T},i}}{Q_i}.

By (25) and the definition of yy, the last term satisfies

1T∑iπiUT,iQi≤βκmT∑j∈Twj=βκy.\frac{1}{T}\sum_i \pi_i\frac{U_{\mathcal{T},i}}{Q_i} \le\frac{\beta\kappa}{mT}\sum_{j\in\mathcal{T}} w_j = \beta\kappa y.

Claim 1 bounds the first weighted coefficient by μ\mu. Claim 2, together with V=∑iπimax⁡{αi+ki,ri}V = \sum_i \pi_i \max\{\alpha_i + k_i, r_i\}, bounds the second by VV. Since x≥0x \ge0 and 1−x≥01-x \ge0, we can apply these bounds to obtain

min⁡iCiT≤μ(1−x)+Vx+βκy≤(μ+βκ)(1−x)+Vx≤max⁡{μ+βκ,V}.\frac{\min_i C_i}{T} \le\mu(1-x) + Vx + \beta\kappa y \le(\mu+ \beta\kappa)(1-x) + Vx \le\max\{\mu+ \beta\kappa, V\}.

The second inequality uses y≤1−xy \le1-x and βκ>0\beta\kappa> 0. The last follows because (1−x)(μ+βκ)+xV(1-x)(\mu+ \beta\kappa) + xV is a convex combination of μ+βκ\mu+ \beta\kappa and VV, as 0≤x≤10 \le x \le1. The averaging is valid even if the paths in Lemma 5 differ between runs, since (10) eliminates each path before the schedules are averaged.

Choosing and Certifying the Parameters

We choose the threshold–cap family once, independently of the scheduling instance, to minimise the guarantee supplied by Lemma 9.

The paper gives a self-contained proof of the guarantee for the chosen parameters, including the rational construction, mathematical arguments, exact sums, and rational bounds in Appendix § 9. We used Python scripts to find the parameters and perform the finite arithmetic checks specified there; they are provided at https://github.com/Felioh/moldable-precedence-scheduling to make those calculations reproducible.

We minimise the objective

max⁡{μ+βκ,V}.(26)\max\{\mu+ \beta\kappa, V\}. \tag*{(26)}

The choices are β>1\beta> 1, any finite number NN of pairs (αi,ri)(\alpha_i, r_i) with αi>1\alpha_i > 1 and 2<ri<32 < r_i < 3, probability weights νi,πi\nu_i, \pi_i, and κ>0\kappa> 0. They must satisfy the cumulative-weight condition (13) and the domination and finite-processor conditions (19). The quantities μ\mu and VV are defined before Lemma 9: μ+βκ\mu+ \beta\kappa bounds the thin-job contribution and VV bounds the wide-job contribution. Thus every feasible rational choice certifies an approximation guarantee.

To find a good choice, we search a family described by three scalars (t,ξ,η)(t, \xi, \eta). For 0<t≤1/50 < t \le1/5, we set β=1+t2\beta= 1 + t^2, place thresholds uniformly between 11 and H=2(1+t2)/(1+t)2H = 2(1+t^2)/(1+t)^2, and use increments of the envelope FF as work weights. The cap curve (C.1) trades path inflation against capacity, while schedule weights proportional to νi(1−1/ri)\nu_i(1 - 1/r_i) enforce domination. The Python search varies tt and η\eta and adjusts ξ\xi to balance the two objective terms. This is a numerical search within a restricted family, not a proof of global optimality.

We then replace the search parameters by rational numbers, round the cumulative work weights down and the caps up, and adjust the schedule weights to preserve domination. Appendix § 9 gives the full construction, using N=65536N = 65536, and its exact sums. The program verify_main_certificate.py checks every sufficient condition using integer and rational arithmetic; the resulting guarantee does not depend on numerical convergence or floating-point tolerances.

Lemma 10. The rational construction in Appendix § 9 satisfies all the conditions of Lemma 9 and has

V≈2.802670863310,μ+βκ≈2.802670869270.V \approx2.802670863310,\qquad\mu+ \beta\kappa\approx2.802670869270.

Both coefficients lie strictly between 11/411/4 and ρ=2802671/106=2.802671\rho= 2802671/10^6 = 2.802671.

The Approximation Guarantee and Running Time

We now apply the parameterised bound to the rational family in § 4. The search is no longer part of the algorithm: the resulting constants are fixed independently of the input.

Proof of Theorem 2. Let m≥6m \ge6. By Lemma 12, the weights νi\nu_i give the average-work bound with factor β\beta. Equation (C.5) supplies the domination condition for the schedule weights. Lemma 10 verifies the remaining hypotheses of Lemma 9. Moreover, αi+ki≤ri\alpha_i+k_i \le r_i for every ii, so V=∑iπiriV=\sum_i \pi_i r_i. Thus the returned schedule satisfies

Cmax⁡≤max⁡{μ+βκ,∑iπiri}T≤ρT≤ρOPT⁡.C_{\max} \le\max\left\{\mu+\beta\kappa,\sum_i\pi_i r_i\right\} \quad T \le\rho T \le\rho\operatorname{OPT}.

For m≤5m \le5, Lemma 11 in Appendix § 7 supplies a schedule of length at most (11/4)T<ρOPT⁡(11/4)T < \rho\operatorname{OPT}. This proves the guarantee for every positive number of processors.

It remains to justify polynomial running time. The LP has polynomial size in the binary encoding of the explicit processing-time tables and the precedence graph. A rational optimal solution of polynomial bit length can be computed in polynomial time; replacing each job’s support by consecutive retained allocations uses rational interpolation. The threshold-cap family has the constant size N=65536N=65536, and all its numbers have constant bit length. In each run, rounding and capping require polynomially many comparisons. The list schedule has at most one start and one completion event per job, and scanning the ready jobs at each event suffices to implement it. Its processing times and event times are rational numbers of polynomial bit length. The small-mm procedures also use only rounding and list scheduling, or a topological ordering. Hence the complete algorithm is deterministic and polynomial.

Declaration of Generative AI Use

The authors developed the approach to improving the framework used in Jansen and Zhang [JZ12] before using generative AI. GPT-6 Astra provided substantial assistance with the analysis: starting from the authors’ ideas, it derived an initial 3.004-approximation guarantee on September 25, 2026. Through successive iterations, the algorithm and its analysis were refined to the final version presented in this paper. The authors extensively revised the presentation and take full responsibility for the paper’s content and correctness.

At Most Five Processors

This appendix supplies the small-processor cases omitted from the main algorithm. The same LP lower bound applies. For m≤2m \le2, execute all jobs sequentially on one processor in a topological order. For 3≤m≤53 \le m \le5, round every fractional job to its slower endpoint, keep every integral allocation, cap all allocations at two, and apply the list rule.

Lemma 11. For m≤5m \le5, the procedures above return a schedule of length at most (11/4)T(11/4)T.

Proof. If m≤2m \le2, the sequential schedule has length

∑jtj(1)≤∑jwj≤mT≤2T.\sum_j t_j(1) \le\sum_j w_j \le mT \le2T.

Now let 3≤m≤53 \le m \le5. Rounding every fractional job to its slower endpoint gives duration at most 2dj2d_j, because tj(s)/dj≤f/(f−1)≤2t_j(s)/d_j \le f/(f-1) \le2, and work at most wjw_j. Capping at two preserves the work bound. Put Q=m−1Q=m-1 and apply Lemma 5, bounding every final work by wjw_j:

C≤∑j∈P(tj(pj)−wjQ)+1Q∑jwj.C \le\sum_{j\in P}\left(t_j(p_j)-\frac{w_j}{Q}\right)+\frac{1}{Q}\sum_j w_j.

A job assigned one processor was not capped, and its path contribution is at most 2(1−1/Q)dj2(1-1/Q)d_j. A job assigned two processors satisfies 2tj(pj)≤wj≤mdj2t_j(p_j) \le w_j \le md_j, and its path contribution is at most m(1/2−1/Q)djm(1/2-1/Q)d_j, since Q≥2Q \ge2. Using the path and work bounds in (7), we obtain

CT≤max⁡{2(1−1Q),m(12−1Q)}+mQ=max⁡{2+m−2m−1,m2}≤114.\frac{C}{T} \le\max\left\{2\left(1-\frac{1}{Q}\right),m\left(\frac{1}{2}-\frac{1}{Q}\right)\right\}+\frac{m}{Q} = \max\left\{2+\frac{m-2}{m-1},\frac{m}{2}\right\}\le\frac{11}{4}.

Proof of pub-main-envelope

Proof of Lemma 7. We minimise the left-hand side over its admissible interval and compare the minimum with one of the terms defining the envelope. Set u=1−ru = 1-r. Then 0<u≤1/b0 < u \le1/b, and the expression becomes

Au+Db−1−bu.\frac{A}{u}+\frac{D}{b-1-bu}.

For positive denominators, the Cauchy–Schwarz inequality gives

Au+Db−1−bu≥(bA+D)2b−1.\frac{A}{u}+\frac{D}{b-1-bu}\ge\frac{\left(\sqrt{bA}+\sqrt{D}\right)^2}{b-1}.

For b=2b=2, the right-hand side is (2A+D)2\left(\sqrt{2A}+\sqrt{D}\right)^2, which is one of the required envelope terms. Now let b≥3b\ge3. The expression is strictly convex in uu and tends to infinity as uu decreases to zero. If its minimum on (0,1/b](0,1/b] is at u=1/bu=1/b, that minimum is

bA+Db−2,bA+\frac{D}{b-2},

the integer envelope term with k=b−2k=b-2.

Otherwise the minimum is attained in the interior. Solving the derivative equation shows that its value and the condition for an interior minimiser are

(bA+D)2b−1,A<Db(b−2)2.\frac{\left(\sqrt{bA}+\sqrt{D}\right)^2}{b-1},\qquad A<\frac{D}{b(b-2)^2}.

In this case we compare with the integer term for k=b−1k=b-1. The difference is

(bA+D)2b−1−((b+1)A+Db−1)=2bAD−(b2−b−1)Ab−1.\frac{\left(\sqrt{bA}+\sqrt{D}\right)^2}{b-1}-\left((b+1)A+\frac{D}{b-1}\right)=\frac{2\sqrt{bAD}-(b^2-b-1)A}{b-1}.

The interior condition gives 2bAD≥2b(b−2)A2\sqrt{bAD}\ge2b(b-2)A, and 2b(b−2)−(b2−b−1)=b2−3b+1>02b(b-2)-(b^2-b-1)=b^2-3b+1>0 for b≥3b\ge3. The difference is therefore nonnegative. In every case one of the terms in the stated envelope is at most the minimum of the left-hand side, proving the lemma.

Exact Verification of the Parameter Choice

This appendix describes and justifies the calculations performed by the provided Python script verify_main_certificate.py, which verifies the fixed parameter choice using exact integer and rational arithmetic. It supplies the algebraic details omitted from § 4.

The Rational Construction

The numerical search uses the cap curve

r(α)=max⁡{3011,α+2+α2+42,ξ+ξ−αη}.(27)r(\alpha)=\max\left\{\frac{30}{11},\frac{\alpha+2+\sqrt{\alpha^2+4}}{2},\sqrt{\xi+\frac{\xi-\alpha}{\eta}}\right\}. \tag*{(27)}

The middle term ensures α+r/(r−1)≤r\alpha+r/(r-1)\le r. The last term is chosen to balance the objective coefficients μ+βκ\mu+\beta\kappa and VV; the first supplies slack for the finite-processor conditions. For the exact construction, fix

t=11376389,ξ=11208491340000000,η=4841327,t = \frac{1137}{6389},\qquad\xi= \frac{112084913}{40000000},\qquad\eta= \frac{484}{1327},
β=1+t2=4211209040819321,H=2(1+t2)(1+t)2=2105604514160169.(28)\beta= 1+t^2 = \frac{42112090}{40819321},\qquad H = \frac{2(1+t^2)}{(1+t)^2} = \frac{21056045}{14160169}. \tag*{(28)}
N=65536,M=1010,S=108.N=65536,\qquad M=10^{10},\qquad S=10^8.

The constants NN, MM, and SS control the threshold grid and the two rational rounding precisions. They are independent of the input instance. For 1≤i≤N1 \le i \le N, set

αi=1+iN(H−1),Ai=β(1−1/αi).\alpha_i = 1+\frac{i}{N}(H-1),\qquad A_i=\beta(1-1/\alpha_i).

To keep the cumulative work weights below FF, round them down. Set z0=0z_0=0, zN=Mz_N=M, and, for 1≤i<N1 \le i < N,

zi=min⁡{M, min⁡1≤k≤64⌊M((k+2)Ai+Dk)⌋+⌊M(2Ai+D)+8M2AiD⌋}.(29)z_i=\min\left\{M,\ \min_{1\le k\le64}\left\lfloor M\left((k+2)A_i+\frac{D}{k}\right)\right\rfloor+\left\lfloor M(2A_i+D)+\sqrt{8M^2A_iD}\right\rfloor\right\}. \tag*{(29)}

Here D=β−1D=\beta-1. Let νi=(zi−zi−1)/M\nu_i=(z_i-z_{i-1})/M. The cutoff 64 is valid for these particular constants, as justified below.

Lemma 12. The weights νi\nu_i are nonnegative, sum to one, and satisfy (13). Consequently, they give average rounded work at most βwj\beta w_j for each job.

The proof below checks that the rounded cumulative weights are nondecreasing and remain below the envelope.

Let rir_i be the smallest multiple of 1/S1/S that is at least r(αi)r(\alpha_i) from (C.1). To preserve the domination condition after this rounding, now use the rational values

ki=riri−1,hi=⌊S(1−1/ri)⌋S,Z=∑iνihi,πi=νihiZ.(30)k_i=\frac{r_i}{r_i-1},\qquad h_i=\frac{\left\lfloor S(1-1/r_i)\right\rfloor}{S},\qquad Z=\sum_i \nu_i h_i,\qquad\pi_i=\frac{\nu_i h_i}{Z}. \tag*{(30)}

The downward rounding of hih_i ensures 0<hi≤1/ki0<h_i\le1/k_i. Therefore Z>0Z>0, the weights πi\pi_i sum to one, and

πiki≤νiZ.(31)\pi_i k_i\le\frac{\nu_i}{Z}. \tag*{(31)}

Thus we may still use κ=1/Z\kappa=1/Z. Moreover, αi+ki≤ri\alpha_i+k_i\le r_i, so V=∑iπiriV=\sum_i\pi_i r_i also remains valid.

The Envelope Endpoint and the Cumulative Weights

First consider the general search parameter 0<t≤1/50<t\le1/5. With β=1+t2\beta=1+t^2 and H=2β/(1+t)2H=2\beta/(1+t)^2, we have

2A(H)=(1−t)2,D=t2.2A(H)=(1-t)^2,\qquad D=t^2.

Thus the square-root entry of F(H)F(H) equals (1−t+t)2=1(1-t+t)^2=1. The difference between consecutive integer entries is

((k+3)A+D/(k+1))−((k+2)A+D/k)=A−Dk(k+1).((k+3)A+D/(k+1))-((k+2)A+D/k)=A-\frac{D}{k(k+1)}.

At A=A(H)A=A(H) this is positive for every k≥1k \ge1, because A(H)≥8/25A(H) \ge8/25 and D≤1/25D \le1/25. The smallest integer entry is therefore

3A(H)+D=1+(1−5t)(1−t)2≥1.3A(H)+D=1+\frac{(1-5t)(1-t)}{2}\ge1.

This proves F(H)=1F(H)=1 throughout the search range. For the constants used in the paper, 2A(H)=(5252/6389)22A(H)=(5252/6389)^2 and D=(1137/6389)2D=(1137/6389)^2.

Proof of Lemma 12. Every expression defining ziz_i is nondecreasing in AiA_i, and AiA_i is nondecreasing in ii. Taking minima and floors preserves this property. Since every ziz_i is at most MM, the final choice zN=Mz_N=M preserves it as well. Consequently νi≥0\nu_i\ge0, and telescoping gives ∑iνi=(zN−z0)/M=1\sum_i\nu_i=(z_N-z_0)/M=1.

We next justify restricting the integer minimum to 1≤k≤641\le k\le64. Direct substitution of the fixed constants gives A1>D/(64⋅65)A_1>D/(64\cdot65). For every i≥1i\ge1 and every k≥64k\ge64, the difference between consecutive integer entries is therefore positive:

Ai−Dk(k+1)>0.A_i-\frac{D}{k(k+1)}>0.

Hence no omitted entry is smaller than the entry with k=64k=64. The other rounded entry satisfies

⌊M(2Ai+D)⌋+⌈8M2AiD⌉≤M(2Ai+D)2.\lfloor M(2A_i+D)\rfloor+\left\lceil\sqrt{8M^2A_iD}\right\rceil\le M(\sqrt{2A_i}+\sqrt{D})^2.

It follows that zi/M≤F(αi)z_i/M\le F(\alpha_i) for i<Ni<N; at i=Ni=N the same statement holds with equality because F(H)=1F(H)=1.

Finally fix 1<y≤H1<y\le H. If no threshold is strictly below yy, the required cumulative bound is immediate. Otherwise let ℓ\ell be the largest index with αℓ<y\alpha_\ell<y. Then ℓ<N\ell<N, and

∑i:αi<yνi=zℓM≤F(αℓ)≤F(y).\sum_{i:\alpha_i<y}\nu_i=\frac{z_\ell}{M}\le F(\alpha_\ell)\le F(y).

Thus (13) holds. Lemma 8 gives the stated rounded-work bound.

Exact Sums and Finite-Machine Inequalities

Proof of Lemma 10. The rational construction gives the exact coefficients

μ+βZ=170619936684405068148014403213550770076087762161272353248853235028830797824,V=4504178902286504320513671116071023398612989725000000.\begin{aligned} \mu+\frac{\beta}{Z}&=\frac{17061993668440506814801440321355077007}{6087762161272353248853235028830797824},\\ V&=\frac{45041789022865043205136711}{16071023398612989725000000}. \end{aligned}

Direct rational comparisons show that

114<V<μ+βZ<2802671106.\frac{11}{4}<V<\mu+\frac{\beta}{Z}<\frac{2802671}{10^6}.

The other quantities needed for feasibility satisfy the rational enclosures

0.6428409359<Z<0.6428409360,1.1978096052<μ<1.1978096053,0.1504386142<δ3<0.1504386143,\begin{aligned} 0.6428409359&<Z<0.6428409360,\\ 1.1978096052&<\mu<1.1978096053,\\ 0.1504386142&<\delta_3<0.1504386143, \end{aligned}

and the exact cap extrema are

rmin⁡=272727273108,rmax⁡=298960373108.r_{\min} = \frac{272727273}{10^{8}}, \qquad r_{\max} = \frac{298960373}{10^{8}}.

These enclosures imply 3(rmax⁡−1)δ3<μ3(r_{\max}-1)\delta_{3}<\mu. Moreover, r−r/(r−1)r-r/(r-1) is increasing for r>1r>1, so

4(rmax⁡−1)3rmax⁡−2<87<240209≤rmin⁡−rmin⁡rmin⁡−1.\frac{4(r_{\max}-1)}{3r_{\max}-2}<\frac{8}{7}<\frac{240}{209}\leq r_{\min}-\frac{r_{\min}}{r_{\min}-1}.

Normalisation, the cumulative-weight condition, and domination follow from Lemma 12 and (C.5). The cap construction also gives 2<ri<32<r_i<3 and αi+ki≤ri\alpha_i+k_i\leq r_i. Hence all hypotheses of Lemma 9 hold.

The companion verifier computes these finite sums and comparisons exactly. For rational u≥0u\geq0, it obtains ⌊u⌋\lfloor\sqrt{u}\rfloor by an integer square root. Likewise, the cap condition r≥r(αi)r\geq r(\alpha_i) is equivalent to

r≥3011,r≥αi+22,r\geq\frac{30}{11}, \qquad r\geq\frac{\alpha_i+2}{2},
r2−(αi+2)r+αi≥0,r2≥ξ+ξ−αiη.r^{2}-(\alpha_i+2)r+\alpha_i\geq0, \qquad r^{2}\geq\xi+\frac{\xi-\alpha_i}{\eta}.

Thus neither the square roots nor the displayed decimal enclosures introduce a floating-point assumption.

References

  1. [1]C.-Y. Chen and C.-P. Chu. ‘A 3.42-approximation algorithm for scheduling malleable tasks under precedence constraints’. In: IEEE Transactions on Parallel and Distributed Systems 24.8 (2013), pp. 1479–1488. DOI: 10.1109/TPDS.2012.258.DOI
  2. [2]C.-Y. Chen. ‘An improved approximation for scheduling malleable tasks with precedence constraints via iterative method’. In: IEEE Transactions on Parallel and Distributed Systems 29.9 (2018), pp. 1937–1946. DOI: 10.1109/TPDS.2018.2813387.DOI
  3. [3]C.-Y. Chen. Speedup-aware rounding for scheduling malleable tasks with precedence constraints. arXiv preprint arXiv:2611.15111v1. 2026. URL: https://arxiv.org/abs/2611.15111v1.
  4. [4]R. L. Graham. ‘Bounds for certain multiprocessing anomalies’. In: Bell System Technical Journal 45.9 (1966), pp. 1563–1581. DOI: 10.1002/j.1538-7305.1966.tb01709.x.DOI

Paper details

vlnc:W_8x5jq8v8
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

GPT-6 Astra (bare)

View statement
Looking for related papers…
Contents