Uncertainty Aware Heuristic Scheduling for Resource Constrained Distributed Data Processing

2.1 Deterministic Directed Acyclic Graph and List Scheduling

List scheduling assigns task priorities and places ready tasks greedily; Kwok and Ahmad [7] survey deterministic graph scheduling. HEFT uses upward ranks based on average durations and insertion-based earliest finish [3]. Stochastic priority-policy analysis addresses related random-duration scheduling problems [6], while textbook treatments establish the broader theory [5]. The problems and guarantees of those sources are not transferred to the heterogeneous DAG heuristic tested here.

The deterministic methods considered here consume point processing-time estimates and produce schedules quickly. CHARM retains a list-scheduling structure and uses empirical worker multipliers to guide placement. Broader stochastic scheduling literature already studies uncertain durations; the proposed comparison concerns this specific computational construction rather than a universal distinction between deterministic and uncertainty-aware methods.

Insertion, duplication, and lookahead alter how a list scheduler allocates tasks [7]. These design choices can interact with duration models. The reported comparison evaluates static assignment and worker priority under a shared dispatcher, so it does not directly compare all insertion schedules as constructed or establish that uncertainty treatment is independent of dispatch semantics.

2.2 Scheduling under Uncertainty

Stochastic scheduling analyses priority policies under random processing times [5], [6]. Chance-constrained programming expresses a requirement that a constraint hold with a specified probability [8]. Robust optimization protects against a specified uncertainty set [9], [10]. Concentration inequalities support sampling error bounds under their assumptions [11], and Bayesian modelling offers methods for estimating predictive distributions [12]. These tools provide a formal context for the general framework.

Closer to systems practice, cloud scheduling research has examined deadline-constrained provisioning, including partial critical-path algorithms for infrastructure-as-a-service clouds [13] and auto-scaling approaches that trade cost against deadlines [14]. These works largely treat the deadline as deterministic given provisioned resources, and uncertainty enters through provisioning margins rather than through the schedule itself. Our position is complementary: we take the cluster as given and resource-constrained, and move the uncertainty treatment inside the scheduling computation, where trace-informed distributions can be exploited rather than padded away.

The reported experiment releases one DAG on a fixed cluster. Online arrivals, queue stability across jobs, and runtime adaptation require separate models and are outside its scope. The static local repair pass should not be interpreted as an evaluated online scheduler.

2.3 Workflow Systems Traces and Simulation

Pegasus and workflow profiling studies supply operational context [1], [2], and production cluster analysis illustrates heterogeneity [4]. The campaign uses synthetic layered DAGs and a custom dispatcher rather than production replay. This allows controlled pairing but leaves operational workload diversity and communication costs untested.

Trace-based evaluation can connect scheduling models to observed task variability. Controlled paired simulation also supports comparisons on identical generated instances. The reported experiment uses common random draws across methods, but only ten realized draws per DAG and noise level, so its per-DAG exceedance estimates are coarse. Production-trace validation and calibration uncertainty remain necessary extensions.

2.4 Synthesis and Positioning

CHARM combines a list-scheduling backbone with distribution-informed placement and repair. The general framework targets a workflow chance constraint; the implemented heuristic uses empirical worker quantiles and a local placement gate. Its reported advantage must be assessed separately from whether it meets an externally specified deadline risk.

3.1 Research Questions and Hypotheses

The research questions concern uncertainty representation, scheduling benefit, and distribution misspecification. The reported experiment addresses restricted versions of them.

RQ1 asks how predictive duration distributions and their estimation uncertainty can inform scheduling. The evaluated implementation uses worker multiplier quantiles rather than a fitted per-class posterior.

RQ2 asks whether risk-aware construction improves realized performance and workflow deadline reliability at an acceptable cost. A common external deadline is required to evaluate the latter directly.

RQ3 asks how performance responds to distribution error, heavy tails, and correlated contention. The reported three-level noise sweep tests only a limited form of distribution shift.

H1 predicts an improvement from risk-aware construction relative to mean-based HEFT. The experiment measures realized makespan and an own-plan exceedance fraction, rather than joint deadline compliance. H2 predicts a benefit from runtime repair. The reported ablation concerns a static local repair pass, so it cannot test runtime rescheduling in its stated form.

H3 predicts controlled degradation as the estimated distribution departs from the true distribution. Three noise levels do not establish linearity in an estimation-error metric, heavy-tail behaviour, or robustness to correlated contention.

