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

Open-shop problems with nowait

• maximal polynomially solvable:

  $O \vert p_{ij}=1;tree;no-wait \vert C_{max}$	Brucker et al. (1993) [3], Hu (1961) [5]
  $O2 \vert p_{ij}=1;chains;r_i;no-wait \vert C_{max}$	Timkovsky (2003) [10]
  $O2 \vert p_{ij}=1;prec;no-wait \vert C_{max}$	Brucker et al. (1993) [3], Coffman & Graham (1972) [4]
  $O \vert p_{ij}=1;intree;no-wait \vert L_{max}$	Brucker et al. (1993) [3], Brucker et al. (1977) [2]
  $O \vert p_{ij}=1;r_i;no-wait \vert L_{max}$	Brucker et al. (1993) [3], Simons (1983) [9]
  $O \vert p_{ij}=1;outtree;no-wait \vert \sum C_i$	Brucker et al. (1993) [3], Hu (1961) [5]
  $O \vert p_{ij}=1;r_i;no-wait \vert \sum C_i$	Timkovsky (2003) [10]
  $O2 \vert p_{ij}=1;chains;r_i;no-wait \vert \sum C_i$	Timkovsky (2003) [10]
  $O2 \vert p_{ij}=1;prec;no-wait \vert \sum C_i$	Timkovsky (2003) [10]
  $Om \vert p_{ij}=1;intree;no-wait \vert \sum C_i$	Baptiste et al. (2004) [1]
  $Om \vert p_{ij}=1;r_i;no-wait \vert \sum w_iC_i$	Timkovsky (2003) [10]
  $O \vert p_{ij}=1;no-wait \vert \sum w_iU_i$	Kubiak et al. (1991) [6]
  $Om \vert p_{ij}=1;r_i;no-wait \vert \sum w_iU_i$	Baptiste et al. (2004) [1]
  $Om \vert p_{ij}=1;r_i;no-wait \vert \sum T_i$	Timkovsky (2003) [10]
  $O \vert p_{ij}=1;no-wait \vert \sum w_iT_i$	Brucker et al. (1993) [3]

• minimal NP-hard:

  $*$	$O \vert p_{ij}=1;prec;no-wait \vert C_{max}$	Ullman (1975) [11]
  $*$	$O2 \vert no-wait \vert C_{max}$	Sahni & Cho (1979) [8]
  $*$	$O \vert p_{ij}=1;outtree;no-wait \vert L_{max}$	Brucker et al. (1977) [2]
  $*$	$O \vert p_{ij}=1;prec;no-wait \vert \sum C_i$	Lenstra & Rinnooy Kan (1978) [7]
  $*$	$O2 \vert no-wait \vert \sum C_i$	Kubiak et al. (1991) [6]
  $*$	$O2 \vert p_{ij}=1;chains;no-wait \vert \sum w_iC_i$	Timkovsky (2003) [10]
  $*$	$O3 \vert p_{ij}=1;chains;no-wait \vert \sum w_iC_i$	Timkovsky (2003) [10]
  $*$	$O2 \vert p_{ij}=1;chains;no-wait \vert \sum U_i$	Timkovsky (2003) [10]
  $*$	$O3 \vert p_{ij}=1;chains;no-wait \vert \sum U_i$	Timkovsky (2003) [10]
  $*$	$O2 \vert p_{ij}=1;chains;no-wait \vert \sum T_i$	Timkovsky (2003) [10]
  $*$	$O3 \vert p_{ij}=1;chains;no-wait \vert \sum T_i$	Timkovsky (2003) [10]

• minimal open:

  $O2 \vert p_{ij}=1;intree;r_i;no-wait \vert C_{max}$
  $O2 \vert p_{ij}=1;outtree;r_i;no-wait \vert C_{max}$
  $O3 \vert p_{ij}=1;chains;r_i;no-wait \vert C_{max}$
  $O3 \vert p_{ij}=1;prec;no-wait \vert C_{max}$
  $O2 \vert p_{ij}=1;chains;r_i;no-wait \vert L_{max}$
  $O2 \vert p_{ij}=1;outtree;no-wait \vert L_{max}$
  $O3 \vert p_{ij}=1;outtree;no-wait \vert L_{max}$
  $O2 \vert p_{ij}=1;intree;r_i;no-wait \vert \sum C_i$
  $O2 \vert p_{ij}=1;outtree;r_i;no-wait \vert \sum C_i$

  $O3 \vert p_{ij}=1;chains;r_i;no-wait \vert \sum C_i$
  $O3 \vert p_{ij}=1;tree;no-wait \vert \sum C_i$
  $O \vert p_{ij}=1;intree;no-wait \vert \sum C_i$
  $O \vert p_{ij}=1;r_i;no-wait \vert \sum w_iC_i$
  $O \vert p_{ij}=1;r_i;no-wait \vert \sum U_i$
  $O \vert p_{ij}=1;r_i;no-wait \vert \sum T_i$
  $O2 \vert p_{ij}=1;r_i;no-wait \vert \sum w_iT_i$
  $O3 \vert p_{ij}=1;r_i;no-wait \vert \sum w_iT_i$

• maximal open:

  $O \vert p_{ij}=1;tree;r_i;no-wait \vert C_{max}$
  $O \vert p_{ij}=1;intree;r_i;no-wait \vert L_{max}$
  $Om \vert p_{ij}=1;prec;r_i;no-wait \vert L_{max}$
  $O \vert p_{ij}=1;tree;r_i;no-wait \vert \sum C_i$

  $Om \vert p_{ij}=1;prec;r_i;no-wait \vert \sum C_i$
  $O \vert p_{ij}=1;r_i;no-wait \vert \sum w_iU_i$
  $O \vert p_{ij}=1;r_i;no-wait \vert \sum w_iT_i$