BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-73-350
       ENTRY:: September 25, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: An almost-optimal algorithm for the assembly line scheduling
               problem.
        TYPE:: Technical Report
      AUTHOR:: Kaufman, Marc T.
        DATE:: January 1973
       PAGES:: 26
    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.
       NOTES:: [Adminitrivia V1/Prg/19950925]
         END:: STAN//CS-TR-73-350