These hypotheses distinguish design aims from findings. No verified preregistration record was supplied. Sections 3 and 4 describe the general framework; Section 5 identifies the narrower implementation and evidence.

3.2 System Model and Notation

A job is a DAG G = (T, E) of tasks i in T connected by data edges (i, j) in E. The platform consists of heterogeneous resources r in R, each with a speed normalisation and a resource-time price. The duration of task i on resource r is a random variable D_{i, r} whose distribution is estimated from traces, and the transfer volume along edge (i, j) is likewise random when its endpoints are placed on different resources. The job carries a deadline delta and, optionally, a resource budget B. A schedule s assigns each task to a resource and a start order, and its makespan C_max(s) is the completion time of the final task, itself a random variable induced by the durations. Table 1 lists the principal symbols.

D_{i,r} Random duration of task i on resource r Time units W_{ij} Random transfer volume on edge (i, j) MB R Set of heterogeneous resources - delta Job deadline Time units epsilon Tolerated violation probability - C_max(s) Makespan of schedule s Time units rho_r Resource-time price of resource r Cost/time unit alpha Rank quantile level - z_{1-alpha} Standard normal quantile at level 1-alpha - K Independent draw count for conceptual risk assessment - L_i Latest allowable start of task i Time units

3.3 Formal Problem Statement

A schedule assigns each task to a resource and a nonpreemptive worker order, respecting precedence and at most one executing task per worker. With resource-time price ρ_r, the general problem minimizes expected execution cost subject to a fixed deadline δ and risk tolerance ε:

minimize_s E[Σ_{i∈T} ρ_{s(i)} D_{i,s(i)}]

s.t (1)

Pr{C_max(s) > δ} ≤ ε, precedence and worker nonoverlap constraints.

Eq. (1) is a general chance-constrained model [8]. A simulated exceedance fraction is an estimator of its risk, not automatically a certificate. For a fixed schedule evaluated using K independent draws from a specified model, let p̂_viol be the empirical fraction:

p̂ _viol(s) = K⁻¹ Σ_{k=1}^{K} 1{C_max^(k)(s) > δ}; p̂ _viol(s) + √[log(1/β)/(2K)] ≤ ε. (2)

The margin in Eq. (2) is a one-sided Hoeffding bound at confidence 1−β, where 0 < β < 1, for a fixed schedule under the sampling model [11]. It does not account for misspecified duration laws, estimated model parameters, correlated draws, or repeated adaptive schedule selection. Independent final certification or a simultaneous bound is needed when many candidates are searched. The reported implementation neither uses this workflow certification rule nor demonstrates the deadline guarantee in Eq. (1).

4.1 Framework Overview

The general framework has estimation, construction, and monitoring layers. Estimated duration and transfer models supply schedule candidates; risk evaluation determines whether they meet a fixed deadline; monitoring can initiate rescheduling with updated information. These are conceptual interfaces. The reported implementation uses empirical worker multiplier traces, a local deadline gate, and a static bounded repair pass. Offline estimation and event-triggered updates can reduce runtime overhead, but their cost and calibration must be measured. No production monitoring or runtime-event experiment is reported here.

4.2 Distributional Estimation from Traces

A per-class log-normal model with parameter uncertainty and shrinkage is a possible estimation layer [12]. Such a model would require an estimation procedure, priors, calibration checks, and a predictive distribution before it could support a chance constraint. Empirical quantiles are another option, with uncertainty depending on trace size and relevance. Finite moment diagnostics cannot prove that a distribution has infinite variance. The reported campaign uses 500 multiplier samples per worker at σ_cal = 0.3, without evaluating per-class shrinkage or transfer estimation.

4.3 Chance Aware Construction

A list scheduler can prioritize tasks using a duration score that combines a predictive mean μ with variability σ. Eq. (3) is a normal-quantile surrogate, not a log-normal quantile or a bound on a path maximum:

d̃ _{i,r} = μ_{i,r} + z_{1−α} σ_{i,r}, 0 < α < 1. (3)

For D ∼ LogNormal(a,b²), the exact marginal quantile is exp(a + b z_{1−α}). Summing marginal quantiles does not in general give the same quantile of a sum or workflow makespan. Joint deadline assessment must include precedence, worker queueing, dependence, and communication assumptions. The tested heuristic derives task deadlines from downstream slack and uses empirical worker multiplier quantiles; it does not propagate exact workflow distributions.

