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

Parallel machine problems with a single server

• maximal polynomially solvable:

  $P;S1 \vert s_i=s;p_i=p;r_i \vert C_{max}$	Brucker et al. (2002B) [2]
  $P \vert \vert \sum C_i$	Bruno et al. (1974) [5]
  $P2;S1 \vert s_i=1 \vert \sum C_i$	Hall et al. (2000) [7]
  $P;S1 \vert s_i=s;p_i=p;r_i \vert \sum C_i$	Brucker et al. (2002B) [2]
  $P;S1 \vert p_i=1 \vert \sum w_iC_i$	Hall et al. (2000) [7]
  $P;S1 \vert s_i=s;p_i=1;r_i \vert \sum w_iC_i$	Brucker et al. (2002B) [2]
  $P \vert p_i=p;r_i \vert \sum w_iC_i$	Brucker & Kravchenko (2008) [4]
  $P;S1 \vert p_i=1 \vert \sum U_i$	Hall et al. (2000) [7]
  $P;S1 \vert s_i=s;p_i=1;r_i \vert \sum w_iU_i$	Brucker et al. (2002B) [2]
  $Pm \vert p_i=p;r_i \vert \sum w_iU_i$	Baptiste et al. (2004) [1]
  $P;S1 \vert s_i=s;p_i=p \vert \sum w_iU_i$	Assignment problem
  $P;S1 \vert s_i=s;p_i=1;r_i \vert \sum T_i$	Brucker et al. (2002B) [2]
  $P \vert p_i=p;r_i \vert \sum T_i$	Brucker & Kravchenko (2005) [3]
  $P \vert p_i=1;r_i \vert \sum w_iT_i$	Networkflowproblem
  $P;S1 \vert s_i=1;p_i=1;r_i \vert \sum w_iT_i$	Assignment problem
  $P;S1 \vert s_i=s;p_i=p \vert \sum w_iT_i$	Assignment problem

• maximal pseudopolynomially solvable:

  $P2;S1 \vert s_i=1 \vert C_{max}$	Hall et al. (2000) [7], Kravchenko & Werner (1997) [8]
  $Pm \vert r_i \vert C_{max}$	Lawler et al. (1989) [9]
  $Pm \vert \vert \sum w_iC_i$	Lawler et al. (1989) [9]
  $P2;S1 \vert p_i=1 \vert \sum w_iU_i$	Single-machine problem, Hall et al. (2000) [7]
  $Pm \vert \vert \sum w_iU_i$	Lawler et al. (1989) [9]
  $P2;S1 \vert p_i=1 \vert \sum T_i$	Single-machine problem, Hall et al. (2000) [7]

• minimal NP-hard:

  	$P2 \vert \vert C_{max}$	Lenstra et al. (1977) [11]
  	$P2;S1 \vert p_i=p \vert C_{max}$	Brucker et al. (2002B) [2]
  $*$	$P \vert \vert C_{max}$	Garey & Johnson (1978) [6]
  $*$	$P2;S1 \vert s_i=s \vert C_{max}$	Hall et al. (2000) [7]
  $*$	$P2;S1 \vert p_i=1;r_i \vert L_{max}$	Single-machine problem, Brucker et al. (2002B) [2]
  $*$	$P2;S1 \vert s_i=1 \vert L_{max}$	Hall et al. (2000) [7]
  	$P2;S1 \vert p_i=p \vert \sum C_i$	Brucker et al. (2002B) [2]
  $*$	$P2 \vert r_i \vert \sum C_i$	Single-machine problem
  $*$	$P2;S1 \vert p_i=1;r_i \vert \sum C_i$	Single-machine problem, Brucker et al. (2002B) [2]
  $*$	$P2;S1 \vert s_i=s \vert \sum C_i$	Hall et al. (2000) [7]
  $*$	$P;S1 \vert s_i=1 \vert \sum C_i$	Brucker et al. (2002B) [2]
  	$P2 \vert \vert \sum w_iC_i$	Bruno et al. (1974) [5]
  $*$	$P \vert \vert \sum w_iC_i$	Lenstra (-) [10]
  	$P2;S1 \vert p_i=1 \vert \sum w_iU_i$	Single-machine problem, Hall et al. (2000) [7]
  	$P2;S1 \vert p_i=1 \vert \sum T_i$	Single-machine problem, Hall et al. (2000) [7]
  $*$	$P2;S1 \vert p_i=1 \vert \sum w_iT_i$	Single-machine problem, Hall et al. (2000) [7]

• minimal open:

  $P2;S1 \vert p_i=1;r_i \vert C_{max}$
  $P2;S1 \vert s_i=1;p_i=p;r_i \vert L_{max}$
  $Pm;S1 \vert s_i=1 \vert \sum C_i$
  $P2;S1 \vert s_i=1;p_i=p;r_i \vert \sum w_iC_i$

  $P \vert p_i=p;r_i \vert \sum U_i$
  $P2 \vert p_i=p;r_i \vert \sum w_iT_i$
  $P2;S1 \vert s_i=s;p_i=1;r_i \vert \sum w_iT_i$

• maximal open:

  $P;S1 \vert p_i=1;r_i \vert C_{max}$
  $Pm;S1 \vert s_i=1 \vert \sum C_i$

  $P;S1 \vert s_i=s;p_i=p;r_i \vert \sum w_iU_i$
  $P;S1 \vert s_i=s;p_i=p;r_i \vert \sum w_iT_i$