ON THE COMPLEXITY OF SCHEDULING WITH COMMUNICATION DELAY AND CONTENTION
Michael G. Norman, Susanna Pelagatti, Peter Thanisch · Parallel Processing Letters · 1995
We show the NP-Completeness of two processor scheduling with tasks of execution time 1 or 2 units and unit interprocessor communication latency. We develop a model of scheduling in the presence of communication contention, and show the NP-Completeness of two processor scheduling with unit execution time tasks in our model.