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

Job-shop problems without preemption

• maximal polynomially solvable:

  $J2 \vert p_{ij}=1;r_i \vert C_{max}$	Timkovsky (1997) [12]
  $J2 \vert p_{ij}=1 \vert \sum C_i$	Kubiak & Timkovsky (1996) [5]
  $J2 \vert p_{ij}=1 \vert \sum U_i$	Kravchenko (1999A) [4]
  $J \vert prec;p_{ij}=1;r_i;n=k \vert \sum w_iU_i$	Brucker & Kraemer (1996) [1]
  $J \vert prec;r_i;n=2 \vert \sum w_iU_i$	Sotskov (1991) [9]
  $J2 \vert n=k \vert \sum w_iU_i$	Brucker et al. (1997A) [2]
  $J \vert prec;p_{ij}=1;r_i;n=k \vert \sum w_iT_i$	Brucker & Kraemer (1996) [1]
  $J \vert prec;r_i;n=2 \vert \sum w_iT_i$	Sotskov (1991) [9]
  $J2 \vert n=k \vert \sum w_iT_i$	Brucker et al. (1997A) [2]

• maximal pseudopolynomially solvable:

  $J \vert prec;r_i;n=k \vert \sum w_iU_i$	Middendorf & Timkovsky (1999) [8]
  $J2 \vert p_{ij}=1 \vert \sum w_iU_i$	Kravchenko (1999A) [4]
  $J \vert prec;r_i;n=k \vert \sum w_iT_i$	Middendorf & Timkovsky (1999) [8]

• minimal NP-hard:

  	$J3 \vert n=3 \vert C_{max}$	Sotskov & Shakhlevich (1995) [10]
  $*$	$J2 \vert \vert C_{max}$	Lenstra & Rinnooy Kan (1979) [7]
  $*$	$J2 \vert chains;p_{ij}=1 \vert C_{max}$	Timkovsky (1985) [11]
  $*$	$J3 \vert p_{ij}=1 \vert C_{max}$	Lenstra & Rinnooy Kan (1979) [7]
  	$J2 \vert p_{ij}=1;r_i \vert \sum C_i$	Timkovsky (1998) [13]
  	$J3 \vert n=3 \vert \sum C_i$	Sotskov & Shakhlevich (1995) [10]
  $*$	$J2 \vert \vert \sum C_i$	Garey et al. (1976) [3]
  $*$	$J2 \vert chains;p_{ij}=1 \vert \sum C_i$	Timkovsky (1998) [13]
  $*$	$J3 \vert p_{ij}=1 \vert \sum C_i$	Lenstra (-) [6]
  	$J2 \vert p_{ij}=1 \vert \sum w_iC_i$	Timkovsky (1998) [13]
  $*$	$J2 \vert p_{ij}=1;r_i \vert \sum w_iC_i$	Timkovsky (1998) [13]
  	$J2 \vert p_{ij}=1;r_i \vert \sum U_i$	Timkovsky (1998) [13]
  	$J2 \vert p_{ij}=1 \vert \sum w_iU_i$	Kravchenko (1999A) [4]
  $*$	$J2 \vert p_{ij}=1 \vert \sum w_iT_i$	Timkovsky (1998) [13]

• minimal open:

  $J2 \vert chains;n=3 \vert C_{max}$
  $J2 \vert r_i;n=3 \vert C_{max}$

  $J2 \vert chains;n=3 \vert \sum C_i$
  $J2 \vert r_i;n=3 \vert \sum C_i$

  $J2 \vert p_{ij}=1;r_i \vert L_{max}$
  $J2 \vert p_{ij}=1 \vert \sum T_i$

• maximal open:

  $J2 \vert p_{ij}=1;r_i \vert L_{max}$
  $J2 \vert prec;r_i;n=k \vert \sum w_iU_i$

  $J2 \vert p_{ij}=1 \vert \sum T_i$

  $J2 \vert prec;r_i;n=k \vert \sum w_iT_i$