BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TN-97-58
       ENTRY:: August 18, 1997
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Precedence Constrained Scheduling to Minimize Weighted 
               Completion Time on a Single Machine.
        TYPE:: Technical Note
      AUTHOR:: Chekuri, Chandra
      AUTHOR:: Motwani, Rajeev
        DATE:: August 1997
       PAGES:: 6
    ABSTRACT:: We consider the problem of scheduling a set of jobs on 
               a single machine with the
               objective of mimizing weighted (average) completion time.  
               The problem is NP-hard
               when there are precedence constraints between jobs, [12] 
               and we provide a simple and efficient combinatorial 
               2-approximation algorithm. In contrast to our work,
               earlier approximation altorithms [9] achieving the same
               ratio are based on solving a linear programming relaxation
               of the problem. 
       NOTES:: [Adminitrivia V1/Prg/19970624]
         END:: STAN//CS-TN-97-58