๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

The Complexity of Scheduling Trees with Communication Delays

โœ Scribed by Jan Karel Lenstra; Marinus Veldhorst; Bart Veltman

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
190 KB
Volume
20
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

โœฆ Synopsis

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 for the special case that m equals 2.

๐Ÿ“œ SIMILAR VOLUMES

Scheduling chains on uniform processors
Scheduling chains on uniform processors with communication delays
โœ Wieslaw Kubiak1; Bernard Penz; Denis Trystram ๐Ÿ“‚ Article ๐Ÿ“… 2002 ๐Ÿ› Springer US ๐ŸŒ English โš– 200 KB

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. Th

The complexity of cyclic shop scheduling
The complexity of cyclic shop scheduling problems
โœ Nicholas G. Hall; Tae-Eog Lee; Marc E. Posner ๐Ÿ“‚ Article ๐Ÿ“… 2002 ๐Ÿ› Springer US ๐ŸŒ English โš– 190 KB

We consider scheduling problems for shops in which a job set is manufactured repetitively. Jobs are scheduled to minimize the cycle time of the job set, which is equivalent to maximizing the throughput rate. We characterize the complexity of the scheduling problem for several types of job shops. Pol

The complexity of two group scheduling p
The complexity of two group scheduling problems
โœ Jacek Blazewicz; Mikhail Y. Kovalyov ๐Ÿ“‚ Article ๐Ÿ“… 2002 ๐Ÿ› Springer US ๐ŸŒ English โš– 94 KB

The problems of scheduling groups of jobs under the group technology assumption are studied. The two remaining open questions posed in the literature a decade ago about the computational complexity of these problems (J. Oper. Res. Soc., 1992; 43:395 -406), are answered. The parallel machine problem

The Communication Complexity of Pointer
The Communication Complexity of Pointer Chasing
โœ Stephen J. Ponzio; Jaikumar Radhakrishnan; S. Venkatesh ๐Ÿ“‚ Article ๐Ÿ“… 2001 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 253 KB

We study the k-round two-party communication complexity of the pointer chasing problem for fixed k. C. Damm, S. Jukna and J. Sgall (1998, Comput. Complexity 7, 109 127) showed an upper bound of O(n log (k&1) n) for this problem. We prove a matching lower bound; this improves the lower bound of 0(n)

The Communication Complexity of Enumerat
The Communication Complexity of Enumeration, Elimination, and Selection
โœ Andris Ambainis; Harry Buhrman; William Gasarch; Bala Kalyanasundaram; Leen Tore ๐Ÿ“‚ Article ๐Ÿ“… 2001 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 278 KB

Let k, n ยฅ N and f: {0, 1} n ร— {0, 1} n Q {0, 1}. Assume Alice has x 1 , ..., x k ยฅ {0, 1} n , Bob has y 1 , ..., y k ยฅ {0, 1} n , and they want to compute municating as few bits as possible. The direct sum conjecture (henceforth DSC) n (log log(n))(log(n)) ) bits. This establishes a weak randomize