ein_ma

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

Single machine problems

maximal polynomially solvable:

$1 \vert prec;r_i \vert C_{max}$ Lawler (1973) [10]

$1 \vert prec;p_i=p;r_i \vert L_{max}$ Simons (1978) [20]

$1 \vert prec;r_i;pmtn \vert L_{max}$ Blazewicz (1976) [6], Baker et al. (1983) [2]

$1 \vert prec;p_i=p;r_i \vert \sum C_i$ Simons (1983) [21]

$1 \vert prec;pmtn;p_i=p;r_i \vert \sum C_i$ Baptiste et al. (2004) [5]

$1 \vert r_i;pmtn \vert \sum C_i$ Baker (1974) [1]

$1 \vert p_i=p;r_i \vert \sum w_iC_i$ Baptiste (2000) [4]

$1 \vert sp-graph \vert \sum w_iC_i$ Lawler (1978) [12]

$1 \vert r_i;pmtn \vert \sum U_i$ Lawler (1990) [13]

$1 \vert p_i=p;r_i \vert \sum w_iU_i$ Baptiste (1999) [3]

$1 \vert pmtn;p_i=p;r_i \vert \sum w_iU_i$ Baptiste (1999) [3]

$1 \vert p_i=p;r_i \vert \sum T_i$ Baptiste (2000) [4]

$1 \vert pmtn;p_i=p;r_i \vert \sum T_i$ Tian et al. (2006) [22]

$1 \vert p_i=1;r_i \vert \sum w_iT_i$ Assignment-problem

maximal pseudopolynomially solvable:

$1 \vert r_i;pmtn \vert \sum w_iU_i$ Lawler (1990) [13]

$1 \vert \vert \sum T_i$ Lawler (1977) [11], Du & Leung (1990) [7]

minimal NP-hard:

$1 \vert r_i \vert L_{max}$ Lenstra et al. (1977) [18]

$1 \vert chains;r_i;pmtn \vert \sum C_i$ Lenstra (-) [15]

$1 \vert prec \vert \sum C_i$ Lawler (1978) [12], Lenstra & Rinnooy Kan (1978) [16]

$1 \vert r_i \vert \sum C_i$ Lenstra et al. (1977) [18]

$1 \vert chains;p_i=1;r_i \vert \sum w_iC_i$ Lenstra & Rinnooy Kan (1980) [17]

$1 \vert prec;p_i=1 \vert \sum w_iC_i$ Lawler (1978) [12], Lenstra & Rinnooy Kan (1978) [16]

$1 \vert r_i;pmtn \vert \sum w_iC_i$ Labetoulle et al. (1984) [9]

$1 \vert chains;p_i=1 \vert \sum U_i$ Lenstra & Rinnooy Kan (1980) [17]

$1 \vert \vert \sum w_iU_i$ Lawler & Moore (1969) [14], Karp (1972) [8]

$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) [19]

$1 \vert \vert \sum w_iT_i$ Lawler (1977) [11], Lenstra et al. (1977) [18]

minimal open:

$1 \vert pmtn;p_i=p;r_i \vert \sum w_iC_i$

$1 \vert p_i=p;r_i \vert \sum w_iT_i$
maximal open:

$1 \vert p_i=p;r_i \vert \sum w_iT_i$

$1 \vert pmtn;p_i=p;r_i \vert \sum w_iT_i$

WWW daemon apache 2009-06-29

$1 \vert prec;r_i \vert C_{max}$	Lawler (1973) [10]
$1 \vert prec;p_i=p;r_i \vert L_{max}$	Simons (1978) [20]
$1 \vert prec;r_i;pmtn \vert L_{max}$	Blazewicz (1976) [6], Baker et al. (1983) [2]
$1 \vert prec;p_i=p;r_i \vert \sum C_i$	Simons (1983) [21]
$1 \vert prec;pmtn;p_i=p;r_i \vert \sum C_i$	Baptiste et al. (2004) [5]
$1 \vert r_i;pmtn \vert \sum C_i$	Baker (1974) [1]
$1 \vert p_i=p;r_i \vert \sum w_iC_i$	Baptiste (2000) [4]
$1 \vert sp-graph \vert \sum w_iC_i$	Lawler (1978) [12]
$1 \vert r_i;pmtn \vert \sum U_i$	Lawler (1990) [13]
$1 \vert p_i=p;r_i \vert \sum w_iU_i$	Baptiste (1999) [3]
$1 \vert pmtn;p_i=p;r_i \vert \sum w_iU_i$	Baptiste (1999) [3]
$1 \vert p_i=p;r_i \vert \sum T_i$	Baptiste (2000) [4]
$1 \vert pmtn;p_i=p;r_i \vert \sum T_i$	Tian et al. (2006) [22]
$1 \vert p_i=1;r_i \vert \sum w_iT_i$	Assignment-problem

$1 \vert r_i;pmtn \vert \sum w_iU_i$	Lawler (1990) [13]
$1 \vert \vert \sum T_i$	Lawler (1977) [11], Du & Leung (1990) [7]

	$1 \vert r_i \vert L_{max}$	Lenstra et al. (1977) [18]
	$1 \vert chains;r_i;pmtn \vert \sum C_i$	Lenstra (-) [15]
	$1 \vert prec \vert \sum C_i$	Lawler (1978) [12], Lenstra & Rinnooy Kan (1978) [16]
	$1 \vert r_i \vert \sum C_i$	Lenstra et al. (1977) [18]
	$1 \vert chains;p_i=1;r_i \vert \sum w_iC_i$	Lenstra & Rinnooy Kan (1980) [17]
	$1 \vert prec;p_i=1 \vert \sum w_iC_i$	Lawler (1978) [12], Lenstra & Rinnooy Kan (1978) [16]
	$1 \vert r_i;pmtn \vert \sum w_iC_i$	Labetoulle et al. (1984) [9]
	$1 \vert chains;p_i=1 \vert \sum U_i$	Lenstra & Rinnooy Kan (1980) [17]
	$1 \vert \vert \sum w_iU_i$	Lawler & Moore (1969) [14], Karp (1972) [8]
	$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) [19]
	$1 \vert \vert \sum w_iT_i$	Lawler (1977) [11], Lenstra et al. (1977) [18]

$1 \vert pmtn;p_i=p;r_i \vert \sum w_iC_i$
$1 \vert p_i=p;r_i \vert \sum w_iT_i$

$1 \vert p_i=p;r_i \vert \sum w_iT_i$
$1 \vert pmtn;p_i=p;r_i \vert \sum w_iT_i$