Task scheduling with interprocessor communication delays

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