- maximal polynomially solvable:
$ F2 \vert \vert C_{max}$
Johnson (1954) [
3]
$ F2;S1 \vert p_{ij}=p;s_{ij}=s;r_i \vert C_{max}$
Brucker et al. (2005) [
1]
$ F;S1 \vert p_{ij}=1;s_{ij}=s;r_i \vert C_{max}$
Brucker et al. (2005) [
1]
$ F;S1 \vert p_{ij}=p;s_{ij}=s \vert C_{max}$
Brucker et al. (2005) [
1]
$ F2;S1 \vert p_{ij}=p;s_{ij}=s;r_i \vert \sum C_i$
Brucker et al. (2005) [
1]
$ F;S1 \vert p_{ij}=1;s_{ij}=s;r_i \vert \sum C_i$
Brucker et al. (2005) [
1]
$ F \vert p_{ij}=p;r_i \vert \sum w_iC_i$
Single-machine problem
$ F2;S1 \vert p_{ij}=p;s_{ij}=1;r_i \vert \sum w_iC_i$
Single-machine problem
$ F \vert p_{ij}=p;r_i \vert \sum w_iU_i$
Single-machine problem
$ F2;S1 \vert p_{ij}=p;s_{ij}=1;r_i \vert \sum w_iU_i$
Single-machine problem
$ F2;S1 \vert p_{ij}=p;s_{ij}=s \vert \sum w_iU_i$
Assignment problem
$ F;S1 \vert p_{ij}=1;s_{ij}=s \vert \sum w_iU_i$
Assignment problem
$ F \vert p_{ij}=p;r_i \vert \sum T_i$
Single-machine problem
$ F2;S1 \vert p_{ij}=p;s_{ij}=1;r_i \vert \sum T_i$
Single-machine problem
$ F \vert p_{ij}=1;r_i \vert \sum w_iT_i$
Single-machine problem
$ F \vert p_{ij}=p \vert \sum w_iT_i$
Single-machine problem
$ F2;S1 \vert p_{ij}=p;s_{ij}=s \vert \sum w_iT_i$
Assignment problem
$ F;S1 \vert p_{ij}=1;s_{ij}=s \vert \sum w_iT_i$
Assignment problem
- minimal NP-hard:
$ F2;S1 \vert p_{ij}=p \vert C_{max}$
Brucker et al. (2005) [
1]
$ * $
$ F2 \vert r_i \vert C_{max}$
Lenstra et al. (1977) [
4]
$ * $
$ F2;S1 \vert s_{ij}=s \vert C_{max}$
Brucker et al. (2005) [
1]
$ * $
$ F3 \vert \vert C_{max}$
Garey et al. (1976) [
2]
$ * $
$ F2 \vert \vert L_{max}$
Lenstra et al. (1977) [
4]
$ * $
$ F2;S1 \vert p_{ij}=1;r_i \vert L_{max}$
Brucker et al. (2005) [
1]
$ * $
$ F3;S1 \vert p_{ij}=1;r_i \vert L_{max}$
Brucker et al. (2005) [
1]
$ * $
$ F2 \vert \vert \sum C_i$
Garey et al. (1976) [
2]
$ * $
$ F2;S1 \vert p_{ij}=1;r_i \vert \sum C_i$
Brucker et al. (2005) [
1]
$ * $
$ F3;S1 \vert p_{ij}=1;r_i \vert \sum C_i$
Brucker et al. (2005) [
1]
$ F2;S1 \vert p_{ij}=1 \vert \sum w_iU_i$
Brucker et al. (2005) [
1]
$ F3;S1 \vert p_{ij}=1 \vert \sum w_iU_i$
Brucker et al. (2005) [
1]
$ F2;S1 \vert p_{ij}=1 \vert \sum T_i$
Brucker et al. (2005) [
1]
$ F3;S1 \vert p_{ij}=1 \vert \sum T_i$
Brucker et al. (2005) [
1]
$ * $
$ F2;S1 \vert p_{ij}=1 \vert \sum w_iT_i$
Brucker et al. (2005) [
1]
$ * $
$ F3;S1 \vert p_{ij}=1 \vert \sum w_iT_i$
Brucker et al. (2005) [
1]
- minimal open:
$ F2;S1 \vert p_{ij}=1 \vert C_{max}$
$ F2;S1 \vert s_{ij}=1 \vert C_{max}$
$ F3;S1 \vert p_{ij}=1 \vert C_{max}$
$ F3;S1 \vert p_{ij}=p;s_{ij}=1;r_i \vert C_{max}$
$ F2;S1 \vert p_{ij}=1;s_{ij}=s;r_i \vert L_{max}$
$ F3;S1 \vert p_{ij}=1;s_{ij}=1;r_i \vert L_{max}$
$ F3;S1 \vert p_{ij}=p;s_{ij}=1 \vert L_{max}$
$ F2;S1 \vert p_{ij}=1 \vert \sum C_i$
$ F3;S1 \vert p_{ij}=1 \vert \sum C_i$
$ F3;S1 \vert p_{ij}=p;s_{ij}=1 \vert \sum C_i$
$ F2;S1 \vert p_{ij}=1;s_{ij}=s;r_i \vert \sum w_iC_i$
$ F3;S1 \vert p_{ij}=1;s_{ij}=1;r_i \vert \sum w_iC_i$
$ F2 \vert p_{ij}=p;r_i \vert \sum w_iT_i$
$ F2;S1 \vert p_{ij}=1;s_{ij}=1;r_i \vert \sum w_iT_i$
$ F3 \vert p_{ij}=p;r_i \vert \sum w_iT_i$
- maximal open:
$ F2;S1 \vert s_{ij}=1 \vert C_{max}$
$ F3;S1 \vert p_{ij}=p;r_i \vert C_{max}$
$ F;S1 \vert p_{ij}=1;r_i \vert C_{max}$
$ F;S1 \vert p_{ij}=p \vert \sum w_iC_i$
$ F3;S1 \vert p_{ij}=p \vert \sum U_i$
$ F;S1 \vert p_{ij}=1 \vert \sum U_i$
$ F;S1 \vert p_{ij}=p;s_{ij}=s;r_i \vert \sum w_iU_i$
$ F;S1 \vert p_{ij}=p;s_{ij}=s;r_i \vert \sum w_iT_i$