Single-machine scheduling with deteriorating jobs and learning effects to minimize the makespan

Xiuli Wang and T.C. Edwin Cheng
European Journal of Operational Research
Volume 178, Issue 1 , 1 April 2007, Pages 57-70
http://dx.doi.org/10.1016/j.ejor.2006.01.017

1機械スケジューリングで，makespan (処理完了時刻) の最小化．
次の2つの効果を考えている．
1つ目は，ジョブの処理開始が遅れるとどんどんとジョブの処理時間が長くなる効果 (deterioration effect)．
もう1つは，ジョブの処理開始を遅くすればするほどジョブの処理時間が短くなる効果 (learning effect)．
この2つを同時に考えた場合をモデル化している．
彼らのモデル化した問題がNP困難かどうかは分かっていないようだが，多項式時間で解けるいくつかの場合を特定し，実際にアルゴリズムを与えている．