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 -approximation. Independently and concurrently with our work, Chen obtained a -approximation for the full convex model and a -approximation for concave speedup. We give a deterministic polynomial-time -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 , identical processors, and positive rational processing times for every job and every integer . A schedule chooses an allocation and a start time for each job. Job occupies processors throughout . At every time, the total number of occupied processors is at most , and for every . The objective is to minimise the makespan .
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 and ,
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 -approximation for every number of processors, where
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 -approximation for arbitrary precedence constraints. Jansen and Zhang [JZ06] improved this factor to by refining the relaxation and rounding analysis. Chen [2] subsequently studied an iterative LP method for this general monotone model, reporting a factor of after two iterations and factors approaching 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 -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 -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 -approximation for the general convex-frontier model and a -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 ; Appendix § 7 handles 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 .
The Algorithm
Write , 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 ; 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 , define the set of retained allocations
These are the smallest allocations attaining each duration, so the values for are distinct. We preserve the original processor counts: consecutive elements of 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 is the continuous piecewise-linear interpolation through the points for . We call the table convex if is convex on . 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.

Figure 1. A processing-time table and its convex duration–work frontier. Allocation is dominated by , which has the same duration and less work. The black points correspond to ; the segments interpolate between them. For example, duration combines allocations and with equal weights and has fractional work , 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 and each retained allocation , introduce a weight . Let and be the fractional duration and work, respectively, and let 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:
The constraints 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 ; Lemma 4 proves this implication. The LP has polynomial size.
Take an optimal LP solution and consider each job’s duration . As a convex combination of retained durations, need not itself equal a retained duration. If for some , replace the job’s weights by weight one on allocation and call the job integral. Otherwise, there is a unique pair of consecutive elements of satisfying . Set
and set all other weights to zero; call this job fractional. This replacement preserves and, by convexity, does not increase , as proved in Lemma 4. Hence it remains optimal. From now on, denotes the work after this replacement.
For a fractional job , the allocations are its slower and faster retained allocations, respectively. Write , so that . The corresponding durations and LP values satisfy
The slower duration plateau runs from allocation through . When considering several jobs, we write and for their retained allocations. Monotonicity of work at allocations and gives
This estimate is the reason for requiring consecutive retained allocations.
Rounding, Capping, and List Scheduling
We construct a finite family of schedules from the same optimal LP solution, represented as above. Choose thresholds and cap parameters , indexed by . We leave these pairs and the family size unspecified until § 4. Define
For a single run , write and . We round and cap the LP solution as follows. For an integral job , let be its retained allocation. For a fractional job , use its slower and faster retained allocations and from (3). The final allocation is
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 . 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 schedules. Algorithm 1 summarises the complete algorithm.
Algorithm 1 Threshold Rounding with Processor Caps
Require: An instance with ; pairs with and
Remove dominated allocations and solve the LP (2).
Compute , , and from (5).
for do
Round jobs to allocations using (6).
Construct a list schedule using durations .
end for
return a schedule of minimum makespan among .
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 . Every feasible solution satisfies
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 times the makespan, so these values are LP feasible and .
For a directed path , the LP constraints give and for . Adding these inequalities yields
For each retained allocation , monotonicity of work and give . Taking the convex combination specified by the LP proves the individual work bounds; the total-work bound is an LP constraint.
An LP duration is a convex combination of retained durations and need not itself be a retained duration. If for some , assign weight one to allocation . Otherwise, choose the unique consecutive elements of satisfying and assign weights
to allocations and , respectively. This preserves . Let be the piecewise-linear duration-work function from Definition 3. Its convexity gives, for the original weights,
The new weights attain , 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 and processor allocations , and use the list scheduling rule from § 2.1. Write for the resulting makespan, and define
where is the work of job at its assigned allocation.
Lemma 5. There is a directed path such that
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 . 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 , at least processors are busy. All jobs executing in the intervals under consideration lie outside . By an area argument, the total length of these intervals is at most . The remaining part of 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 is the smallest processor cap in (5). Using the faster retained allocation of each fractional job, define
We call the jobs in thin and those in wide. A thin job has both retained allocations at most . The wide jobs are exactly the integral jobs and the fractional jobs with . In particular, an integral job belongs to regardless of its processor allocation. The partition depends only on the LP solution and , so it is the same in every run.
Consider a single run with threshold and integer cap . Write for the allocation selected by threshold rounding (before the min-operation in (6)) and for the final allocation. A job is capped precisely when . Using the notation above for these final allocations, put
Thus is the LP work of the wide jobs, whereas 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
Proof. A thin job satisfies , so it is never capped. For a fractional wide job, the notation in (3) and the adjacency bound give
It therefore selects its slower allocation, whose work is at most . An integral job has work before capping. Since capping cannot increase work, every wide job has final work .
Define for thin jobs and for wide jobs. Then in both cases. Apply Lemma 5, replace each off-path work term by , and write the off-path sum as the total sum minus the path sum:
For a thin job , , and its allocation is unchanged by the cap. Threshold rounding therefore gives , so its contribution in parentheses is at most . The same bound holds for a wide job whose selected allocation is at most : its allocation is also unchanged, and .
Every remaining path job is capped and wide. Its final allocation is , so the final-work bound just proved gives . Its contribution in parentheses is therefore at most . Since , this is at most
Sum over the path, apply its duration bound in (7), and bound the additional capped-path work by . Adding gives (10).
Averaging across Runs
We analyse the work obtained by rounding each job with the threshold choices. Let be the work of job after rounding with the original threshold , before capping. Assign nonnegative weights to the threshold choices, with , and use the same weights for every job. For a fixed job , these weights define an average of its work across the threshold choices. Our aim is to find conditions under which
where is a target work factor. Throughout this analysis, sums over range over unless explicitly restricted.
An integral job has work under every threshold. For a fractional job , use the notation in (3): threshold selects the faster allocation precisely when , and selects the slower allocation otherwise. Its weighted work therefore depends only on the total weight assigned to the faster choice. We control this quantity by bounding the weight of thresholds below each value by a function . 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 and imposing the processor caps cannot increase work, so the resulting work guarantee also applies to the actual runs.
Write and, for , define
and set . The function is nondecreasing, because 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 on the weight assigned to faster choices.
Lemma 7 (8K). For all , every integer , and every with , we have
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 times the job’s LP work, where is the target work factor used to define .
Lemma 8. Let satisfy . Suppose thresholds and nonnegative weights satisfy
Then, for every job ,
This inequality remains valid if any thresholds are increased.
Proof. An integral job has work in every rounding, so its weighted work is , as required by (14). For a fractional job , use (3) and put
The slower allocation has work , while the faster allocation has work . The faster allocation is chosen precisely for the thresholds counted by ; the remaining weight selects the slower allocation. Dividing the weighted rounded work by therefore gives
In the LP representation (3), the weights on the slower and faster allocations are and . Dividing the LP duration equation by yields
Since , the LP weight on the faster allocation is . Using these weights to compute the LP work and then dividing by , we obtain
Equations (15) and (16) express both normalised work quantities as weighted averages of the same two values, and . The faster allocation has weight after rounding and in the LP; in each case, the slower allocation receives the remaining weight.
Since , monotonicity of work gives , and hence . If , both retained allocations have the same work. Therefore
Thus the target inequality (14) holds regardless of the rounding choices.
Now suppose . Our goal is , as stated in (14). Dividing this inequality by and substituting (15) and (16) shows that it is equivalent to
Subtracting from both sides of (17) and dividing by gives, with ,
Since , we have . Also by (4). If , condition (13) and Lemma 7, with and , prove (18). If , apply the same lemma with and . Its right-hand side equals , and . Consequently the right-hand side of (18) is at least . 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 average job work, while average schedule makespans. The algorithm returns the shortest schedule, whose makespan is at most this average.
Fix rational thresholds and cap parameters , indexed by . Let be rational weights with . For a real number , write , and define
Lemma 9. Assume that for every job , and that a number satisfies
For every , the algorithm of § 2 with these threshold-cap pairs returns a schedule of makespan at most
Proof. For each run , we apply the makespan bound (10) from Lemma 6. We then average these bounds with weights . Let , , and be as in (5), and abbreviate
Since and , we have .
Use the fixed partition from (9). Since and , Lemma 6 applies to every run with this same partition. In particular, thin jobs are uncapped and wide jobs have final work at most in every run.
Since , we have . Thus
and hence . We also have , so . Since , we have and therefore
To prepare for averaging the makespan bounds, set
Then and . In the makespan bound (10), the duration term and the wide-job work term, after division by , can be rewritten as
The following two claims will bound the weighted averages of the coefficients of and by and , respectively.
Claim 1. The weighted average of the threshold coefficients satisfies
Proof of Claim 1. Raising the thresholds from to increases their weighted average by
We show that the factors compensate for this increase. Because and ,
Combining with and the second condition in (19), we obtain
Using (21), we therefore obtain
This proves the claim, since . ■
Claim 2. For every run ,
Proof of Claim 2. If , the threshold is unchanged, so . Since and ,
Taking the maximum proves (24) in this case. If , the threshold is raised to . In this case we show that both entries of the maximum are at most . Since , it suffices to show that . By (21),
The second inequality uses . For the third, the preceding fraction equals , which decreases with because ; we use . The last inequality is the final condition in (19). Thus whenever the threshold is raised. Since also , both entries of the maximum are at most , proving (24) in the remaining case. ■
We now bound the average contribution of thin jobs and then average the makespan bounds. Let be the final work of the thin jobs in run . Recall that is the work of job after rounding with the original threshold , before capping. Raising the threshold to 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 . Multiplying by , summing over runs, and then applying the assumed work bound to each job in the fixed set gives
The makespan bounds use the schedule weights and the coefficients . We relate them to this work average as follows:
The first inequality uses , which follows from the cap bound (20). The second uses , 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 just proved.
Let be the makespan of the schedule from run . Dividing (10) by and using the rewriting (22) gives, for every run,
The algorithm returns the shortest of these schedules. Since and , its makespan is at most their weighted average: . Moreover, is the same in every run because it is defined using the LP work of the fixed set . Multiplying the per-run bounds by and summing therefore gives
By (25) and the definition of , the last term satisfies
Claim 1 bounds the first weighted coefficient by . Claim 2, together with , bounds the second by . Since and , we can apply these bounds to obtain
The second inequality uses and . The last follows because is a convex combination of and , as . 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
The choices are , any finite number of pairs with and , probability weights , and . They must satisfy the cumulative-weight condition (13) and the domination and finite-processor conditions (19). The quantities and are defined before Lemma 9: bounds the thin-job contribution and 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 . For , we set , place thresholds uniformly between and , and use increments of the envelope as work weights. The cap curve (C.1) trades path inflation against capacity, while schedule weights proportional to enforce domination. The Python search varies and and adjusts 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 , 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
Both coefficients lie strictly between and .
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 . By Lemma 12, the weights give the average-work bound with factor . Equation (C.5) supplies the domination condition for the schedule weights. Lemma 10 verifies the remaining hypotheses of Lemma 9. Moreover, for every , so . Thus the returned schedule satisfies
For , Lemma 11 in Appendix § 7 supplies a schedule of length at most . 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 , 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- 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 , execute all jobs sequentially on one processor in a topological order. For , 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 , the procedures above return a schedule of length at most .
Proof. If , the sequential schedule has length
Now let . Rounding every fractional job to its slower endpoint gives duration at most , because , and work at most . Capping at two preserves the work bound. Put and apply Lemma 5, bounding every final work by :
A job assigned one processor was not capped, and its path contribution is at most . A job assigned two processors satisfies , and its path contribution is at most , since . Using the path and work bounds in (7), we obtain
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 . Then , and the expression becomes
For positive denominators, the Cauchy–Schwarz inequality gives
For , the right-hand side is , which is one of the required envelope terms. Now let . The expression is strictly convex in and tends to infinity as decreases to zero. If its minimum on is at , that minimum is
the integer envelope term with .
Otherwise the minimum is attained in the interior. Solving the derivative equation shows that its value and the condition for an interior minimiser are
In this case we compare with the integer term for . The difference is
The interior condition gives , and for . 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
The middle term ensures . The last term is chosen to balance the objective coefficients and ; the first supplies slack for the finite-processor conditions. For the exact construction, fix
The constants , , and control the threshold grid and the two rational rounding precisions. They are independent of the input instance. For , set
To keep the cumulative work weights below , round them down. Set , , and, for ,
Here . Let . The cutoff 64 is valid for these particular constants, as justified below.
Lemma 12. The weights are nonnegative, sum to one, and satisfy (13). Consequently, they give average rounded work at most for each job.
The proof below checks that the rounded cumulative weights are nondecreasing and remain below the envelope.
Let be the smallest multiple of that is at least from (C.1). To preserve the domination condition after this rounding, now use the rational values
The downward rounding of ensures . Therefore , the weights sum to one, and
Thus we may still use . Moreover, , so also remains valid.
The Envelope Endpoint and the Cumulative Weights
First consider the general search parameter . With and , we have
Thus the square-root entry of equals . The difference between consecutive integer entries is
At this is positive for every , because and . The smallest integer entry is therefore
This proves throughout the search range. For the constants used in the paper, and .
Proof of Lemma 12. Every expression defining is nondecreasing in , and is nondecreasing in . Taking minima and floors preserves this property. Since every is at most , the final choice preserves it as well. Consequently , and telescoping gives .
We next justify restricting the integer minimum to . Direct substitution of the fixed constants gives . For every and every , the difference between consecutive integer entries is therefore positive:
Hence no omitted entry is smaller than the entry with . The other rounded entry satisfies
It follows that for ; at the same statement holds with equality because .
Finally fix . If no threshold is strictly below , the required cumulative bound is immediate. Otherwise let be the largest index with . Then , and
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
Direct rational comparisons show that
The other quantities needed for feasibility satisfy the rational enclosures
and the exact cap extrema are
These enclosures imply . Moreover, is increasing for , so
Normalisation, the cumulative-weight condition, and domination follow from Lemma 12 and (C.5). The cap construction also gives and . Hence all hypotheses of Lemma 9 hold.
The companion verifier computes these finite sums and comparisons exactly. For rational , it obtains by an integer square root. Likewise, the cap condition is equivalent to
Thus neither the square roots nor the displayed decimal enclosures introduce a floating-point assumption.
References
- [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]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]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]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