Institution: Stanford University, Department of Computer Science

Title: An almost-optimal algorithm for the assembly line scheduling problem.

Author: Kaufman, Marc T.

Date: January 1973

Abstract: This paper considers a solution to the multiprocessor scheduling problem for the case where the ordering relation between tasks can be represented as a tree. Assume that we have n identical processors, and a number of tasks to perform. Each task $T_i$ requires an amount of time ${\mu}_i$ to complete, 0 < ${\u}_i \leq$ k, so that k is an upper bound on task length. Tasks are indivisible, so that a processor once assigned must remain assigned until the task completes (no preemption). Then the "longest path" scheduling method is almost-optimal in the following sense: Let $\omage$ be the total time required to process all of the tasks by the "longest path" algorithm. Let ${\omega}_o$ be the minimal time in which all of the tasks can be processed. Let ${\omega}_p$ be the minimal time to process all of the tasks if arbitrary preemption of processors is allowed. Then: ${\omega}_p \leq {\omega}_o \leq \omega \leq {\omega}_p$ + k - k/n, where n is the number of processors available to any of the algorithms.

http://i.stanford.edu/pub/cstr/reports/cs/tr/73/350/CS-TR-73-350.pdf