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

Parallel machine problems with preemption

• maximal polynomially solvable:

  $P \vert outtree;pmtn;r_i \vert C_{max}$	Lawler (1982) [19]
  $P \vert tree;pmtn \vert C_{max}$	Muntz & Coffman (1970) [28], Gonzalez & Johnson (1980) [13]
  $Q \vert chains;pmtn \vert C_{max}$	Horvath et al. (1977) [14]
  $P \vert intree;pmtn \vert L_{max}$	Lawler (1982) [19]
  $Q2 \vert prec;pmtn;r_i \vert L_{max}$	Lawler (1982) [19]
  $R \vert pmtn;r_i \vert L_{max}$	Lawler & Labetoulle (1978) [21]
  $P2 \vert p_i=p;prec;pmtn \vert \sum C_i$	Coffman et al. (2003) [9]
  $P2 \vert p_i=p;outtree;pmtn;r_i \vert \sum C_i$	Lushchakova (2006) [26]
  $P \vert p_i=1;outtree;pmtn;r_i \vert \sum C_i$	Brucker et al. (2002) [5], Huo & Leung (2005) [15]
  $P \vert p_i=p;outtree;pmtn \vert \sum C_i$	Brucker et al. (2002) [5]
  $Q \vert p_i=p;pmtn;r_i \vert \sum C_i$	Kravchenko & Werner (2009) [16]
  $Q \vert pmtn \vert \sum C_i$	Labetoulle et al. (1984) [17]
  $P \vert p_i=p;pmtn \vert \sum w_iC_i$	McNaughton (1959) [27]
  $Q \vert p_i=p;pmtn \vert \sum U_i$	Baptiste et al. (2004) [3]
  $Qm \vert pmtn \vert \sum U_i$	Lawler (1979) [18], Lawler & Martel (1989) [23]
  $P \vert p_i=1;pmtn;r_i \vert \sum w_iU_i$	Brucker et al. (2003) [4]
  $Pm \vert p_i=p;pmtn \vert \sum w_iU_i$	Baptiste (2000B) [1]
  $P \vert p_i=p;pmtn \vert \sum T_i$	Baptiste et al. (2004) [3]
  $P \vert p_i=1;pmtn;r_i \vert \sum w_iT_i$	Baptiste (2002) [2]

• maximal pseudopolynomially solvable:

  $Pm \vert pmtn \vert \sum w_iC_i$	McNaughton (1959) [27], Lawler et al. (1989) [22]
  $Qm \vert pmtn \vert \sum w_iU_i$	Lawler (1979) [18], Lawler & Martel (1989) [23]

• minimal NP-hard:

  $*$	$P \vert intree;pmtn;r_i \vert C_{max}$	Lenstra (-) [24]
  $*$	$P \vert p_i=1;prec;pmtn \vert C_{max}$	Ullman (1976) [31]
  $*$	$R2 \vert chains;pmtn \vert C_{max}$	Lenstra (-) [24]
  $*$	$P \vert outtree;pmtn \vert L_{max}$	Lenstra (-) [24]
  	$P2 \vert pmtn;r_i \vert \sum C_i$	Du et al. (1990) [11]
  $*$	$P \vert pmtn;r_i \vert \sum C_i$	Brucker & Kravchenko (2004) [7]
  $*$	$P2 \vert chains;pmtn \vert \sum C_i$	Du et al. (1991) [12]
  $*$	$R \vert pmtn \vert \sum C_i$	Sitters (2001) [29]
  	$P2 \vert pmtn \vert \sum w_iC_i$	Bruno et al. (1974) [8]
  $*$	$P \vert p_i=p;pmtn;r_i \vert \sum w_iC_i$	Leung & Young (1990A) [25]
  $*$	$P \vert pmtn \vert \sum w_iC_i$	Lenstra (-) [24]
  $*$	$P2 \vert p_i=1;chains;pmtn \vert \sum w_iC_i$	Timkovsky (2003) [30], Du et al. (1991) [12]
  $*$	$P2 \vert pmtn;r_i \vert \sum w_iC_i$	Labetoulle et al. (1984) [17]
  	$P \vert pmtn \vert \sum U_i$	Lawler (1983) [20]
  	$P2 \vert pmtn;r_i \vert \sum U_i$	Du et al. (1992) [10]
  $*$	$P2 \vert p_i=1;chains;pmtn \vert \sum U_i$	Baptiste et al. (2004) [3]
  $*$	$R \vert pmtn \vert \sum U_i$	Sitters (2001) [29]
  	$P \vert p_i=p;pmtn \vert \sum w_iU_i$	Brucker & Kravchenko (1999) [6]
  	$P2 \vert pmtn \vert \sum w_iU_i$	Single-machine problem

• minimal open:

  $Pm \vert p_i=1;intree;pmtn;r_i \vert C_{max}$
  $Pm \vert p_i=1;prec;pmtn \vert C_{max}$
  $Qm \vert p_i=p;chains;pmtn;r_i \vert C_{max}$
  $Qm \vert p_i=p;intree;pmtn \vert C_{max}$
  $Qm \vert p_i=p;outtree;pmtn \vert C_{max}$
  $Pm \vert p_i=1;chains;pmtn;r_i \vert L_{max}$
  $Pm \vert p_i=1;outtree;pmtn \vert L_{max}$
  $Qm \vert p_i=p;chains;pmtn \vert L_{max}$

  $P2 \vert p_i=1;intree;pmtn;r_i \vert \sum C_i$
  $Pm \vert p_i=p;chains;pmtn;r_i \vert \sum C_i$
  $Pm \vert p_i=1;intree;pmtn \vert \sum C_i$
  $Q2 \vert p_i=p;chains;pmtn \vert \sum C_i$
  $R2 \vert pmtn \vert \sum C_i$
  $P2 \vert p_i=p;pmtn;r_i \vert \sum w_iC_i$
  $Q2 \vert p_i=p;pmtn \vert \sum w_iC_i$

  $P2 \vert p_i=p;pmtn;r_i \vert \sum U_i$
  $R2 \vert pmtn \vert \sum U_i$
  $Q2 \vert p_i=p;pmtn \vert \sum w_iU_i$
  $P2 \vert p_i=1;chains;pmtn \vert \sum T_i$
  $P2 \vert p_i=p;pmtn;r_i \vert \sum T_i$
  $P2 \vert pmtn \vert \sum T_i$
  $Q2 \vert p_i=p;pmtn \vert \sum T_i$
  $P2 \vert p_i=p;pmtn \vert \sum w_iT_i$

• maximal open:

  $Q \vert outtree;pmtn;r_i \vert C_{max}$
  $Q \vert tree;pmtn \vert C_{max}$
  $Q \vert chains;pmtn;r_i \vert L_{max}$
  $Q \vert intree;pmtn \vert L_{max}$
  $Qm \vert prec;pmtn;r_i \vert L_{max}$

  $Q \vert p_i=p;prec;pmtn;r_i \vert \sum C_i$
  $Q \vert p_i=p;pmtn;r_i \vert \sum U_i$
  $Rm \vert pmtn \vert \sum U_i$
  $Qm \vert p_i=p;pmtn;r_i \vert \sum w_iU_i$
  $Q \vert p_i=p;tree;pmtn;r_i \vert \sum T_i$

  $Q \vert pmtn \vert \sum T_i$
  $Qm \vert p_i=p;prec;pmtn;r_i \vert \sum T_i$
  $Rm \vert pmtn \vert \sum T_i$
  $Q \vert p_i=p;pmtn \vert \sum w_iT_i$
  $Qm \vert p_i=p;pmtn;r_i \vert \sum w_iT_i$