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

Serial batching problems

• maximal polynomially solvable:

  $1 \vert prec;s-batch \vert L_{max}$	Ng et al. (2002) [12]
  $1 \vert prec;p_i=p;s-batch \vert \sum C_i$	Albers & Brucker (1993) [1]
  $1 \vert s-batch \vert \sum C_i$	Coffman et al. (1990) [5]
  $1 \vert p_i=p;s-batch;r_i \vert \sum w_iC_i$	Baptiste (2000A) [2]
  $1 \vert s-batch \vert \sum U_i$	Brucker & Kovalyov (1996) [4]
  $1 \vert p_i=p;s-batch;r_i \vert \sum w_iU_i$	Baptiste (2000A) [2]
  $1 \vert p_i=p;s-batch;r_i \vert \sum T_i$	Baptiste (2000A) [2]

• maximal pseudopolynomially solvable:

  $1 \vert s-batch \vert \sum w_iU_i$	Brucker & Kovalyov (1996) [4], Karp (1972) [7]
  $1 \vert s-batch \vert \sum T_i$	Du & Leung (1990) [6], Baptiste & Jouglet (2001) [3]

• minimal NP-hard:

  $*$	$1 \vert s-batch;r_i \vert L_{max}$	Lenstra et al. (1977) [11]
  	$1 \vert chains;s-batch \vert \sum C_i$	Albers & Brucker (1993) [1]
  $*$	$1 \vert prec;s-batch \vert \sum C_i$	Lawler (1978) [8], Lenstra & Rinnooy Kan (1978) [9]
  $*$	$1 \vert s-batch;r_i \vert \sum C_i$	Lenstra et al. (1977) [11]
  $*$	$1 \vert chains;p_i=1;s-batch \vert \sum w_iC_i$	Albers & Brucker (1993) [1]
  $*$	$1 \vert s-batch \vert \sum w_iC_i$	Albers & Brucker (1993) [1]
  $*$	$1 \vert chains;p_i=1;s-batch \vert \sum U_i$	Lenstra & Rinnooy Kan (1980) [10]
  	$1 \vert s-batch \vert \sum w_iU_i$	Brucker & Kovalyov (1996) [4], Karp (1972) [7]
  	$1 \vert s-batch \vert \sum T_i$	Du & Leung (1990) [6], Baptiste & Jouglet (2001) [3]
  $*$	$1 \vert chains;p_i=1;s-batch \vert \sum T_i$	Leung & Young (1990) [6]

• minimal open:

  $1 \vert chains;p_i=1;s-batch;r_i \vert L_{max}$
  $1 \vert chains;p_i=1;s-batch;r_i \vert \sum C_i$
  $1 \vert p_i=1;s-batch \vert \sum w_iT_i$

• maximal open:

  $1 \vert prec;p_i=p;s-batch;r_i \vert L_{max}$
  $1 \vert prec;p_i=p;s-batch;r_i \vert \sum C_i$
  $1 \vert p_i=p;s-batch;r_i \vert \sum w_iT_i$