New complexity results on scheduling with small communication delays

Although most of the scheduling problems with interprocessor communication delays have been shown to be NP-complete, some important special cases were still unsolved. This paper deals with the problem where communication times are smaller than processing times and task duplication is not allowed. We prove that this problem is NP-complete and we give an efficient approximate algorithm with performance guarantee.