TASK-SCHEDULING WITH INTERPROCESSOR COMMUNICATION DELAYS

Philippe Chrétienne

doi:10.1016/0377-2217(92)90346-B

TASK-SCHEDULING WITH INTERPROCESSOR COMMUNICATION DELAYS

1992-03-01

21

PRE

AI

P

Philippe Chrétienne *

DOI：10.1016/0377-2217(92)90346-B

原文链接

原文求助

摘要

En 中文

Distributed memory architectures raise new and complex scheduling problems. In this paper, we first define a basic distributed memory computer scheduling problem issued from an ideal architecture. By proving that the corresponding decision problem is NP-complete, we show that unlike shared memory computer scheduling problems, these new problems do not become easy when the processor limitation constraint is removed. Finally, we improve the knowledge of the borderline between the easy and difficult subproblems of the basic one by giving some polynomial special cases.

Keyword:

SCHEDULING

COMPLEXITY

ALGORITHMS

INTERPROCESSOR COMMUNICATION DELAY

TASK-SCHEDULING WITH INTERPROCESSOR COMMUNICATION DELAYS

摘要

AI总结

期刊

机构

引用论文