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

Shop problems with multipurpose machines

• maximal polymomially solvable:

  $FMPMm \vert r_i;p_{ij}=1 \vert C_{max}$	Brucker et al. (1997) [4]
  $FMPMm \vert r_i;p_{ij}=1 \vert \sum C_i$	Brucker et al. (1997) [4]
  $FMPMm \vert p_{ij}=1 \vert \sum w_iC_i$	Brucker et al. (1997) [4]
  $FMPMm \vert p_{ij}=1 \vert \sum w_iU_i$	Brucker et al. (1997) [4]
  $FMPMm \vert prec;r_i;n=k \vert \sum w_iU_i$	Brucker (1995) [2]
  $FMPMm \vert p_{ij}=1 \vert \sum T_i$	Brucker et al. (1997) [4]
  $FMPMm \vert prec;r_i;n=k \vert \sum w_iT_i$	Brucker (1995) [2]
  $JMPM \vert prec;r_i;n=2 \vert L_{max}$	Jurisch (1995) [7]
  $JMPM \vert prec;r_i;p_{ij}=1;n=k \vert \sum w_iU_i$	Brucker et al. (1997) [4]
  $JMPM \vert prec;r_i;p_{ij}=1;n=k \vert \sum w_iT_i$	Brucker et al. (1997) [4]
  $OMPMm \vert r_i;p_{ij}=1 \vert C_{max}$	Brucker et al. (1997) [4]
  $OMPMm \vert r_i;p_{ij}=1 \vert \sum C_i$	Brucker et al. (1997) [4]
  $OMPMm \vert p_{ij}=1 \vert \sum w_iC_i$	Brucker et al. (1997) [4]
  $OMPMm \vert p_{ij}=1 \vert \sum w_iU_i$	Brucker et al. (1997) [4]
  $OMPMm \vert prec;r_i;n=k \vert \sum w_iU_i$	Brucker (1995) [2]
  $OMPMm \vert p_{ij}=1 \vert \sum T_i$	Brucker et al. (1997) [4]
  $OMPMm \vert prec;r_i;n=k \vert \sum w_iT_i$	Brucker (1995) [2]

• maximal pseudopolymomially solvable:

  $JMPM2 \vert n=3 \vert C_{max}$	Jurisch (1995) [7], Meyer (1992) [16]
  $OMPM \vert p_{ij}=1 \vert C_{max}$	Jurisch (1995) [7]

