近年來，雲端工作流排程常面臨任務執行時間高度不確定的問題。真實雲端叢集的延遲現象時常呈現高度右偏的重尾分佈 (如 Pareto 分佈)。當環境極度不穩定 (形狀參數 α ≤ 2) 時，傳統依賴「變異數」進行風險評估的風險感知排程演算法會因數學發散而失效。此外，為防禦錯誤與延遲風險所採用的主動任務複製策略，容易在有限的資源下引起資源排擠與後繼任務無法解鎖的拓樸飢餓，導致整體完工時間反增。
為解決上述挑戰，本研究針對異質環境提出結合風險權重與主動任務複製的 PTAR(Pareto and Topology-Aware Replication) 排程演算法。首先，針對變異數發散問題，本研究使用模糊邏輯與分級平均積分表示法解模糊化，賦予任務能夠兼顧平均預期時間與重尾風險的優先權重。其次，本研究推導了異質環境下雙副本聯合執行時間的期望值，並建立「成本效益決策不等式」，藉由評估截斷極端延遲的預期時間收益與搶占資源的機會成本，作為觸發複製策略的決策依據。
透過真實世界工作流資料集進行的蒙地卡羅模擬實驗顯示，本研究之風險權重能夠將平均誤差百分比控制在 -2.11%。在排程與複製效能上，相較於全域複製與風險分群策略，PTAR 在極端隨機環境中達成了最高的有效複製率 46.45%，並且在受限的資源環境中實現了最低的排成長度比 16.29。本研究有效將有限算力利用於高風險的節點上，顯著提升了排程精準度與強韌性。

Cloud workflow scheduling frequently encounters highly uncertain task execution times that exhibit right-skewed heavy-tail behavior, such as the Pareto distribution. Traditional variance-based risk-aware algorithms fail under extreme instability (shape parameter ≤ 2) due to mathematical divergence. Furthermore, active task replication causes resource contention and topological starvation under limited resources, increasing the overall makespan. This study proposes the PTAR (Pareto and Topology-Aware Replication) algorithm to minimize makespan in heterogeneous environments.
To resolve variance divergence, PTAR employs fuzzy logic and Graded Mean Integration Representation (GMIR) defuzzification. This assigns priority weights that balance the average expected time and extreme heavy-tail risks. Additionally, PTAR establishes a cost-benefit decision inequality by deriving the joint expected execution time of dual replicas. This dynamically triggers replication by weighing the expected time benefit of truncating extreme delays against the opportunity cost of resource preemption.
Monte Carlo simulations on real-world workflow datasets show the proposed risk weight tightly controls the Mean Percentage Error (MPE) at -2.11%. Compared to global replication and risk-clustering strategies, PTAR achieves the highest Effective Duplication Rate (EDR) of 46.45% in highly random environments and realizes the lowest Schedule Length Ratio (SLR) of 16.29 under constrained computing resources. Conclusively, PTAR strategically invests limited computing power into high-risk nodes, significantly improving scheduling accuracy and robustness without inducing topological starvation.

