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

Single machine problems with non-negative time-lags

• maximal polynomially solvable:

  $1 \vert chains(l);p_i=p \vert C_{max}$	Munier & Sourd (2003) [21]
  $1 \vert outtree(l);p_i=1;r_i \vert C_{max}$	Bruno et al. (1980) [6]
  $1 \vert prec(1) \vert C_{max}$	Finta & Liu (1996) [8]
  $1 \vert prec;r_i \vert C_{max}$	Lawler (1973) [10]
  $1 \vert tree(l);p_i=1 \vert C_{max}$	Bruno et al. (1980) [6]
  $1 \vert intree(l);p_i=1 \vert L_{max}$	Bruno et al. (1980) [6]
  $1 \vert prec \vert L_{max}$	Lawler (1973) [10]
  $1 \vert prec(1);p_i=1;r_i \vert L_{max}$	Bruno et al. (1980) [6]
  $1 \vert prec;p_i=p;r_i \vert L_{max}$	Simons (1978) [23]
  $1 \vert chains(l);p_i=p \vert \sum C_i$	Brucker et al. (2006) [5]
  $1 \vert outtree(l);p_i=1;r_i \vert \sum C_i$	Brucker & Knust (1999) [4]
  $1 \vert prec(1);p_i=1;r_i \vert \sum C_i$	Baptiste & Timkovsky (2004) [3]
  $1 \vert prec;p_i=p;r_i \vert \sum C_i$	Simons (1983) [24]
  $1 \vert p_i=p;r_i \vert \sum w_iC_i$	Baptiste (2000) [2]
  $1 \vert sp-graph \vert \sum w_iC_i$	Lawler (1978) [12]
  $1 \vert \vert \sum U_i$	Moore (1968) [20], Maxwell (1970) [19], Sidney (1973) [22]
  $1 \vert p_i=p;r_i \vert \sum w_iU_i$	Baptiste (1999) [1]
  $1 \vert p_i=p;r_i \vert \sum T_i$	Baptiste (2000) [2]
  $1 \vert p_i=1;r_i \vert \sum w_iT_i$	Assignment-problem
  $1 \vert p_i=p \vert \sum w_iT_i$	Assignment-problem

• maximal pseudopolynomially solvable:

  $1 \vert \vert \sum w_iU_i$	Lawler & Moore (1969) [13], Karp (1972) [9]
  $1 \vert \vert \sum T_i$	Lawler (1977) [11], Du & Leung (1990) [7]

• minimal NP-hard:

  $*$	$1 \vert chains(l) \vert C_{max}$	Wikum et al. (1994) [27]
  $*$	$1 \vert chains(l_{ij});p_i=1 \vert C_{max}$	Yu (1996) [28], Yu et al. (2004) [29]
  $*$	$1 \vert intree(l);p_i=1;r_i \vert C_{max}$	Brucker & Knust (1999) [4]
  $*$	$1 \vert prec(l);p_i=1 \vert C_{max}$	Leung et al. (1984) [17], Timkovsky (2003) [26]
  $*$	$1 \vert outtree(l);p_i=1 \vert L_{max}$	Brucker & Knust (1999) [4]
  $*$	$1 \vert r_i \vert L_{max}$	Lenstra et al. (1977) [16]
  $*$	$1 \vert chains(l) \vert \sum C_i$	Brucker & Knust (1999) [4]
  $*$	$1 \vert prec \vert \sum C_i$	Lawler (1978) [12], Lenstra & Rinnooy Kan (1978) [14]
  $*$	$1 \vert r_i \vert \sum C_i$	Lenstra et al. (1977) [16]
  $*$	$1 \vert chains(1);p_i=1 \vert \sum w_iC_i$	Tanaev et al. (1994) [25]
  $*$	$1 \vert chains;p_i=1;r_i \vert \sum w_iC_i$	Lenstra & Rinnooy Kan (1980) [15]
  $*$	$1 \vert prec;p_i=1 \vert \sum w_iC_i$	Lawler (1978) [12], Lenstra & Rinnooy Kan (1978) [14]
  $*$	$1 \vert chains;p_i=1 \vert \sum U_i$	Lenstra & Rinnooy Kan (1980) [15]
  	$1 \vert \vert \sum w_iU_i$	Lawler & Moore (1969) [13], Karp (1972) [9]
  	$1 \vert \vert \sum T_i$	Lawler (1977) [11], Du & Leung (1990) [7]
  $*$	$1 \vert chains;p_i=1 \vert \sum T_i$	Leung & Young (1990) [18]
  $*$	$1 \vert \vert \sum w_iT_i$	Lawler (1977) [11], Lenstra et al. (1977) [16]

• minimal open:

  $1 \vert chains(1);p_i=p;r_i \vert C_{max}$
  $1 \vert intree(l);p_i=p \vert C_{max}$
  $1 \vert outtree(l);p_i=p \vert C_{max}$
  $1 \vert chains(1);p_i=p \vert L_{max}$
  $1 \vert chains(l);p_i=1;r_i \vert L_{max}$
  $1 \vert chains(1) \vert \sum C_i$
  $1 \vert chains(1);p_i=p;r_i \vert \sum C_i$

  $1 \vert chains(l_{ij});p_i=1 \vert \sum C_i$
  $1 \vert intree(1);p_i=1;r_i \vert \sum C_i$
  $1 \vert intree(1);p_i=p \vert \sum C_i$
  $1 \vert intree(l);p_i=1 \vert \sum C_i$
  $1 \vert outtree(1);p_i=p \vert \sum C_i$
  $1 \vert p_i=p;r_i \vert \sum w_iT_i$

• maximal open:

  $1 \vert outtree(l);p_i=p;r_i \vert C_{max}$
  $1 \vert prec(1);r_i \vert C_{max}$
  $1 \vert tree(l);p_i=p \vert C_{max}$
  $1 \vert chains(l);p_i=p;r_i \vert L_{max}$
  $1 \vert intree(l);p_i=p \vert L_{max}$

  $1 \vert prec(1) \vert L_{max}$
  $1 \vert prec(1);p_i=p;r_i \vert L_{max}$
  $1 \vert prec(l_{ij});p_i=p;r_i \vert \sum C_i$
  $1 \vert tree(1) \vert \sum C_i$
  $1 \vert p_i=p;r_i \vert \sum w_iT_i$