Approximability of single machine scheduling with fixed jobs to minimize total completion time

J.J. Yuan, Y.X. Lin, C.T. Ng and T.C.E. Cheng
European Journal of Operational Research
Volume 178, Issue 1 , 1 April 2007, Pages 46-56
http://dx.doi.org/10.1016/j.ejor.2006.01.025

1機械スケジューリングで，いくつかのジョブのスケジュールが固定されていて，release dateがあり，先行制約　 (precedence constraint)もある場合の問題を考察．目的関数はtotal completion time．
この問題の近似保証について詳細に調べている．以後，nはジョブの数．
まず，preemption (割込み) のない場合．
線形時間n近似アルゴリズムが存在 (固定ジョブがすべて処理され，他のジョブがすべてreleaseされたら，先行制約に従う任意の順序で休みなくジョブを処理させるアルゴリズム)．
P≠NPならば，擬多項式時間(1-ε)n近似アルゴリズムは存在しない (3-partitionより)．
その他，割込みのある場合や重み付きの場合なども含めて，いろいろな結果が報告されている．