ON THE COMPLEXITY OF SCHEDULING WITH COMMUNICATION DELAY AND CONTENTION

Michael G. Norman,Susanna Pelagatti,Peter Thanisch

ON THE COMPLEXITY OF SCHEDULING WITH COMMUNICATION DELAY AND CONTENTION

1995

Michael G. Norman
Susanna Pelagatti
Peter Thanisch

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.

Keywords:

Deadline-monotonic scheduling
Parallel computing
Fair-share scheduling
Distributed computing
Earliest deadline first scheduling
Real-time computing
Two-level scheduling
Computer science
Rate-monotonic scheduling
Fixed-priority pre-emptive scheduling
Round-robin scheduling
Dynamic priority scheduling

Correction
Source
Cite
Save
Machine Reading By IdeaReader

References

Citations