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

Parallel batching problems

• maximal polynomially solvable:

  $1 \vert outtree;p_i=p;p-batch;r_i;b<n \vert C_{max}$	Parallel machine problem
  $1 \vert p-batch;b<n \vert C_{max}$	Brucker et al. (1998) [3]
  $1 \vert tree;p_i=p;p-batch;b<n \vert C_{max}$	Parallel machine problem
  $1 \vert chains;p_i=1;p-batch;r_i;b<n \vert L_{max}$	Parallel machine problem
  $1 \vert intree;p_i=p;p-batch;b<n \vert L_{max}$	Parallel machine problem
  $1 \vert outtree;p_i=1;p-batch;r_i;b<n \vert \sum C_i$	Parallel machine problem
  $1 \vert tree;p_i=p;p-batch;b<n \vert \sum C_i$	Parallel machine problem
  $1 \vert p-batch \vert \sum w_iC_i$	Brucker et al. (1998) [3]
  $1 \vert p_i=p;p-batch;r_i;b<n \vert \sum w_iC_i$	Baptiste (2000A) [1]
  $1 \vert p-batch \vert \sum U_i$	Brucker et al. (1998) [3]
  $1 \vert p_i=p;p-batch;r_i;b<n \vert \sum w_iU_i$	Baptiste (2000A) [1]
  $1 \vert prec;p_i=p;p-batch \vert \sum w_iU_i$	Earliest Start Schedule
  $1 \vert p_i=p;p-batch;r_i;b<n \vert \sum T_i$	Baptiste (2000A) [1]
  $1 \vert p_i=1;p-batch;r_i;b<n \vert \sum w_iT_i$	Parallel machine problem
  $1 \vert p_i=p;p-batch;b<n \vert \sum w_iT_i$	Parallel machine problem
  $1 \vert p_i=p;p-batch;r_i \vert \sum w_iT_i$	Baptiste et al. (2004) [2]
  $1 \vert prec;p_i=p;p-batch \vert \sum w_iT_i$	Earliest Start Schedule

• maximal pseudopolynomially solvable:

  $1 \vert p-batch;r_i \vert \sum w_iU_i$	Baptiste et al. (2004) [2]
  $1 \vert p-batch;r_i \vert \sum w_iT_i$	Baptiste et al. (2004) [2]

• minimal NP-hard:

  $*$	$1 \vert intree;p_i=1;p-batch;r_i;b<n \vert C_{max}$	Parallel machine problem
  $*$	$1 \vert p-batch;r_i;b<n \vert C_{max}$	Brucker et al. (1998) [3]
  $*$	$1 \vert prec;p_i=1;p-batch;b<n \vert C_{max}$	Parallel machine problem
  $*$	$1 \vert outtree;p_i=1;p-batch;b<n \vert L_{max}$	Parallel machine problem
  $*$	$1 \vert p-batch;b<n \vert L_{max}$	Brucker et al. (1998) [3]
  $*$	$1 \vert intree;p_i=1;p-batch;r_i;b<n \vert \sum C_i$	Parallel machine problem
  $*$	$1 \vert p-batch;r_i;b<n \vert \sum C_i$	Single machine problem
  $*$	$1 \vert prec;p_i=1;p-batch;b<n \vert \sum C_i$	Parallel machine problem
  $*$	$1 \vert chains;p_i=1;p-batch;b<n \vert \sum w_iC_i$	Parallel machine problem
  $*$	$1 \vert chains;p_i=1;p-batch;b<n \vert \sum U_i$	Single machine problem
  	$1 \vert p-batch \vert \sum w_iU_i$	Brucker et al. (1998) [3]
  $*$	$1 \vert chains;p_i=1;p-batch;b<n \vert \sum T_i$	Single machine problem
  	$1 \vert p-batch \vert \sum w_iT_i$	Brucker et al. (1998) [3]

• minimal open:

  $1 \vert chains;p-batch \vert C_{max}$
  $1 \vert intree;p_i=1;p-batch;r_i \vert C_{max}$
  $1 \vert p-batch;r_i \vert C_{max}$
  $1 \vert chains;p_i=p;p-batch;r_i \vert L_{max}$
  $1 \vert outtree;p_i=1;p-batch;r_i \vert L_{max}$
  $1 \vert chains;p-batch \vert \sum C_i$
  $1 \vert chains;p_i=p;p-batch;r_i \vert \sum C_i$
  $1 \vert intree;p_i=1;p-batch;r_i \vert \sum C_i$

  $1 \vert p-batch;b<n \vert \sum C_i$
  $1 \vert p-batch;r_i \vert \sum C_i$
  $1 \vert chains;p_i=1;p-batch;r_i \vert \sum w_iC_i$
  $1 \vert chains;p_i=1;p-batch;r_i \vert \sum U_i$
  $1 \vert chains;p_i=1;p-batch;r_i \vert \sum T_i$
  $1 \vert p-batch \vert \sum T_i$
  $1 \vert p_i=p;p-batch;r_i;b<n \vert \sum w_iT_i$

• maximal open:

  $1 \vert tree;p-batch;b<n \vert C_{max}$
  $1 \vert chains;p_i=p;p-batch;r_i;b<n \vert L_{max}$
  $1 \vert outtree;p_i=p;p-batch;r_i;b<n \vert \sum C_i$
  $1 \vert tree;p-batch;b<n \vert \sum C_i$
  $1 \vert p-batch;b<n \vert \sum w_iC_i$
  $1 \vert prec;p-batch;r_i \vert \sum w_iC_i$

  $1 \vert prec;p-batch;r_i \vert \sum U_i$
  $1 \vert prec;p_i=p;p-batch;r_i \vert \sum w_iU_i$
  $1 \vert prec;p-batch;r_i \vert \sum T_i$
  $1 \vert p_i=p;p-batch;r_i;b<n \vert \sum w_iT_i$
  $1 \vert prec;p_i=p;p-batch;r_i \vert \sum w_iT_i$