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

Multiprocessor task problems with dedicated processors and preemption

• maximal polynomially solvable:

  $Pm \vert r_i;pmtn;fix_i \vert L_{max}$	Bianco et al. (1997) [1]
  $P2 \vert pmtn;fix_i \vert \sum C_i$	Cai et al. (1998) [2]

• maximal pseudopolynomially solvable:

• minimal NP-hard:

  $*$	$P \vert pmtn;fix_i \vert C_{max}$	Hoogeveen et al. (1994) [3], Kubale (1990) [4]
  $*$	$P2 \vert chains;pmtn;fix_i \vert C_{max}$	Hoogeveen et al. (1994) [3]
  $*$	$P \vert pmtn;fix_i \vert \sum C_i$	Hoogeveen et al. (1994) [3]
  $*$	$P2 \vert chains;pmtn;fix_i \vert \sum C_i$	Hoogeveen et al. (1994) [3]
  $*$	$P2 \vert pmtn;fix_i \vert \sum w_iC_i$	Oguz & Qi (2006) [5]

• minimal open:

  $P2 \vert r_i;pmtn;fix_i \vert \sum C_i$
  $P3 \vert pmtn;fix_i \vert \sum C_i$
  $P2 \vert pmtn;fix_i \vert \sum U_i$
  $P2 \vert pmtn;fix_i \vert \sum T_i$

• maximal open:

  $Pm \vert r_i;pmtn;fix_i \vert \sum w_iU_i$
  $Pm \vert r_i;pmtn;fix_i \vert \sum T_i$