Research Article

Uncertainty aware heuristic scheduling for resource constrained distributed data processing

Authors

Min-Chul Park * Department of Mechanical Design Engineering, Korea Advanced Institute of Engineering Design (KAIED), Daejeon, Republic of Korea.
Seo-Yeon Kim Department of Mechanical Design Engineering, Korea Advanced Institute of Engineering Design (KAIED), Daejeon, Republic of Korea.
Alessandro Conti Dipartimento di Meccanica, Politecnico di Milano, Milano, Italy.
Samar Q. Hassan Department of Industrial Engineering, Jordan University of Science and Technology, Irbid, Jordan.
Pieter J. De Wit Department of Mechanical Engineering, KU Leuven, Leuven, Belgium.

https://doi.org/10.48313/uda.v3i4.115

Downloads

Abstract

Distributed task scheduling under variable durations requires distinguishing local risk-aware placement from a workflow-level deadline guarantee. We formulate a chance-constrained scheduling framework and examine reported results for CHARM, a restricted quantile-guided heuristic on 100 random layered Directed Acyclic Graphs (DAGs) of 30–60 tasks and an eight-worker heterogeneous cluster. Worker calibration traces inform per-task placement and a bounded local repair pass. At log-normal noise σ = 0.3, mean realized makespan is 9.80 time units versus 9.94 for a Heterogeneous Earliest Finish Time (HEFT) assignment evaluated under common dispatch semantics, a 1.4% reduction, with nominal makespan 8.07 versus 7.82. The fraction exceeding 1.1 times each method's own nominal makespan is 0.797 versus 0.891; this method-dependent threshold is a plan-relative measure rather than a common external deadline. Removing the local chance gate raises realized makespan by 0.13 and the plan-relative exceedance fraction by 0.029. Removing local repair leaves the displayed realized mean unchanged. The experiment does not certify the workflow chance constraint, evaluate runtime rescheduling, or test production traces. Reported statistical results and duration conventions require raw-outcome verification, including an inconsistency in the miss-probability signed-rank summary.

Keywords

Task scheduling Uncertainty Chance constraints Heterogeneous computing Makespan robustness Heterogeneous earliest finish time

References (20)

[1] Deelman, E., Vahi, K., Juve, G., Rynge, M., Callaghan, S., Maechling, P. J., … ., & Wenger, K. (2015). Pegasus, a workflow management system for science automation. Future generation computer systems, 46, 17–35. https://doi.org/10.1016/j.future.2014.10.008

[2] Juve, G., Chervenak, A., Deelman, E., Bharathi, S., Mehta, G., & Vahi, K. (2013). Characterizing and profiling scientific workflows. Future generation computer systems, 29(3), 682–692. https://doi.org/10.1016/j.future.2012.08.015

[3] Topcuoglu, H., Hariri, S., & Wu, M.-Y. (2002). Performance-effective and low-complexity task scheduling for heterogeneous computing. IEEE transactions on parallel and distributed systems, 13(3), 260–274. https://doi.org/10.1109/71.993206

[4] Reiss, C., Tumanov, A., Ganger, G. R., Katz, R. H., & Kozuch, M. A. (2012). Heterogeneity and dynamicity of clouds at scale: Google trace analysis. Proceedings of the third ACM symposium on cloud computing (pp. 1–13). Association for Computing Machinery. https://doi.org/10.1145/2391229.2391236

[5] Pinedo, M. L. (2012). Scheduling: Theory, algorithms, and systems. Springer. https://doi.org/10.1007/978-1-4614-2361-4

[6] Möhring, R. H., Schulz, A. S., & Uetz, M. (1999). Approximation in stochastic scheduling: The power of LP-based priority policies. Journal of theassociation for computing machinery,, 46(6), 924–942. https://doi.org/10.1145/331524.331530

[7] Kwok, Y. K., & Ahmad, I. (1999). Static scheduling algorithms for allocating directed task graphs to multiprocessors. ACM computing surveys., 31(4), 406–471. https://doi.org/10.1145/344588.344618

[8] Prékopa, A. (1995). Stochastic programming. Springer. https://doi.org/10.1007/978-94-017-3087-7

[9] Bertsimas, D., & Sim, M. (2004). The price of robustness. Operations research, 52(1), 35–53. https://doi.org/10.1287/opre.1030.0065

[10] Ben-Tal, A., Nemirovski, A., & El Ghaoui, L. (2009). Robust optimization. Princeton university press. https://doi.org/10.1515/9781400831050

[11] Boucheron, S., Lugosi, G., & Massart, P. (2013). Concentration inequalities: A nonasymptotic theory of independence. Oxford University Press. https://doi.org/10.1093/acprof:oso/9780199535255.001.0001

[12] Gelman, A., Carlin, J. B., Stern, H. S., & Rubin, D. B. (2013). Bayesian data analysis. Chapman and hall/cRc. https://doi.org/10.1201/b16018

[13] Abrishami, S., Naghibzadeh, M., & Epema, D. H. J. (2013). Deadline-constrained workflow scheduling algorithms for Infrastructure as a Service Clouds. Future generation computer systems, 29(1), 158–169. https://doi.org/10.1016/j.future.2012.05.004

