Volume 5, Issue 6 pp. 459-476
Research Article

Scheduling chains on uniform processors with communication delays

Wieslaw Kubiak1

Corresponding Author

Wieslaw Kubiak1

Memorial University of Newfoundland, Faculty of Business Administration, St John's Newfoundland A1B 3X5, Canada

Memorial University of Newfoundland, Faculty of Business Administration, St John's Newfoundland A1B 3X5, CanadaSearch for more papers by this author
Bernard Penz

Bernard Penz

GILCO, ENSGI-INPG, 46 avenue F. Viallet 38031 Grenoble Cedex 1, France

Search for more papers by this author
Denis Trystram

Denis Trystram

ID-IMAG, ENSIMAG - antenne de Montbonnot ZIRST 51, avenue Jean Kuntzmann 38330 Montbonnot Saint Martin, France

Search for more papers by this author
First published: 07 November 2002
Citations: 10

Abstract

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. Copyright © 2002 John Wiley & Sons, Ltd.

The full text of this article hosted at iucr.org is unavailable due to technical difficulties.