• minimal NP-hard:

  	$FMPM \vert n=3 \vert C_{max}$	Brucker et al. (1997) [4]
  	$FMPM2 \vert \vert C_{max}$	Lenstra et al. (1977) [15]
  $*$	$FMPM \vert intree;r_i;p_{ij}=1 \vert C_{max}$	Brucker et al. (1977) [3]
  $*$	$FMPM \vert prec;p_{ij}=1 \vert C_{max}$	Ullman (1975) [22]
  $*$	$FMPM2 \vert chains \vert C_{max}$	Lenstra et al. (1977) [15]
  $*$	$FMPM2 \vert r_i \vert C_{max}$	Lenstra et al. (1977) [15]
  $*$	$FMPM3 \vert \vert C_{max}$	Garey et al. (1976) [5]
  $*$	$FMPM \vert outtree;p_{ij}=1 \vert L_{max}$	Brucker et al. (1977) [3]
  $*$	$FMPM2 \vert \vert L_{max}$	Lenstra et al. (1977) [15]
  $*$	$FMPM \vert prec;p_{ij}=1 \vert \sum C_i$	Lenstra & Rinnooy Kan (1978) [13]
  $*$	$FMPM2 \vert \vert \sum C_i$	Garey et al. (1976) [5]
  $*$	$FMPM2 \vert chains;p_{ij}=1 \vert \sum w_iC_i$	Tanaev et al. (1994) [18]
  $*$	$FMPM2 \vert chains;p_{ij}=1 \vert \sum U_i$	Single-machine problem
  $*$	$FMPM2 \vert chains;p_{ij}=1 \vert \sum T_i$	Single-machine problem
  	$JMPM2 \vert n=3 \vert C_{max}$	Jurisch (1995) [7], Meyer (1992) [16]
  $*$	$JMPM2 \vert chains;p_{ij}=1 \vert C_{max}$	Timkovsky (1985) [19]
  $*$	$JMPM3 \vert p_{ij}=1 \vert C_{max}$	Lenstra & Rinnooy Kan (1979) [14]
  	$JMPM2 \vert r_i;p_{ij}=1 \vert \sum C_i$	Timkovsky (1998) [20]
  	$JMPM3 \vert n=3 \vert \sum C_i$	Sotskov & Shakhlevich (1995) [17]
  $*$	$JMPM2 \vert chains;p_{ij}=1 \vert \sum C_i$	Timkovsky (1998) [20]
  $*$	$JMPM3 \vert p_{ij}=1 \vert \sum C_i$	Lenstra (-) [12]
  	$JMPM2 \vert p_{ij}=1 \vert \sum w_iC_i$	Timkovsky (1998) [20]
  $*$	$JMPM2 \vert r_i;p_{ij}=1 \vert \sum w_iC_i$	Timkovsky (1998) [20]
  	$JMPM2 \vert r_i;p_{ij}=1 \vert \sum U_i$	Timkovsky (1998) [20]
  	$JMPM2 \vert p_{ij}=1 \vert \sum w_iU_i$	Kravchenko (1999A) [8]
  $*$	$JMPM2 \vert p_{ij}=1 \vert \sum w_iT_i$	Timkovsky (1998) [20]

  
  

  	$OMPM \vert n=3 \vert C_{max}$	Gonzalez & Sahni (1976) [6]
  	$OMPM3 \vert \vert C_{max}$	Gonzalez & Sahni (1976) [6]
  $*$	$OMPM \vert \vert C_{max}$	Lenstra (-) [12]
  $*$	$OMPM \vert outtree;r_i;p_{ij}=1 \vert C_{max}$	Timkovsky (2003) [21]
  $*$	$OMPM \vert prec;p_{ij}=1 \vert C_{max}$	Timkovsky (2003) [21]
  $*$	$OMPM2 \vert chains \vert C_{max}$	Tanaev et al. (1994) [18]
  $*$	$OMPM2 \vert r_i \vert C_{max}$	Lawler et al. (1981,1982) [10] [11]
  $*$	$OMPM \vert outtree;p_{ij}=1 \vert L_{max}$	Timkovsky (2003) [21]
  $*$	$OMPM2 \vert \vert L_{max}$	Lawler et al. (1981,1982) [10] [11]
  $*$	$OMPM2 \vert \vert \sum C_i$	Achugbue & Chin (1982) [1]
  $*$	$OMPM \vert prec;p_{ij}=1 \vert \sum C_i$	Lenstra & Rinnooy Kan (1978) [13]
  $*$	$OMPM2 \vert chains;p_{ij}=1 \vert \sum w_iC_i$	Timkovsky (2003) [21]
  $*$	$OMPM \vert r_i;p_{ij}=1 \vert \sum U_i$	Kravchenko (1999) [9]
  $*$	$OMPM2 \vert chains;p_{ij}=1 \vert \sum U_i$	Timkovsky (2003) [21]
  $*$	$OMPM2 \vert chains;p_{ij}=1 \vert \sum T_i$	Timkovsky (2003) [21]

