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

Job-shop problems with nowait

• maximal polynomially solvable:

  $J2 \vert p_{ij}=1;no-wait \vert \sum C_i$	Kravchenko (1998) [2]
  $J \vert prec;r_i;n=k;no-wait \vert \sum w_iU_i$	Baptiste et al. (2004) [1]
  $J \vert prec;r_i;n=k;no-wait \vert \sum w_iT_i$	Baptiste et al. (2004) [1]

• maximal pseudopolynomially solvable:

  $J2 \vert p_{ij}=1;no-wait \vert C_{max}$

  Timkovsky (1985) [7], Kubiak (1989) [3]

• minimal NP-hard:

  	$J2 \vert p_{ij}=1;no-wait \vert C_{max}$	Timkovsky (1985) [7], Kubiak (1989) [3]
  $*$	$J2 \vert chains;p_{ij}=1;no-wait \vert C_{max}$	Timkovsky (1998) [8]
  $*$	$J2 \vert no-wait \vert C_{max}$	Sahni & Cho (1979) [5]
  $*$	$J3 \vert p_{ij}=1;no-wait \vert C_{max}$	Sriskandarajah & Ladet (1986) [6]
  $*$	$J2 \vert p_{ij}=1;r_i;no-wait \vert L_{max}$	Timkovsky (1998) [8]
  $*$	$J2 \vert chains;p_{ij}=1;no-wait \vert \sum C_i$	Timkovsky (1998) [8]
  $*$	$J2 \vert no-wait \vert \sum C_i$	Roeck (1984) [4]
  $*$	$J2 \vert p_{ij}=1;r_i;no-wait \vert \sum C_i$	Timkovsky (1998) [8]
  $*$	$J3 \vert p_{ij}=1;no-wait \vert \sum C_i$	Sriskandarajah & Ladet (1986) [6]
  	$J2 \vert p_{ij}=1;no-wait \vert \sum w_iC_i$	Timkovsky (1998) [8]
  $*$	$J2 \vert p_{ij}=1;no-wait \vert \sum w_iT_i$	Timkovsky (1998) [8]