[14] Mao, M., & Humphrey, M. (2011). Auto-scaling to minimize cost and meet application deadlines in cloud workflows. Proceedings of 2011 international conference for high performance computing, networking, storage and analysis. New York, NY, USA: Association for Computing Machinery. https://doi.org/10.1145/2063384.2063449

[15] Harris, C. R., Millman, K. J., van der Walt, S. J., Gommers, R., Virtanen, P., Cournapeau, D., … ., & Oliphant, T. E. (2020). Array programming with NumPy. Nature, 585(7825), 357–362. https://doi.org/10.1038/s41586-020-2649-2

[16] Virtanen, P., Gommers, R., Oliphant, T. E., Haberland, M., Reddy, T., Cournapeau, D., … ., & Contributors, S. 1. . (2020). SciPy 1.0: Fundamental algorithms for scientific computing in Python. Nature methods, 17(3), 261–272. https://doi.org/10.1038/s41592-019-0686-2

[17] Seabold, S., Perktold, J., & others. (2010). Statsmodels: Econometric and statistical modeling with python. Proceedings of the python in science conference (pp. 92–96). SciPy. https://doi.org/10.25080/Majora-92bf1922-011

[18] Wilcoxon, F. (1945). Individual comparisons by ranking methods. Biometrics bulletin, 1(6), 80–83. https://doi.org/10.2307/3001968

[19] Demšar, J. (2006). Statistical comparisons of classifiers over multiple data sets. Journal of machine learning research, 7(1), 1–30. https://jmlr.org/papers/v7/demsar06a.html

[20] Holm, S. (1979). A simple sequentially rejective multiple test procedure. Scandinavian journal of statistics, 6(2), 65–70. https://www.jstor.org/stable/4615733

Article Metrics

Published 2026-12-16
Issue Vol. 3 No. 4 (2026): Uncertainty Discourse and Applications
Section Articles
Document Type Research Article
Views 0
Downloads 0

How to Cite

Park, M.-C., Kim, S.-Y., Conti, A., Hassan, S. Q., & De Wit, P. J. (2026). Uncertainty aware heuristic scheduling for resource constrained distributed data processing. Uncertainty Discourse and Applications, 3(4), 272-284. https://doi.org/10.48313/uda.v3i4.115

Download Citation

Similar Articles

Pratyasha Dash, Kshitish Kumar Mohanta, Enhancing project scheduling with neutrosophic sets: New solution approaches for solving neutro-sophic CPM/PERT , Uncertainty Discourse and Applications: Vol. 2 No. 2 (2025): Uncertainty Discourse and Applications
M Navya Pratyusha, Ranjan Kumar, Advancements in critical path method using neutrosophic theory: A review , Uncertainty Discourse and Applications: Vol. 1 No. 1 (2024): Uncertainty Discourse and Applications
Aniekan Essienubong Ikpe, Imoh Ime Ekanem, Ikechukwu Bismark Owunna, Application of brute force algorithm optimization as an industrial hotspot in inventory management and control , Uncertainty Discourse and Applications: Vol. 1 No. 2 (2024): Uncertainty Discourse and Applications
Sanaz Hami Hassan Kiyadeh, Ramin Goudarzi Karim, Habibeh Karimi, Interval width fuzzy aggregation for streaming process monitoring on the Tennessee Eastman benchmark , Uncertainty Discourse and Applications: Vol. 3 No. 3 (2026): Uncertainty Discourse and Applications
Janardan Behera, Dynamic stochastic-fuzzy optimization for inventory decision systems under mixeduncertainty , Uncertainty Discourse and Applications: Vol. 3 No. 1 (2026): Uncertainty Discourse and Applications
Abolfazl Fereydoni, Seyedeh Fatemeh Faghidian, Fractional-order general Type-2 fuzzy control with adaptive type-reduction for load frequency control in multi-area renewable-based power systems with communication delays , Uncertainty Discourse and Applications: Vol. 3 No. 3 (2026): Uncertainty Discourse and Applications
Ismail A Mageed, Challenges, unresolved open problems, and next-generation entropy hydrology , Uncertainty Discourse and Applications: Vol. 2 No. 4 (2025): Uncertainty Discourse and Applications
Mohammed Ayedh, Wajahat Ali, An AI-and fuzzy-logic-based framework for climate change adaptation and environmental resilience in Yemen , Uncertainty Discourse and Applications: Vol. 3 No. 2 (2026): Uncertainty Discourse and Applications
Mohamed H. Abdelati, A hybrid Genetic Algorithm for solving fuzzy facility location problems with mixed-integer programming , Uncertainty Discourse and Applications: Vol. 2 No. 4 (2025): Uncertainty Discourse and Applications
Phi-Hung Nguyen, Lan-Anh Thi Nguyen, Duc-Minh Vu, Tra-Giang Vu, Anh-Phuong Nguyen-Danh, Thi-Lien Nguyen, Assessing stakeholder preferences in carbon credit systems with neutrosophic DELPHI and DEMATEL , Uncertainty Discourse and Applications: Vol. 2 No. 2 (2025): Uncertainty Discourse and Applications

1-10 of 66 Next

You may also start an advanced similarity search for this article.