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
factors.

本文主要研究在共享内存平台下内存限制下数据分配和任务调度问题，提出了一个整数线性规划模型和基于禁忌搜索算法的可行解决方案，并在随机生成的实例上验证了该方法的有效性。