𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Scheduling with parallel processors and linear delay costs

✍ Scribed by Kenneth R. Baker; Alan G. Merten

Publisher
John Wiley and Sons
Year
1973
Tongue
English
Weight
649 KB
Volume
20
Category
Article
ISSN
0894-069X

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

This paper deals with the sequencing problem of minimizing linear delay costs with parallel identical processors. The theoretical properties of this m‐machine problem are explored, and the problem of determining an optimum scheduling procedure is examined. Properties of the optimum schedule are given as well as the corresponding reductions in the number of schedules that must be evaluated in the search for an optimum. An experimental comparison of scheduling rules is reported; this indicates that although a class of effective heuristics can be identified, their relative behavior is difficult to characterize.

πŸ“œ SIMILAR VOLUMES

Parallel Algorithms with Processor Failu
Parallel Algorithms with Processor Failures and Delays
✍ Jonathan F. Buss; Paris C. Kanellakis; Prabhakar L. Ragde; Alex Allister Shvarts πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 367 KB

We study efficient deterministic parallel algorithms on two models: restartable fail-stop CRCW PRAMs and asynchronous PRAMs. In the first model, synchronous processes are subject to arbitrary stop failures and restarts determined by an on-line adversary and involving loss of private but not shared m

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