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

Open-shop problems with preemption

• maximal polynomially solvable:

  $O \vert pmtn;r_i \vert L_{max}$

  Cho & Sahni (1981) [1]

• minimal NP-hard:

  $*$	$O2 \vert chains;pmtn \vert C_{max}$	Lenstra (-) [5]
  	$O2 \vert pmtn \vert \sum C_i$	Du & Leung (1993) [2]
  $*$	$O2 \vert chains;pmtn \vert \sum C_i$	Lenstra (-) [5]
  $*$	$O2 \vert pmtn;r_i \vert \sum C_i$	Sriskandarajah & Wagneur (1994) [7]
  $*$	$O3 \vert pmtn \vert \sum C_i$	Liu & Bulfin (1985) [6]
  $*$	$O2 \vert pmtn \vert \sum w_iC_i$	Lenstra (-) [5]
  	$O2 \vert pmtn \vert \sum U_i$	Lawler et al. (1981,1982) [3] [4]