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

Flow-shop problems with preemption

• maximal polynomially solvable:

  $F2 \vert pmtn \vert C_{max}$

  Gonzalez & Sahni (1978) [3], Cho & Sahni (1981) [1]

• minimal NP-hard:

  $*$	$F2 \vert chains;pmtn \vert C_{max}$	Lenstra (-) [4]
  $*$	$F2 \vert r_i;pmtn \vert C_{max}$	Gonzalez & Sahni (1978) [3], Cho & Sahni (1981) [1]
  $*$	$F3 \vert pmtn \vert C_{max}$	Gonzalez & Sahni (1978) [3], Cho & Sahni (1981) [1]
  $*$	$F2 \vert pmtn \vert L_{max}$	Gonzalez & Sahni (1978) [3], Cho & Sahni (1981) [1]
  $*$	$F2 \vert pmtn \vert \sum C_i$	Du & Leung (1993) [2]