[1] Ishfaq Ahmad and Yu-Kwong Kwok. On exploiting task duplication in parallel program scheduling. IEEE Transactions on Parallel and Distributed Systems, 9(9):872–892, 1998.
[2] Ishtiaq Ahmed, Saeid Mofrad, Shiyong Lu, Changxin Bai, Fengwei Zhang, and Dunren Che. Seed: Confidential big data workflow scheduling with intel sgx under deadline constraints. In IEEE International Conference on Services Computing, pages 108–115. IEEE, 2020.
[3] Hamid Arabnejad and Jorge G Barbosa. List scheduling algorithm for heterogeneous systems by an optimistic cost table. IEEE Transactions on Parallel and Distributed Systems, 25(3):682–694, 2013.
[4] Anne Benoit, Ümit V Çatalyürek, Yves Robert, and Erik Saule. A survey of pipelined workflow scheduling: Models and algorithms. ACM Computing Surveys, 45(4):1–36, 2013.
[5] Anne Benoit, Mourad Hakem, and Yves Robert. Fault tolerant scheduling of precedence task graphs on heterogeneous platforms. In IEEE International Symposium on Parallel and Distributed Processing, pages 1–8. IEEE, 2008.
[6] Shishir Bharathi, Ann Chervenak, Ewa Deelman, Gaurang Mehta, Mei-Hui Su, and Karan Vahi. Characterization of scientific workflows. In Third Workshop on Workflows in Support of Large-Scale Science, pages 1–10. IEEE, 2008.
[7] Rodrigo N Calheiros and Rajkumar Buyya. Meeting deadlines of scientific workflows in public clouds with tasks replication. IEEE Transactions on Parallel and Distributed Systems, 25(7):1787–1796, 2013.
[8] Louis-Claude Canon and Emmanuel Jeannot. Evaluation and optimization of the robustness of dag schedules in heterogeneous environments. IEEE Transactions on Parallel and Distributed Systems, 21(4):532–546, 2009.
[9] Shan-Huo Chen and Chih Hsun Hsieh. Graded mean integration representation of generalized fuzzy number. Journal of the Chinese Fuzzy Systems Association, 1999.
[10] Jeffrey Dean and Luiz André Barroso. The tail at scale. Communications of the ACM, 56(2):74–80, 2013.
[11] Sheng Di, Derrick Kondo, and Franck Cappello. Characterizing and modeling cloud applications/jobs on a google data center. The Journal of Supercomputing, 69(1):139–160, 2014.
[12] Hamza Djigal, Jun Feng, Jiamin Lu, and Jidong Ge. Ippts: An efficient algorithm for scientific workflow scheduling in heterogeneous computing systems. IEEE Transactions on Parallel and Distributed Systems, 32(5):1057–1071, 2020.
[13] Tianyou Guo, Jun Xu, Xiaohui Yan, Jianpeng Hou, Ping Li, Zhaohui Li, Jiafeng Guo,and Xueqi Cheng. Ease the process of machine learning with dataflow. In ACM International on Conference on Information and Knowledge Management, pages 2437–2440. ACM, 2016.
[14] Boontee Kruatrachue and Ted Lewis. Grain size determination for parallel processing. IEEE Software, 5(1):23–32, 2002.
[15] Yu-Kwong Kwok and Ishfaq Ahmad. Static scheduling algorithms for allocating directed task graphs to multiprocessors. ACM Computing Surveys, 31(4):406–471, 1999.
[16] Kenli Li, Xiaoyong Tang, Bharadwaj Veeravalli, and Keqin Li. Scheduling precedence constrained stochastic tasks on heterogeneous cluster systems. IEEE Transactions on computers, 64(1):191–204, 2013.
[17] Qian Ren and Guangshun Yao. A hybrid fault-tolerant workflow scheduling with performance fluctuated cloud resources. IEEE Transactions on Services Computing, 2025.
[18] Xiaoqi Ren, Ganesh Ananthanarayanan, Adam Wierman, and Minlan Yu. Hopper: Decentralized speculation-aware cluster scheduling at scale. ACM SIGCOMM Comput. Commun. Rev., 45(4):379–392, 2015.
[19] Amrith Rajagopal Setlur, S Jaya Nirmala, Har Simrat Singh, and Sudhanshu Khoriya. An efficient fault tolerant workflow scheduling approach using replication heuristics and checkpointing in the cloud. Journal of Parallel and Distributed Computing, 136:14–28, 2020.
[20] Gilbert C Sih and Edward A Lee. A compile-time scheduling heuristic for interconnection-constrained heterogeneous processor architectures. IEEE Transactions on Parallel and Distributed Systems, 4(2):175–187, 1993.
[21] Xiaoyong Tang, Kenli Li, Guiping Liao, Kui Fang, and Fan Wu. A stochastic scheduling algorithm for precedence constrained tasks on grid. Future Generation Computer Systems, 27(8):1083–1091, 2011.
[22] Haluk Topcuoglu, Salim Hariri, and Min-You Wu. Performance-effective and low-complexity task scheduling for heterogeneous computing. IEEE Transactions on Parallel and Distributed Systems, 13(3):260–274, 2002.
[23] Jeffrey D Ullman. Np-complete scheduling problems. Journal of Computer and System sciences, 10(3):384–393, 1975.
[24] Laurens Versluis, Roland Mathá, Sacheendra Talluri, Tim Hegeman, Radu Prodan, Ewa Deelman, and Alexandru Iosup. The workflow trace archive: Open-access data from public and private computing infrastructures. IEEE Transactions on Parallel and Distributed Systems, 31(9):2170–2184, 2020.
[25] Da Wang, Gauri Joshi, and Gregory Wornell. Using straggler replication to reduce latency in large-scale parallel computing. ACM SIGMETRICS Performance Evaluation Review, 43(3):7–11, 2015.
[26] Huanle Xu and Wing Cheong Lau. Optimization for speculative execution in big data processing clusters. IEEE Transactions on Parallel and Distributed Systems, 28(2):530–545, 2016.
[27] Maotong Xu, Sultan Alamro, Tian Lan, and Suresh Subramaniam. Chronos: A unifying optimization framework for speculative execution of deadline-critical mapreduce jobs. pages 718–729. IEEE, 2018.
[28] Guangshun Yao, Yongsheng Ding, and Kuangrong Hao. Using imbalance characteristic for fault-tolerant workflow scheduling in cloud systems. IEEE Transactions on Parallel and Distributed Systems, 28(12):3671–3683, 2017.
[29] Lei Yu, Liuhua Chen, Zhipeng Cai, Haiying Shen, Yi Liang, and Yi Pan. Stochastic load balancing for virtual resource management in datacenters. IEEE Transactions on Cloud Computing, 8(2):459–472, 2016.
[30] Amelie Chi Zhou, Weilin Xue, Yao Xiao, Bingsheng He, Shadi Ibrahim, and Reynold Cheng. Taming system dynamics on resource optimization for data processing workflows: A probabilistic approach. IEEE Transactions on Parallel and Distributed Systems, 33(1):231–248, 2021.