• minimal open:

  $FMPM \vert p_{ij}=1 \vert C_{max}$
  $FMPM2 \vert chains;p_{ij}=1 \vert C_{max}$
  $FMPM2 \vert r_i;p_{ij}=1 \vert L_{max}$
  $FMPM \vert n=2 \vert \sum C_i$
  $FMPM \vert p_{ij}=1 \vert \sum C_i$
  $FMPM2 \vert chains;p_{ij}=1 \vert \sum C_i$
  $FMPM2 \vert r_i;p_{ij}=1 \vert \sum w_iC_i$
  $FMPM \vert n=2 \vert \sum U_i$
  $FMPM2 \vert p_{ij}=1 \vert \sum w_iT_i$

  $JMPM2 \vert p_{ij}=1 \vert C_{max}$
  $JMPM2 \vert n=2 \vert \sum C_i$
  $JMPM2 \vert p_{ij}=1 \vert \sum C_i$
  $JMPM2 \vert n=2 \vert \sum U_i$
  $OMPM \vert p_{ij}=1;n=2 \vert C_{max}$
  $OMPM \vert p_{ij}=1;n=3 \vert C_{max}$
  $OMPM2 \vert \vert C_{max}$

  $OMPM2 \vert chains;p_{ij}=1 \vert C_{max}$
  $OMPM2 \vert r_i;p_{ij}=1 \vert L_{max}$
  $OMPM \vert p_{ij}=1;n=2 \vert \sum C_i$
  $OMPM \vert p_{ij}=1;n=3 \vert \sum C_i$
  $OMPM2 \vert chains;p_{ij}=1 \vert \sum C_i$
  $OMPM2 \vert r_i;p_{ij}=1 \vert \sum w_iC_i$
  $OMPM2 \vert p_{ij}=1 \vert \sum w_iT_i$

• maximal open:

  $FMPM \vert outtree;r_i;p_{ij}=1 \vert C_{max}$
  $FMPM \vert tree;p_{ij}=1 \vert C_{max}$
  $FMPM \vert chains;r_i;p_{ij}=1 \vert L_{max}$
  $FMPM \vert intree;p_{ij}=1 \vert L_{max}$
  $FMPMm \vert prec;r_i;p_{ij}=1 \vert L_{max}$
  $FMPM \vert tree;r_i;p_{ij}=1 \vert \sum C_i$
  $FMPMm \vert prec;r_i;p_{ij}=1 \vert \sum C_i$
  $FMPM \vert prec;r_i;n=k \vert \sum w_iC_i$
  $FMPM \vert r_i;p_{ij}=1 \vert \sum w_iU_i$
  $FMPM \vert r_i;p_{ij}=1 \vert \sum w_iT_i$
  $JMPM2 \vert r_i;p_{ij}=1 \vert L_{max}$
  $JMPM2 \vert prec;r_i;n=k \vert \sum w_iC_i$
  $JMPM2 \vert p_{ij}=1 \vert \sum U_i$
  $JMPM \vert prec;r_i;n=2 \vert \sum w_iU_i$
  $JMPM2 \vert p_{ij}=1 \vert \sum T_i$
  $JMPM \vert prec;r_i;n=2 \vert \sum w_iT_i$

  $OMPM \vert tree;p_{ij}=1 \vert C_{max}$
  $OMPM2 \vert \vert C_{max}$
  $OMPM \vert intree;r_i;p_{ij}=1 \vert L_{max}$
  $OMPMm \vert prec;r_i;p_{ij}=1 \vert L_{max}$
  $OMPM \vert tree;r_i;p_{ij}=1 \vert \sum C_i$
  $OMPMm \vert prec;r_i;p_{ij}=1 \vert \sum C_i$
  $OMPM \vert prec;r_i;n=k \vert \sum w_iC_i$
  $OMPM \vert p_{ij}=1 \vert \sum w_iU_i$
  $OMPM \vert prec;r_i;n=2 \vert \sum w_iU_i$
  $OMPM \vert prec;r_i;p_{ij}=1;n=k \vert \sum w_iU_i$
  $OMPMm \vert r_i;p_{ij}=1 \vert \sum w_iU_i$
  $OMPM \vert prec;r_i;n=2 \vert \sum w_iT_i$
  $OMPM \vert prec;r_i;p_{ij}=1;n=k \vert \sum w_iT_i$
  $OMPM \vert r_i;p_{ij}=1 \vert \sum w_iT_i$