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

Open-shop problems with transportation delays

• maximal polynomially solvable:

  $O \vert p_{ij}=1;t_{ikl}=T \vert C_{max}$	Rayward-Smith & Rebaine (1992) [12]
  $O2 \vert \vert C_{max}$	Gonzalez & Sahni (1976) [5]
  $O2 \vert p_{ij}=1;t_{ikl}=T;r_i \vert C_{max}$	Brucker et al. (2004) [3]
  $O2 \vert p_{ij}=1;t_{kl} \vert C_{max}$	Knust (1999) [6], Brucker et al. (2004) [3]
  $O \vert p_{ij}=1;r_i \vert L_{max}$	Brucker et al. (1993) [4], Networkflowproblem
  $Om \vert p_{ij}=1;r_i \vert \sum C_i$	Tautenhahn & Woeginger (1997) [13]
  $O \vert p_{ij}=1 \vert \sum w_iC_i$	Brucker et al. (1993) [4]
  $O2 \vert p_{ij}=1;t_{kl} \vert \sum w_iC_i$	Brucker et al. (2004) [3]
  $O \vert p_{ij}=1 \vert \sum U_i$	Liu & Bulfin (1988) [11]
  $O2 \vert p_{ij}=1;t_{ikl}=T \vert \sum U_i$	Brucker et al. (2004) [3]
  $Om \vert p_{ij}=1;r_i \vert \sum w_iU_i$	Baptiste (2003) [2]
  $O \vert p_{ij}=1 \vert \sum T_i$	Liu & Bulfin (1988) [11]

• minimal NP-hard:

  	$O2 \vert t_{ikl}=T \vert C_{max}$	Yu (1996) [14]
  	$O3 \vert \vert C_{max}$	Gonzalez & Sahni (1976) [5]
  $*$	$O \vert \vert C_{max}$	Lenstra (-) [10]
  $*$	$O \vert p_{ij}=1;t_{kl}=t_{lk} \vert C_{max}$	Rayward-Smith & Rebaine (1992) [12]
  $*$	$O2 \vert p_{ij}=1;t_i \vert C_{max}$	Yu (1996) [14], Yu et al. (2004) [15]
  $*$	$O2 \vert r_i \vert C_{max}$	Lawler et al. (1981,1982) [8] [9]
  $*$	$O2 \vert t_i\in\{T_1,T_2\} \vert C_{max}$	Yu (1996) [14]
  $*$	$O2 \vert \vert L_{max}$	Lawler et al. (1981,1982) [8] [9]
  $*$	$O2 \vert \vert \sum C_i$	Achugbue & Chin (1982) [1]
  $*$	$O2 \vert p_{ij}=1;t_i;r_i \vert \sum C_i$	Brucker et al. (2004) [3]
  $*$	$O2 \vert p_{ij}=1;t_i \vert \sum w_iC_i$	Brucker et al. (2004) [3]
  $*$	$O \vert p_{ij}=1;r_i \vert \sum U_i$	Kravchenko (1999) [7]

• minimal open:

  $O2 \vert p_{ij}=1;t_i\in\{T_1,T_2\} \vert C_{max}$
  $O2 \vert p_{ij}=1;t_{kl};r_i \vert C_{max}$
  $O3 \vert p_{ij}=1;t_i\in\{T_1,T_2\} \vert C_{max}$
  $O3 \vert p_{ij}=1;t_{ikl}=T;r_i \vert C_{max}$
  $O3 \vert p_{ij}=1;t_{kl}=t_{lk} \vert C_{max}$
  $O2 \vert p_{ij}=1;t_{ikl}=T;r_i \vert L_{max}$
  $O2 \vert p_{ij}=1;t_{kl} \vert L_{max}$

  $O3 \vert p_{ij}=1;t_{ikl}=T \vert L_{max}$
  $O \vert p_{ij}=1;r_i \vert \sum C_i$
  $O2 \vert p_{ij}=1;t_i\in\{T_1,T_2\} \vert \sum C_i$
  $O2 \vert p_{ij}=1;t_{ikl}=T;r_i \vert \sum C_i$
  $O3 \vert p_{ij}=1;t_{ikl}=T \vert \sum C_i$
  $O2 \vert p_{ij}=1;r_i \vert \sum w_iC_i$
  $O3 \vert p_{ij}=1;r_i \vert \sum w_iC_i$

  $O \vert p_{ij}=1 \vert \sum w_iU_i$
  $O2 \vert p_{ij}=1;t_{ikl}=T \vert \sum w_iU_i$
  $O2 \vert p_{ij}=1;r_i \vert \sum T_i$
  $O2 \vert p_{ij}=1;t_{ikl}=T \vert \sum T_i$
  $O3 \vert p_{ij}=1;r_i \vert \sum T_i$
  $O2 \vert p_{ij}=1 \vert \sum w_iT_i$
  $O3 \vert p_{ij}=1 \vert \sum w_iT_i$

• maximal open:

  $O \vert p_{ij}=1;t_{ikl} \vert \sum C_i$
  $O \vert p_{ij}=1;t_{kl};r_i \vert \sum w_iC_i$
  $O \vert p_{ij}=1;t_i\in\{T_1,T_2\} \vert \sum w_iU_i$
  $O3 \vert p_{ij}=1;t_{ikl};r_i \vert \sum w_iU_i$
  $Om \vert p_{ij}=1;t_i\in\{T_1,T_2\};r_i \vert \sum w_iU_i$

  $Om \vert p_{ij}=1;t_{kl};r_i \vert \sum w_iU_i$
  $O \vert p_{ij}=1;t_i\in\{T_1,T_2\};r_i \vert \sum w_iT_i$
  $O3 \vert p_{ij}=1;t_{ikl};r_i \vert \sum w_iT_i$
  $Om \vert p_{ij}=1;t_{kl};r_i \vert \sum w_iT_i$