Resource allocation of DAWs using mathematical programming

Scientific Workflows are high-level programs that consist of tasks connected by control structures and data dependencies. They are a popular way of modeling and executing large-scale and complex data analysis tasks. In the following, we will call them data analysis workflows (DAWs). DAWs are executed on distributed infrastructures by a scheduler who decides which tasks are executed when on which node while obeying the dependencies of the workflow. The workflow scheduling problem is NP-hard, even without additional requirements such as deadlines and budget constraints. One popular way of solving scheduling problems is the usage of mathematical programming, in which available resources, data dependencies, additional constraints, and optimization goals are modeled in mathematical terms that allow for the application of general solvers to find optimal solutions. These models provide a deep insight into the problem being evaluated and also enable us to consider secondary preferences and to perform a post-optimality analysis to determine the most preferred solution among equally optimal alternatives. In this chapter, we give an introduction into mathematical programming for optimization problems and explain its usage for workflow scheduling. We compare different concrete approaches to the problem and highlight important aspects by means of four concrete case studies.