Günter Rote:
A parallel scheduling algorithm for minimizing the number of unscheduled
jobs
In: "Parallel Algorithms & Architectures". Proceedings of the International
Workshop on Parallel Algorithms and Architectures, Centre National de
Rencontres Mathématiques, Luminy, France, April 14–18, 1986.
Editors: M. Cosnard, Y. Robert, P. Quinton, and M. Tchuente.
North-Holland, 1986, pp. 99–108, (Zbl 639.68031).
Abstract
We consider the problem of scheduling n jobs with different
processing times on one machine subject to a common release date and
different due-dates, in order to maximize the number of jobs that are
finished on time. The well-known Moore-Hodgson algorithm from 1968 is the most
efficient sequential algorithm and runs in O(n log n)
time. We present a parallelization of this algorithm with takes
O(log2n) time on n2 processors in the single
instruction stream, multiple data stream (SIMD) shared memory model without
write conflicts but with read conflicts allowed.
Our approach is based on the
binary tree method of Dekel and Sahni (Binary trees and parallel scheduling
algorithms, IEEE Transactions on Computers C-32, 1983). It requires a
thorough analysis of the behavior of the sequential algorithm. We show that a
parallel algorithm of Dekel and Sahni for the same scheduling problem relies
on an erroneous assumption.
Last update: March 9, 2010.