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

Flow-shop problems without preemption

• maximal polynomially solvable:

  $F \vert p_{ij}=1;outtree;r_i \vert C_{max}$	Bruno et al. (1980) [4]
  $F \vert p_{ij}=1;tree \vert C_{max}$	Bruno et al. (1980) [4]
  $F2 \vert \vert C_{max}$	Johnson (1954) [6]
  $F \vert p_{ij}=1;intree \vert L_{max}$	Bruno et al. (1980) [4]
  $F2 \vert p_{ij}=1;prec;r_i \vert L_{max}$	Bruno et al. (1980) [4]
  $F \vert p_{ij}=1;outtree;r_i \vert \sum C_i$	Brucker & Knust (1999) [3]
  $F2 \vert p_{ij}=1;prec;r_i \vert \sum C_i$	Baptiste & Timkovsky (2004) [2]
  $Fm \vert p_{ij}=1;intree \vert \sum C_i$	Averbakh et al. (2005) [1]
  $F \vert p_{ij}=1;r_i \vert \sum w_iU_i$	Single-machine problem
  $F \vert p_{ij}=1;r_i \vert \sum w_iT_i$	Single-machine problem

• minimal NP-hard:

  $*$	$F \vert p_{ij}=1;intree;r_i \vert C_{max}$	Brucker & Knust (1999) [3]
  $*$	$F \vert p_{ij}=1;prec \vert C_{max}$	Leung et al. (1984) [8], Timkovsky (2003) [10]
  $*$	$F2 \vert chains \vert C_{max}$	Lenstra et al. (1977) [7]
  $*$	$F2 \vert r_i \vert C_{max}$	Lenstra et al. (1977) [7]
  $*$	$F3 \vert \vert C_{max}$	Garey et al. (1976) [5]
  $*$	$F \vert p_{ij}=1;outtree \vert L_{max}$	Brucker & Knust (1999) [3]
  $*$	$F2 \vert \vert L_{max}$	Lenstra et al. (1977) [7]
  $*$	$F2 \vert \vert \sum C_i$	Garey et al. (1976) [5]
  $*$	$F2 \vert p_{ij}=1;chains \vert \sum w_iC_i$	Tanaev et al. (1994) [9]
  $*$	$F3 \vert p_{ij}=1;chains \vert \sum w_iC_i$	Tanaev et al. (1994) [9]
  $*$	$F2 \vert p_{ij}=1;chains \vert \sum U_i$	Brucker & Knust (1999) [3]
  $*$	$F3 \vert p_{ij}=1;chains \vert \sum U_i$	Brucker & Knust (1999) [3]
  $*$	$F2 \vert p_{ij}=1;chains \vert \sum T_i$	Brucker & Knust (1999) [3]
  $*$	$F3 \vert p_{ij}=1;chains \vert \sum T_i$	Brucker & Knust (1999) [3]

• minimal open:

  $F3 \vert p_{ij}=1;intree;r_i \vert C_{max}$
  $F3 \vert p_{ij}=1;prec \vert C_{max}$

  $F3 \vert p_{ij}=1;chains;r_i \vert L_{max}$
  $F3 \vert p_{ij}=1;outtree \vert L_{max}$

  $F \vert p_{ij}=1;intree \vert \sum C_i$
  $F3 \vert p_{ij}=1;intree;r_i \vert \sum C_i$
  $F3 \vert p_{ij}=1;tree \vert \sum C_i$

• maximal open:

  $F \vert p_{ij}=1;chains;r_i \vert L_{max}$

  $Fm \vert p_{ij}=1;prec;r_i \vert L_{max}$

  $F \vert p_{ij}=1;prec;r_i \vert \sum C_i$