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

Multipurpose machine problems

• maximal polynomially solvable:

  $QMPM \vert \vert \sum C_i$	Horn (1973) [6], Bruno et al. (1974) [3]
  $PMPM \vert p_i=1;r_i \vert \sum w_iU_i$	Brucker et al. (1997) [2]
  $QMPM \vert p_i=1 \vert \sum w_iU_i$	Brucker et al. (1997) [2]
  $PMPM \vert p_i=1;r_i \vert \sum w_iT_i$	Brucker et al. (1997) [2]
  $QMPM \vert p_i=1 \vert \sum w_iT_i$	Brucker et al. (1997) [2]

• minimal NP-hard:

  	$PMPM2 \vert \vert C_{max}$	Lenstra et al. (1977) [10]
  	$PMPM2 \vert chains;p_i=1 \vert C_{max}$	Brucker et al. (1997) [1]
  $*$	$PMPM \vert \vert C_{max}$	Garey & Johnson (1978) [5]
  $*$	$PMPM \vert intree;p_i=1;r_i \vert C_{max}$	Brucker et al. (1977) [1]
  $*$	$PMPM \vert prec;p_i=1 \vert C_{max}$	Ullman (1975) [12]
  $*$	$PMPM2 \vert chains \vert C_{max}$	Du et al. (1991) [4]
  $*$	$QMPM \vert chains;p_i=1 \vert C_{max}$	Kubiak (1988) [7]
  $*$	$PMPM \vert outtree;p_i=1 \vert L_{max}$	Brucker et al. (1977) [1]
  $*$	$PMPM \vert prec;p_i=1 \vert \sum C_i$	Lenstra & Rinnooy Kan (1978) [9]
  $*$	$PMPM2 \vert chains \vert \sum C_i$	Du et al. (1991) [4]
  $*$	$PMPM2 \vert r_i \vert \sum C_i$	Single-machine problem
  	$PMPM2 \vert \vert \sum w_iC_i$	Bruno et al. (1974) [3]
  $*$	$PMPM \vert \vert \sum w_iC_i$	Lenstra (-) [8]
  $*$	$PMPM2 \vert chains;p_i=1 \vert \sum w_iC_i$	Timkovsky (1998) [11]
  $*$	$PMPM2 \vert chains;p_i=1 \vert \sum U_i$	Single-machine problem
  $*$	$PMPM2 \vert chains;p_i=1 \vert \sum T_i$	Single-machine problem

• minimal open:

  $QMPM2 \vert p_i=1;r_i \vert C_{max}$
  $PMPM2 \vert chains;p_i=1 \vert \sum C_i$

  $QMPM2 \vert p_i=1;r_i \vert \sum C_i$

• maximal open:

  $QMPM \vert tree;p_i=1;r_i \vert \sum C_i$
  $QMPMm \vert prec;p_i=1;r_i \vert \sum C_i$

  $QMPM \vert p_i=1;r_i \vert \sum w_iU_i$
  $QMPM \vert p_i=1;r_i \vert \sum w_iT_i$