Feedback and Requirement Biasing for Enhancing Robustness of Scheduling Algorithms for Distributed System Processing - Grounds, Nicolas (My University, 2018)
Scheduling tasks in a distributed system (e.g., cloud computing) in order to optimize an objective such as minimizing deadline misses has been a topic of research for decades. Such a problem is proven NP Complete even with perfect knowledge of tasks' requirements and their arrivals to the distributed system for processing. However, a realistic approach to distributed systems scheduling as part of a cloud computing service provider requires development of scheduling algorithms that can accomodate tasks arriving dynamically having requirements that are not accurately known. In this dissertation, a framework is proposed for handling dynamic scheduling of tasks where scheduling algorithms decision-making is based on execution within a modeled system of modeled tasks with inaccurate requirements with respect to the actual tasks running on an actual system. Tasks are arranged into directed-acyclic graphs representing execution precedence constraints called workflows, which have a known deadline or time by which all contained tasks should complete processing. Various scheduling algorithms are evaluated and compared using simulation software (simulating both the model and actual systems) according to their ability to complete workflows relative to their deadline as well as their robustness to the amount of error in the model tasks' requirements. Simulation conditions are varied with respect to the amount of error in model tasks' requirements. Finally, feedback from the actual system to the model system regarding task processing completion and model error biasing techniques are evaluated and shown to be useful in enhancing the robustness of scheduling algorithms to model errors.
Keywords: scheduling; distributed processing; robustness