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

Flow-shop problems with transportation times and a single robot

• maximal polynomially solvable:

  $F2 \vert \vert C_{max}$	Johnson (1954) [4]
  $F2;R1 \vert p_{ij}=1;t_i \vert C_{max}$	Hurink & Knust (2001) [3]
  $F2;R1 \vert p_{ij}=p;t_i\in\{T_1,T_2\} \vert C_{max}$	Hurink & Knust (2001) [3]
  $F3;R1 \vert p_{ij}=1;t_k;r_i \vert C_{max}$	Baptiste et al. (2004) [1]
  $F;R1 \vert n \ge m-1; p_{ij}=p;t_k \vert C_{max}$	Hurink & Knust (2001) [3]
  $F3;R1 \vert p_{ij}=1;t_k \vert L_{max}$	Baptiste et al. (2004) [1]
  $F \vert p_{ij}=p;r_i \vert \sum w_iC_i$	Single-machine problem
  $F2;R1 \vert p_{ij}=p;t_{ik}=T;r_i \vert \sum w_iC_i$	Knust (1999) [6]
  $F \vert p_{ij}=p;r_i \vert \sum w_iU_i$	Single-machine problem
  $F2;R1 \vert p_{ij}=p;t_{ik}=T;r_i \vert \sum w_iU_i$	Knust (1999) [6]
  $F \vert p_{ij}=p;r_i \vert \sum T_i$	Single-machine problem
  $F2;R1 \vert p_{ij}=p;t_{ik}=T;r_i \vert \sum T_i$	Knust (1999) [6]
  $F \vert p_{ij}=1;r_i \vert \sum w_iT_i$	Single-machine problem
  $F \vert p_{ij}=p \vert \sum w_iT_i$	Single-machine problem
  $F2;R1 \vert p_{ij}=p;t_{ik}=T \vert \sum w_iT_i$	Knust (1999) [6]

• minimal NP-hard:

  $*$	$F2 \vert r_i \vert C_{max}$	Lenstra et al. (1977) [7]
  $*$	$F2;R1 \vert p_{ij}=p;t_i \vert C_{max}$	Hurink & Knust (2001) [3]
  $*$	$F2;R1 \vert t_{ik}=T \vert C_{max}$	Kise (1991) [5], Hurink & Knust (2001) [3]
  $*$	$F3 \vert \vert C_{max}$	Garey et al. (1976) [2]
  $*$	$F3;R1 \vert p_{ij}=p;t_{ik};r_i \vert C_{max}$	Knust (1999) [6]
  $*$	$F2 \vert \vert L_{max}$	Lenstra et al. (1977) [7]
  $*$	$F2;R1 \vert p_{ij}=1;t_i;r_i \vert L_{max}$	Knust (1999) [6]
  $*$	$F3;R1 \vert p_{ij}=1;t_{ik};r_i \vert L_{max}$	Knust (1999) [6]
  $*$	$F3;R1 \vert p_{ij}=p;t_{ik} \vert L_{max}$	Knust (1999) [6]
  $*$	$F2 \vert \vert \sum C_i$	Garey et al. (1976) [2]
  $*$	$F2;R1 \vert p_{ij}=1;t_i;r_i \vert \sum C_i$	Knust (1999) [6]
  $*$	$F3;R1 \vert p_{ij}=1;t_{ik};r_i \vert \sum C_i$	Knust (1999) [6]
  	$F2;R1 \vert p_{ij}=1;t_i \vert \sum w_iU_i$	Knust (1999) [6]
  	$F3;R1 \vert p_{ij}=1;t_{ik} \vert \sum w_iU_i$	Knust (1999) [6]
  	$F2;R1 \vert p_{ij}=1;t_i \vert \sum T_i$	Knust (1999) [6]
  	$F3;R1 \vert p_{ij}=1;t_{ik} \vert \sum T_i$	Knust (1999) [6]
  $*$	$F2;R1 \vert p_{ij}=1;t_i \vert \sum w_iT_i$	Knust (1999) [6]
  $*$	$F3;R1 \vert p_{ij}=1;t_{ik} \vert \sum w_iT_i$	Knust (1999) [6]

• minimal open:

  $F2;R1 \vert p_{ij}=1;t_i\in\{T_1,T_2\};r_i \vert C_{max}$
  $F3;R1 \vert p_{ij}=1;t_i\in\{T_1,T_2\} \vert C_{max}$
  $F3;R1 \vert p_{ij}=p;t_{ik}=T;r_i \vert C_{max}$
  $Fm;R1 \vert p_{ij}=1;t_{ik}=T;r_i \vert C_{max}$
  $F2;R1 \vert p_{ij}=1;t_i\in\{T_1,T_2\} \vert L_{max}$
  $F3;R1 \vert p_{ij}=1;t_{ik}=T;r_i \vert L_{max}$
  $F3;R1 \vert p_{ij}=p;t_{ik}=T \vert L_{max}$

  $Fm;R1 \vert p_{ij}=1;t_{ik}=T \vert L_{max}$
  $F2;R1 \vert p_{ij}=1;t_i\in\{T_1,T_2\} \vert \sum C_i$
  $F3;R1 \vert p_{ij}=1;t_{ik}=T \vert \sum C_i$
  $F3;R1 \vert p_{ij}=1;t_{ik}=T \vert \sum U_i$
  $F2 \vert p_{ij}=p;r_i \vert \sum w_iT_i$
  $F2;R1 \vert p_{ij}=1;t_{ik}=T;r_i \vert \sum w_iT_i$
  $F3 \vert p_{ij}=p;r_i \vert \sum w_iT_i$

• maximal open:

  $F3;R1 \vert p_{ij}=p;t_{ik} \vert C_{max}$
  $F;R1 \vert p_{ij}=1;t_{ik};r_i \vert C_{max}$
  $F;R1 \vert p_{ij}=p;t_{ik} \vert \sum w_iC_i$
  $F;R1 \vert p_{ij}=1;t_{ik} \vert \sum U_i$
  $F3;R1 \vert p_{ij}=p;t_i;r_i \vert \sum w_iU_i$

  $F;R1 \vert p_{ij}=p;t_i\in\{T_1,T_2\};r_i \vert \sum w_iU_i$
  $F;R1 \vert p_{ij}=p;t_k;r_i \vert \sum w_iU_i$
  $F3;R1 \vert p_{ij}=p;t_i;r_i \vert \sum w_iT_i$
  $F;R1 \vert p_{ij}=p;t_i\in\{T_1,T_2\};r_i \vert \sum w_iT_i$
  $F;R1 \vert p_{ij}=p;t_k;r_i \vert \sum w_iT_i$