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

Multiprocessor task problems with parallel processors

• maximal polynomially solvable:

  $P \vert outtree;r_i;p_i=p \vert C_{max}$	Brucker et al. (1977) [5]
  $P \vert tree;p_i=p \vert C_{max}$	Hu (1961) [19], Davida & Linton (1976) [12]
  $P2 \vert prec;p_i=p;size_i \vert C_{max}$	Lloyd (1981) [25]
  $Pm \vert r_i;p_i=p;size_i \vert C_{max}$	Baptiste (2003B) [1]
  $P \vert chains;r_i;p_i=1 \vert L_{max}$	Dror et al. (1998) [13], Baptiste et al. (2004) [2]
  $P \vert intree;p_i=p \vert L_{max}$	Brucker et al. (1977) [5], Monma (1982) [26]
  $P2 \vert prec;r_i;p_i=1 \vert L_{max}$	Garey & Johnson (1977) [17]
  $P \vert \vert \sum C_i$	Bruno et al. (1974) [10]
  $P \vert outtree;p_i=p \vert \sum C_i$	Hu (1961) [19]
  $P \vert outtree;r_i;p_i=1 \vert \sum C_i$	Brucker et al. (2002) [6]
  $P2 \vert prec;p_i=p \vert \sum C_i$	Coffman & Graham (1972) [11]
  $Pm \vert intree;p_i=p \vert \sum C_i$	Baptiste et al. (2004) [2]
  $Pm \vert r_i;p_i=p;size_i \vert \sum C_i$	Baptiste (2003B) [1]
  $P \vert r_i;p_i=p \vert \sum w_iC_i$	Brucker & Kravchenko (2008) [9]
  $Pm \vert p_i=p;size_i \vert \sum w_iC_i$	Drozdowski & Dell' Olmo (2000) [14]
  $P2 \vert r_i;p_i=1;size_i \vert L_{max}$	Baptiste & Schieber (2003) [3]
  $Pm \vert r_i;p_i=p \vert \sum w_iU_i$	Baptiste et al. (2004) [2]
  $Pm \vert p_i=p;size_i \vert \sum w_iU_i$	Brucker et al. (2000) [7]
  $P \vert r_i;p_i=p \vert \sum T_i$	Brucker & Kravchenko (2005) [8]
  $Pm \vert p_i=p;size_i \vert \sum T_i$	Brucker et al. (2000) [7]
  $P \vert p_i=p \vert \sum w_iU_i, \sum w_iT_i$	Assignment-problem
  $P \vert r_i;p_i=1 \vert \sum w_iU_i, \sum w_iT_i$	Networkflowproblem

• maximal pseudopolynomially solvable:

  $P3 \vert size_i \vert C_{max}$	Du & Leung (1989) [15]
  $Pm \vert r_i \vert C_{max}$, $Pm \vert \vert \sum w_iC_i$, $Pm \vert \vert \sum w_iU_i$	Lawler et al. (1989) [20]

• minimal NP-hard:

  	$P2 \vert \vert C_{max}$	Lenstra et al. (1977) [24]
  $*$	$P \vert \vert C_{max}$	Garey & Johnson (1978) [18]
  $*$	$P \vert intree;r_i;p_i=1 \vert C_{max}$	Brucker et al. (1977) [5]
  $*$	$P \vert p_i=1;size_i \vert C_{max}$	Lloyd (1981) [25]
  $*$	$P \vert prec;p_i=1 \vert C_{max}$	Ullman (1975) [28]
  $*$	$P2 \vert chains \vert C_{max}$	Du et al. (1991) [16]
  $*$	$P2 \vert chains;r_i;p_i=1;size_i \vert C_{max}$	Brucker et al. (2000) [7]
  $*$	$P2 \vert r_i;size_i \vert C_{max}$	Lee & Cai (1999) [21]
  $*$	$P3 \vert chains;p_i=1;size_i \vert C_{max}$	Blazewicz & Liu (1996) [4]
  $*$	$P5 \vert size_i \vert C_{max}$	Du & Leung (1989) [15]
  $*$	$P \vert outtree;p_i=1 \vert L_{max}$	Brucker et al. (1977) [5]
  $*$	$P2 \vert chains;p_i=1;size_i \vert L_{max}$	Brucker et al. (2000) [7]
  $*$	$P2 \vert size_i \vert L_{max}$	Lee & Cai (1999) [21]
  	$P2 \vert size_i \vert \sum C_i$	Lee & Cai (1999) [21]
  $*$	$P \vert intree;r_i;p_i=1 \vert \sum C_i$	Lenstra (-) [22]
  $*$	$P \vert p_i=1;size_i \vert \sum C_i$	Drozdowski & Dell' Olmo (2000) [14]
  $*$	$P \vert prec;p_i=1 \vert \sum C_i$	Lenstra & Rinnooy Kan (1978) [23]
  $*$	$P2 \vert chains \vert \sum C_i$	Du et al. (1991) [16]
  $*$	$P2 \vert intree;p_i=1;size_i \vert \sum C_i$	Zinder & Do (2005) [29]
  $*$	$P2 \vert outtree;p_i=1;size_i \vert \sum C_i$	Zinder et al. (2005) [30]
  $*$	$P2 \vert r_i \vert \sum C_i$	Single-machine problem
  	$P2 \vert \vert \sum w_iC_i$	Bruno et al. (1974) [10]
  $*$	$P \vert \vert \sum w_iC_i$	Lenstra (-) [22]
  $*$	$P2 \vert chains;p_i=1 \vert \sum w_iC_i$	Timkovsky (1998) [27]
  $*$	$P2 \vert size_i \vert \sum w_iC_i$	Lee & Cai (1999) [21]
  $*$	$P2 \vert chains;p_i=1 \vert \sum U_i, \sum T_i$	Single-machine problem

• minimal open:

  $P2 \vert r_i;p_i=p;size_i \vert L_{max}$
  $Pm \vert r_i;p_i=1;size_i \vert L_{max}$
  $P2 \vert chains;p_i=1;size_i \vert \sum C_i$

  $P2 \vert r_i;p_i=1;size_i \vert \sum w_iC_i$
  $P2 \vert r_i;p_i=1;size_i \vert \sum U_i$

  $P2 \vert r_i;p_i=1;size_i \vert \sum T_i$
  $P2 \vert p_i=1;size_i \vert \sum w_iT_i$

• maximal open:

  $Pm \vert chains;r_i;p_i=p;size_i \vert \sum C_i$

  $Pm \vert r_i;p_i=p;size_i \vert \sum w_iU_i$

  $Pm \vert r_i;p_i=p;size_i \vert \sum w_iT_i$