TASK-SCHEDULING WITH INTERPROCESSOR COMMUNICATION DELAYS

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.