Single-machine scheduling with periodic maintenance to minimize makespan

by Min Ji, Yong He and T.C.E. Cheng
Computers & Operations Research
Volume 34, Issue 6 , June 2007, Pages 1764-1770 http://dx.doi.org/10.1016/j.cor.2005.05.034

1機械スケジューリングで、定期的にmaintenanceを行なう場合の近似アルゴリズムについて。
ジョブが途中中断を許さないとすると、maintenance時刻に近付くとジョブが割り当てられなくなる。
そのときにmakespan(全てのジョブが完了するまでの時間)の最小化を考える。
この問題がすぐにbin packingと同じ構造を持っていることは分かるが、目的関数が少しだけ違う。
しかし、bin packingにおけるいわゆるfirst fit法 (processing timeが長いジョブから割り当てる) を行なうと、2近似になることを示している。(これはタイト)
また、PがNPと等しくなければ、近似比が2よりもよい多項式時間アルゴリズムが存在しないことも示している。
これにもう少し現実的であろう条件を付け加えたり、一般化することで、色々な変種を考えることができるので、何かできそうな気がする。