Computing workflows in heterogeneous multiprocessor systems are frequently
modeled as directed acyclic graphs of tasks and data blocks, which represent
computational modules and their dependencies in the form of data produced by a
task and used by others. However, for some workflows, such as the task schedule
in a digital signal processor may run out of memory by exposing too much
parallelism. This paper focuses on the data allocation and task scheduling
problem under memory constraints, and concentrates on shared memory platforms.
We first propose an integer linear programming model to formulate the problem.
Then we consider the problem as an extended flexible job shop scheduling
problem, while trying to minimize the critical path of the graph. To solve this
problem, we propose a tabu search algorithm (TS) which combines several
distinguished features such as a greedy initial solution construction method
and a mixed neighborhood evaluation strategy based on exact evaluation and
approximate evaluation methods. Experimental results on randomly generated
instances show that the the proposed TS algorithm can obtain relatively
high-quality solutions in a reasonable computational time. In specific, the
tabu search method averagely improves the makespan by 5-25% compared to the
classical load balancing algorithm that are widely used in the literature.
Besides, some key features of TS are also analyzed to identify its success