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


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.

  pdf file (gzipped)
other papers about this subject
Last update: March 9, 2010.