If no candidate placement meets a risk requirement, the framework must report infeasibility or use a specified escalation whose revised risk and resource cost are evaluated. Replication or relaxing ε changes the decision problem and cannot silently preserve the original guarantee. A local per-task gate with probability 0.9 does not imply 90% workflow completion probability; a joint certificate or valid allocation of total risk is required.

4.4 Runtime Repair

Runtime repair would condition remaining durations on observed progress and reschedule only unexecuted tasks while respecting completed and running work. Its effectiveness depends on engine support, repair cost, trigger definitions, and re-evaluation of joint risk. This is a proposed extension. The reported repair pass modifies a static schedule using a quantile-inflated makespan estimate, with at most five moves, and does not demonstrate event-driven runtime adaptation.

4.5 The CHARM Algorithm

Algorithm 1 states the general construction-and-monitoring interfaces, not the procedure executed in Section 5. Probability checks refer to independent or simultaneous risk assessment under a specified joint model. The narrower worker-quantile heuristic is described in the experimental setup.

Algorithm 1. Conceptual workflow risk assessment and rescheduling.

Input: DAG G, resources R, fixed deadline δ, risk ε, predictive model, certification confidence 1: fit or load specified predictive models and calibration evidence 2: generate a precedence-feasible schedule using a list heuristic 3: assess workflow risk using independent or simultaneous certification 4: while no admissible schedule has been found do 5: generate a new candidate within a stated search budget 6: verify worker nonoverlap and precedence constraints 7: evaluate expected cost and joint deadline risk 8: if the risk condition is met, retain the candidate 9: if the search budget is exhausted, report failure or an explicit escalation 10: end construction loop; if no admissible schedule exists, report failure and stop 11: otherwise dispatch the retained schedule; optionally monitor execution progress 12: while unfinished work remains do 13: update the conditional duration model without changing completed work 14: if a specified repair trigger is met, generate a feasible remaining-work schedule 15: reassess its risk using the stated certification procedure 16: apply it only within the repair and resource budgets 17: report estimated risk, confidence scope, and any escalation Output: schedule and risk assessment conditional on the supplied model

4.6 Complexity Assumptions and Failure Conditions

A HEFT-style construction has O(|T|²|R|) scheduling cost under its standard implementation. Dense task– resource costs require O(|T||R|) storage, in addition to O(|T|+|E|) graph and schedule state. Simulating K workflow realizations adds the cost of K full dispatch runs; it cannot generally be bounded by only the number of nominal critical paths, because resource contention can change the realized path. Candidate search, model estimation, and repeated repairs multiply these costs. The reported experiment supplies total harness timing, without a separate scheduler-cost benchmark.

The simulation assumes the stated task multipliers and fixed worker factors. Correlated contention requires an explicit joint model and is untested.

Calibration traces must remain relevant to future durations. The outer noise levels intentionally change the multiplier distribution.

Task deadlines derived from slack are heuristic allocations; near-tied paths and queueing can invalidate a local interpretation as a joint guarantee.

Repair requires an explicit move and computation budget. The tested pass allows at most five moves. These conditions define the proposed risk assessment. Monitoring does not by itself establish that every failure regime is detectable or that a cold-start fallback is safe.

Heavy-tailed durations may require empirical or model-based quantiles rather than moment scores; their adequacy must be validated.

Shared contention can couple task durations and defeat an independence-based assessment.

A cold start without defensible duration information leaves reliability unquantified. A conservative schedule cannot be called safe without a justified uncertainty set.

5.1 Setup

The manuscript reports 100 random layered DAGs with one entry and one exit, 30–60 tasks (mean 45.3), 3– 6 middle layers, and inter-layer edge probabilities in [0.2, 0.4]. Eight workers have speed factors in [0.53, 1.91] and fixed noise factors f_w in [0.66, 1.48]. A nominal task duration is base duration divided by speed; realized duration multiplies it by LogNormal(0,σ f_w), with σ ∈ {0.2,0.3,0.4}. Under this reported parameterization the multiplier mean is exp((σ f_w)²/2), greater than one, so the nominal duration is not the stochastic mean. The table label “expected” denotes nominal simulation values here. Whether the code instead centers multipliers requires verification.

