𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Scheduling chains on uniform processors with communication delays

✍ Scribed by Wieslaw Kubiak1; Bernard Penz; Denis Trystram

Publisher
Springer US
Year
2002
Tongue
English
Weight
200 KB
Volume
5
Category
Article
ISSN
1094-6136

No coin nor oath required. For personal study only.

✦ Synopsis

We show that the problem of scheduling chains of unit execution time (UET) jobs on uniform processors with communication delays to minimize makespan is NP-hard in the strong sense. We also give a heuristic that generates solutions with known, and relatively small, absolute error for this problem. The NP-hardness result holds even for the case without communication delays, and complements the earlier result of Gonzalez and Sahni who gave a polynomial time algorithm for preemptive jobs of arbitrary length.

We also study the structure of optimal solutions for the two processor problem of scheduling chains of UET jobs with communication delays, where one processor is a (integer) times faster than the other. This investigation leads to a linear time optimization algorithm for this case.

πŸ“œ SIMILAR VOLUMES

The Complexity of Scheduling Trees with
The Complexity of Scheduling Trees with Communication Delays
✍ Jan Karel Lenstra; Marinus Veldhorst; Bart Veltman πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 190 KB

We consider the problem of finding a minimum-length schedule on m machines for a set of n unit-length tasks with a forest of intrees as precedence relation, and with unit interprocessor communication delays. First, we prove that this problem is NP-complete; second, we derive a linear time algorithm

EM-ML PET reconstruction on multiple pro
EM-ML PET reconstruction on multiple processors with reduced communications
✍ SΓΈren P. Olesen; Jens Gregor; Michael G. Thomason; Gary T. Smith πŸ“‚ Article πŸ“… 1996 πŸ› John Wiley and Sons 🌐 English βš– 811 KB

Positron emission tomography (PET) reconstruction by the EM algorithm is an iterative computation of Poisson emission rates to maximize a likelihood function. The method is time consuming and, for real scanner data, requires large numerical arrays. To speed up the computation on multiple processors

Communication-Efficient Sorting Algorith
Communication-Efficient Sorting Algorithms on Reconfigurable Array of Processors With Slotted Optical Buses
✍ Mounir Hamdi; Chunming Qiao; Yi Pan; J. Tong πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 222 KB

The reconfigurable array with slotted optical buses (RASOB) has recently received a lot of attention from the research community. In this paper, we first discuss the reconfiguration methods and communication capabilities of the RASOB architecture. Then, we use this architecture for the implementatio