last update: 17.11.98 (SK)         http://www.mathematik.uni-osnabrueck.de/research/OR/class

Job-shop problems with preemption

• maximal polynomially solvable:

  $J \vert prec;r_i;n=2;pmtn \vert \sum w_iU_i$	Sotskov (1991) [5]
  $J \vert prec;r_i;n=2;pmtn \vert \sum w_iT_i$	Sotskov (1991) [5]

• maximal pseudopolynomially solvable:

  $J \vert prec;r_i;n=k;pmtn \vert \sum w_iU_i$	Middendorf & Timkovsky (1999) [4]
  $J \vert prec;r_i;n=k;pmtn \vert \sum w_iT_i$	Middendorf & Timkovsky (1999) [4]

• minimal NP-hard:

  	$J2 \vert n=3;pmtn \vert C_{max}$	Brucker et al. (1999B) [1]
  $*$	$J2 \vert pmtn \vert C_{max}$	Lenstra & Rinnooy Kan (1979) [3]
  	$J2 \vert n=3;pmtn \vert \sum C_i$	Brucker et al. (1999B) [1]
  $*$	$J2 \vert pmtn \vert \sum C_i$	Lenstra (-) [2]