Every method is reported as receiving nominal durations and a 500-task multiplier calibration trace per worker at σ_cal = 0.3. CHARM sets T* to 1.05 times the HEFT nominal construction makespan, derives task deadlines from downstream slack, and chooses a worker passing an empirical 90% local finish gate, preferring the earliest median-scaled finish. A static repair pass responds to a quantile-inflated makespan estimate above T*. The exact feasibility fallback, task-deadline formula, and repair moves require the implementation record. The 0.9 task gate is an estimated local condition, not a certified workflow chance constraint.

All methods are evaluated without communication cost by a shared event-driven dispatcher. A static assignment and per-worker priority order are converted into execution by starting the highest-priority ready task on each idle worker. This may differ from HEFT's constructed insertion schedule, so the comparison is between assignments under common dispatch rather than faithful insertion-schedule execution. Ten common random draws per DAG and noise level pair methods. The reported miss fraction uses a different threshold for each method, 1.1 times its own nominal makespan; robustness is exactly one minus that fraction and supplies no independent outcome. No common external deadline or T* compliance is reported. Software references identify NumPy, SciPy, and statsmodels [15–17], and the stated tests use Wilcoxon [18], Demšar [19], and Holm [20].

Cluster 8 heterogeneous workers, speed factors in [0.53, 1.91], realized duration = expected x LogNormal(0, sigma x f_w) with per-worker noise factor f_w in [0.66, 1.48] Information model Schedulers see expected durations only, plus a 500-task calibration trace per worker (empirical multiplier quantiles) taken at sigma_cal = 0.3 Noise levels Sigma in {0.2, 0.3, 0.4}, 10 common-random-number duration draws per DAG and level Methods Random assignment, EFT list scheduling (insertion-based), HEFT (upward rank + insertion-based EFT), static greedy on expected durations, CHARM (deadline from downstream slack, P(finish <= deadline) >= 0.9 via worker quantiles, local repair) Evaluation One shared event-driven simulator (static assignment, dynamic ready dispatch per worker in priority order) scores all methods on expected and realized durations Metrics Expected makespan, realized makespan (mean +/- std), deadline-miss probability P(realized > 1.1 x expected), robustness index P(realized <= 1.1 x expected)

5.2 Main Comparison RQ1 RQ2

At σ = 0.3, Table 3 gives mean realized makespan 9.80 for CHARM and 9.94 for HEFT-based assignment under the shared dispatcher, a reduction of 1.4%. Reported within-DAG standard deviations are 0.94 and 1.02. The source gives paired Wilcoxon W = 1413, p = 0.000132 across 100 DAG means, with CHARM lower on 66 DAGs. The medians are nearly equal, 9.68 and 9.67. Random, EFT, and static greedy have larger realized means. CHARM's nominal makespan is 8.07 versus 7.82 for HEFT, a 3.2% increase. This comparison describes an assignment trade-off under the simulator, rather than an increase in expected monetary or energy cost.

Plan-relative exceedance fractions are 0.797 for CHARM and 0.891 for HEFT; their complementary robustness values are 0.203 and 0.109. CHARM's threshold is larger because its nominal makespan is larger. Random assignment has a smaller exceedance fraction despite much slower execution because its own plan is substantially longer. These values measure conformity to each method's own nominal plan, not the probability of meeting one shared application deadline. The source's signed-rank summary for this comparison is internally inconsistent and remains a verification dependency in Table 7.

5.3 Ablation Which Component Carries the Gain

Removing the local chance gate raises displayed realized makespan from 9.80 to 9.93, with reported W = 1348 and p = 5.19 × 10⁻⁵; its own-plan exceedance fraction rises by 0.029, from 0.797 to 0.826. The ablated nominal makespan (8.04) differs from HEFT's (7.82), so this variant cannot be described as identical to HEFT. Removing static repair leaves both displayed realized means at 9.80 (reported p = 0.69) and changes exceedance fraction from 0.797 to 0.842 while also lowering the nominal plan from 8.07 to 7.93. This change does not by itself establish tail protection at a common threshold. The source reports repair on 46% of DAGs, 0.91 moves per DAG, capped at five. The experiment supports a benefit of the local gate on realized makespan within this design; runtime-repair H2 remains untested.

Table 5 varies target factor γ on the first 30 DAGs. Nominal means range from 8.32 to 8.36, realized means from 10.01 to 10.11, and own-plan exceedance fractions from 0.797 to 0.810. The small variation suggests limited sensitivity in this particular subset and parameter range. It does not establish that the gate saturates or that γ controls external deadline reliability.

