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

Multiprocessor task problems with dedicated processors

• maximal polynomially solvable:

  $P2 \vert fix_i \vert C_{max}$	Hoogeveen et al. (1994) [6]
  $Pm \vert r_i;p_i=1;fix_i \vert C_{max}$	Brucker & Kraemer (1996) [4]
  $Pm \vert r_i;p_i=1;fix_i \vert \sum C_i$	Brucker & Kraemer (1996) [4]
  $Pm \vert p_i=1;fix_i \vert \sum w_iC_i$	Brucker & Kraemer (1996) [4]
  $Pm \vert p_i=1;fix_i \vert \sum w_iU_i$	Brucker & Kraemer (1996) [4]
  $Pm \vert p_i=1;fix_i \vert \sum T_i$	Brucker & Kraemer (1996) [4]

• minimal NP-hard:

  $*$	$P \vert p_i=1;fix_i \vert C_{max}$	Hoogeveen et al. (1994) [6]
  $*$	$P2 \vert chains;p_i=1;fix_i \vert C_{max}$	Hoogeveen et al. (1994) [6], Blazewicz et al. (1983) [3]
  $*$	$P2 \vert r_i;fix_i \vert C_{max}$	Hoogeveen et al. (1994) [6]
  $*$	$P3 \vert fix_i \vert C_{max}$	Blazewicz et al. (1992) [1], [2], Hoogeveen et al. (1994) [6]
  $*$	$P2 \vert fix_i \vert L_{max}$	Hoogeveen et al. (1994) [6]
  $*$	$P \vert p_i=1;fix_i \vert \sum C_i$	Hoogeveen et al. (1994) [6]
  $*$	$P2 \vert fix_i \vert \sum C_i$	Hoogeveen et al. (1994) [6], Cai et al. (1998) [5]
  $*$	$P2 \vert chains;p_i=1;fix_i \vert \sum C_i$	Hoogeveen et al. (1994) [6], Blazewicz et al. (1983) [3]

• minimal open:

  $P2 \vert r_i;p_i=1;fix_i \vert L_{max}$
  $P2 \vert r_i;p_i=1;fix_i \vert \sum w_iC_i$
  $P2 \vert p_i=1;fix_i \vert \sum w_iT_i$

• maximal open:

  $Pm \vert r_i;p_i=1;fix_i \vert \sum w_iU_i$
  $Pm \vert r_i;p_i=1;fix_i \vert \sum w_iT_i$