|
Mathematical formulation Consider a HC system and a collection of tasks with variable computational requirements, to be executed on the system. Every task is the atomic unit of workload to be assigned to a computation resource, and it cannot be divided in smaller chunks, nor interrupted after an assignment was performed (the scheduling problem follows a non-preemptive model). The HC environment implies that the execution times of any individual task will vary from one machine to others, so there will be a competition among tasks for using the most suited machines in the system (i.e., those machines able to execute each task in the minimum time). The general formulation of any scheduling problem proposes to find an assignment of tasks to machines in order to satisfy some objectives. Given that using the computational resources does not come for free, most scheduling problems mainly concerns about time, trying to minimize the total time spent to execute all tasks. While several characteristics or properties can be assigned to each task (i.e. CPU and memory requirements, priority, execution time deadline, etc.), the simplest model used for scheduling, and also the most common one, considers only the execution time of every single task in each computation resource. So, the most usual metric to minimize in this model is the makespan, defined as the time spent from the instant when the first task begins to execute to the moment when the execution of the last task is completed. However, many other metrics have been considered, such as the economic cost of executing an application, and the quality of service, specially in grids infrastructures [Leung et al., 2004]. Beyond all those single-objective approaches, scheduling is an obvious multiobjective problem when considering several task properties or several metrics in conflict with each other. This work is mainly concerned in optimizing the makespan metric, and the following formulation present the HCSP mathematical model aimed at minimizing the makespan. • Given a HC system composed of a set of computational resources P = {m1,m2, . . . ,mM} (machines, dimension M) , and a collection of tasks T = {t1, t2, . . . , tN} (dimension N) to be executed on the HC system. • Given a execution time function ET : {1 . . .N}×{1, . . . ,M} → R+, where ET(i,j) is the time required to execute the task ti in the machine mj . • The goal of the HSCP aimed at minimizing the makespan is to find an assignment of tasks to machines (a function f : TN → PM) which minimizes
|
|
HCSP |
|
Heterogeneous Computing Scheduling Problem |
|
HSCP mathematical formulation |