5.4 Stress across Noise Levels RQ3

Table 6 and Fig. 2 vary true noise while calibration stays at σ_cal = 0.3. CHARM's realized mean is 8.89 versus HEFT's 8.90 at σ = 0.2, 9.80 versus 9.94 at 0.3, and 11.05 versus 11.33 at 0.4. The gap grows over these three conditions. The multiplier parameterization also changes its mean, so this is not a pure variance or estimation-error experiment. Own-plan exceedance fractions rise for every method; at σ = 0.4 they exceed 0.9 for HEFT and CHARM, but remain 0.662, 0.837, and 0.820 for random, EFT, and greedy. These different thresholds preclude a cross-method deadline-reliability ranking. The sweep does not establish linear degradation, heavy-tail robustness, or correlated-contention performance.

Note (Fig. 2): The inversion between the tight schedules (HEFT worst) and the conservative ones (random best) is the own-expectation artifact discussed in Section 5.2; CHARM sits below HEFT at every level.

5.5 Statistical Analysis

Table 7 retains the reported paired Wilcoxon and Friedman results. The primary realized-makespan comparison uses 100 DAG means, rather than treating 1,000 duration draws as independent instances. A four-comparison CHARM-versus-baseline family uses Holm correction; the source's “five-way family” wording refers to five methods, not five pairwise tests. The miss-probability row reports 54 better and 46 tied DAGs alongside W = 455; for the usual signed-rank statistic, 54 same-direction nonzero differences would have minimum rank sum zero. Raw paired outcomes and the statistic convention are needed to resolve this inconsistency. Displayed p = 0.000 entries denote rounded values, not zero probability. Until regenerated, these statistics remain source-reported calculations rather than independently confirmed tests.

5.6 Discussion Findings Losses and Scope

The reported realized-makespan means favour CHARM over HEFT-based assignment at intermediate and high noise, with a modest nominal-plan increase. The local-gate ablation supports a construction-time effect in this simulation. Static repair has no demonstrated mean effect at the displayed precision, and its own-plan exceedance change cannot establish fixed-deadline tail protection. These are the empirical findings supported The close realized medians and 66 favourable DAGs show that CHARM does not improve every instance. HEFT has the smaller nominal plan, whereas plan-relative exceedance measures adherence to that plan and uses method-dependent thresholds. Target-factor variation is small on the 30-DAG subset. None of these observations provides a certified workflow reliability guarantee or an operating recommendation for a production cluster.

The evidence covers 100 synthetic DAGs, one eight-worker cluster, no communication cost, log-normal multipliers, and a makespan objective. Production traces, correlated stragglers, heavy-tailed models, runtime rescheduling, replication, elasticity, energy, and multi-job fairness are untested. A future experiment should evaluate all schedulers at shared external deadlines and report feasibility, calibration, scheduler overhead, and outcome uncertainty.

The numerical results are reported at proof-of-concept scale. Independent regeneration requires the harness, raw draws, calibration samples, assignments, and execution logs. Resolution of the signed-rank inconsistency remains necessary; a verified release is not specified.

6.1 Limitations

Risk assessment is conditional on a duration model and its calibration. Shared contention can introduce dependence absent from the simulation. Quantiles estimated from 500 samples have sampling uncertainty, and changes in workload or cluster conditions can invalidate them. The local task gate used here is weaker than the joint deadline condition in Eq. (1), while the own-plan exceedance measure does not assess that condition. Small-scale synthetic results cannot certify production reliability.

The general formulation concerns one job on a fixed cluster. Multi-job fairness, preemption, and elasticity require additional constraints. The tested repair pass is static and does not require demonstrated runtime preemption or replication. Runtime extensions should specify engine support and measure their cost.

6.1 Alternative Viewpoints and Responses

Robust optimization protects against an uncertainty set [9], [10], while chance constraints depend on a probability law. Their relative conservatism depends on how the set, law, and risk tolerance are chosen. Neither inherently collapses the risk–cost trade-off to a single setting. A comparison should expose these choices and assess both at shared deadline and resource conditions.

Learned schedulers provide another possible comparator, whose calibration, sample needs, and distribution-shift behaviour require evidence. Transparent local risk scores are inspectable, but are not automatically probability certificates. The reported ablations isolate a static local gate and repair pass, without testing learning-based policies or reactive runtime rescheduling.