1 Introduction
2 The risk criteria
-
Value at risk (\(\alpha \)-quantile of Y):$$\begin{aligned} \mathbf{VaR}_\alpha [Y]=\inf \{t: \mathrm{Pr}[Y\le t] \ge \alpha \}, \alpha \in (0,1], \end{aligned}$$
-
Conditional value at risk:$$\begin{aligned} \mathbf{CVaR}_\alpha [Y]= & {} \inf \left\{ \gamma +\frac{1}{1-\alpha }{} \mathbf{E}[Y-\gamma ]^+: \gamma \in \mathbb {R}\right\} ,\\&\alpha \in [0,1), \end{aligned}$$
3 Problem formulations
\(\mathcal {P}\)
|
\(\textsc {Min}{-}\textsc {Exp}~\mathcal {P}\)
|
\(\textsc {Min}{-}\textsc {VaR}_\alpha ~\mathcal {P}\)
|
\(\textsc {Min}{-}\textsc {CVaR}_\alpha ~\mathcal {P}\)
|
\(\textsc {Min}{-}\textsc {Max}~\mathcal {P}\)
|
---|---|---|---|---|
\(1|p_j=1|\max T_j\)
| Str. NP-hard not appr. within \(\frac{7}{6}-\epsilon \), \(\epsilon >0\) (Kasperski and Zieliński 2016) | Str. NP-hard not at all appr. for any \(\alpha \in (0,1)\) | Str. NP-hard not appr. within \(\frac{7}{6}-\epsilon \), \(\epsilon >0\) for any \(\alpha \in [0,1)\) | Poly. sol. (Kasperski and Zieliński 2016) |
\(1|p_j=1|\sum U_j\)
| Poly sol. (assignment) | Str. NP-hard not at all appr. for any \(\alpha \in (0,1)\) | Str. NP-hard for any \(\alpha \in (0,1)\) | Str. NP-hard not appr. for any constant \(\gamma >1\) |
\(1||\sum U_j\)
| NP-hard | As above | As above | As above |
\(1|p_j=1|\sum T_j\)
| Poly sol. (assignment) | Str. NP-hard not at all appr. for any \(\alpha \in (0,1)\) | Str. NP-hard for any \(\alpha \in (0,1)\) | Str. NP-hard not appr. within \(\frac{5}{4}-\epsilon \), \(\epsilon >0\) |
\(1||\sum T_j\)
| Str. NP-hard | As above | As above | As above |
\(\mathcal {P}\)
|
\(\textsc {Min}{-}\textsc {Exp}~\mathcal {P}\)
|
\(\textsc {Min}{-}\textsc {VaR}_\alpha ~\mathcal {P}\)
|
\(\textsc {Min}{-}\textsc {CVaR}_\alpha ~\mathcal {P}\)
|
\(\textsc {Min}{-}\textsc {Max}~\mathcal {P}\)
|
---|---|---|---|---|
\(1||\sum C_j\)
| Poly sol. | Str. NP-hard not appr. within \(\frac{6}{5}-\epsilon \), \(\epsilon >0\) | Str. NP-hard for any \(\alpha \in (0,1)\) | |
\(1||\sum U_j\)
| Open | Str. NP-hard for any \(\alpha \in (0,1]\) | Str. NP-hard for any \(\alpha \in (0,1)\) | Str. NP-hard |
\(1||\sum T_j\)
| NP-hard (Lawler 1977) | Str. NP-hard not appr. within \(\frac{6}{5}-\epsilon \), \(\epsilon >0\) | Str. NP-hard for any \(\alpha \in (0,1)\) | Str. NP-hard not appr. within \(\frac{6}{5}-\epsilon \), \(\epsilon >0\) |
\(\mathcal {P}\)
|
\(\textsc {Min}{-}\textsc {Exp}~\mathcal {P}\)
|
\(\textsc {Min}{-}\textsc {VaR}_\alpha ~\mathcal {P}\)
|
\(\textsc {Min}{-}\textsc {CVaR}_\alpha ~\mathcal {P}\)
|
\(\textsc {Min}{-}\textsc {Max}~\mathcal {P}\)
|
---|---|---|---|---|
\(1|prec|\max w_j T_j\) with \(\tilde{d}_j\), \(\tilde{p}_j\), \(w_j\) | \(O(f_{\max }^K Kn^2)\) FPTAS for const. K | \(O(f_{\max }^K Kn^2)\) FPTAS for const. K | \(O(f_{\max }^K Kn^2)\) FPTAS for const. K | \(O(Kn^2)\) (Kasperski and Zieliński 2016) |
\(1|prec|\sum w_j C_j\) with \(\tilde{p}_j\), \(w_j\) | As the determ. problem | Appr. within 2 for const. K | Appr. within 2 | Appr. within 2 (Mastrolilli et al. 2013) |
\(1|prec^*|\sum w_j C_j\) with \(\tilde{p}_j\), \(w_j\) | Poly sol. | Appr. within 2 for const. K | Appr. within \(\min \{\frac{1}{1-\alpha },2\}\) | Appr. within 2 (Mastrolilli et al. 2013) |
\(1|p_j=1|\sum w_j U_j\) with \(\tilde{d}_j\), \(w_j\) | Poly sol. | – | Appr. within \(\min \{\frac{1}{\mathrm{Pr}_{\min }},\frac{1}{1-\alpha }\}\) | Appr. within K |
\(1||\sum w_j U_j\) with \(\tilde{d}_j\), \(p_j\), \(w_j\) | Appr. within \(4+\epsilon \), \(\epsilon >0\) | – | Appr. within \(\min \{\frac{4+\epsilon }{\mathrm{Pr}_{\min }},\frac{4+\epsilon }{1-\alpha }\}\) | Appr. within \((4+\epsilon )K\), \(\epsilon >0\) |
\(1|p_j=1|\sum w_j T_j\) with \(\tilde{d}_j\), \(w_j\) | Poly sol. | – | Appr. within \(\min \{\frac{1}{\mathrm{Pr}_{\min }},\frac{1}{1-\alpha }\}\) | Appr. within K |
\(1||\sum w_j T_j\) with \(\tilde{d}_j\), \(p_j\), \(w_j\) | Appr. within \(4+\epsilon \), \(\epsilon >0\) | – | Appr. within \(\min \{\frac{4+\epsilon }{\mathrm{Pr}_{\min }},\frac{4+\epsilon }{1-\alpha }\}\) | Appr. within \((4+\epsilon )K\), \(\epsilon >0\) |
4 Some general properties
5 Negative complexity results
5.1 Uncertain due dates
\(\xi _1\)
|
\(\xi _2\)
|
\(\xi _3\)
|
\(\xi _4\)
|
\(\xi _5\)
| |
---|---|---|---|---|---|
\(J_{x_1}\)
| 1 | 2 | 2 | 1 | 1 |
\(J_{\overline{x}_1}\)
| 2 | 2 | 1 | 2 | 2 |
\(J_{x_2}\)
| 4 | 4 | 3 | 3 | 4 |
\(J_{\overline{x}_2}\)
| 3 | 3 | 4 | 4 | 4 |
\(J_{x_3}\)
| 6 | 6 | 6 | 5 | 5 |
\(J_{\overline{x}_3}\)
| 5 | 5 | 6 | 6 | 6 |
\(J_{x_4}\)
| 8 | 7 | 8 | 8 | 8 |
\(J_{\overline{x}_4}\)
| 8 | 8 | 7 | 8 | 7 |
\(\xi _1\)
|
\(\xi _2\)
|
\(\xi _3\)
|
\(\xi _4\)
|
\(\xi _5\)
|
\(\xi '_1\)
|
\(\xi '_2\)
|
\(\xi '_3\)
|
\(\xi '_4\)
| |
---|---|---|---|---|---|---|---|---|---|
\(J_{x_1}\)
| 1 | 2 | 2 | 1 | 1 | 1/2 | 8 | 8 | 8 |
\(J_{\overline{x}_1}\)
| 2 | 2 | 1 | 2 | 2 | 1/2 | 8 | 8 | 8 |
\(J_{x_2}\)
| 4 | 4 | 3 | 3 | 4 | 8 | 2+1/2 | 8 | 8 |
\(J_{\overline{x}_2}\)
| 3 | 3 | 4 | 4 | 4 | 8 | 2 + 1/2 | 8 | 8 |
\(J_{x_3}\)
| 6 | 6 | 6 | 5 | 5 | 8 | 8 | 4 + 1/2 | 8 |
\(J_{\overline{x}_3}\)
| 5 | 5 | 6 | 6 | 6 | 8 | 8 | 4+1/2 | 8 |
\(J_{x_4}\)
| 8 | 7 | 8 | 8 | 8 | 8 | 8 | 8 | 6 + 1/2 |
\(J_{\overline{x}_4}\)
| 8 | 8 | 7 | 8 | 7 | 8 | 8 | 8 | 6 + 1/2 |
5.2 Uncertain processing times
\(\xi _1\)
|
\(\xi _2\)
|
\(\xi _3\)
|
\(\xi _4\)
|
\(\xi _5\)
|
\(\xi '_1\)
|
\(\xi '_2\)
|
\(\xi '_3\)
|
\(\xi '_4\)
|
\(d_i\)
| |
---|---|---|---|---|---|---|---|---|---|---|
\(J_{x_1}\)
| 0 | 0 | 1 | 0 | 0 | 2 | 0 | 0 | 0 | 2 |
\(J_{\overline{x}_1}\)
| 1 | 0 | 0 | 1 | 1 | 2 | 0 | 0 | 0 | 2 |
\(J_{x_2}\)
| 1 | 1 | 0 | 0 | 0 | 0 | 2 | 0 | 0 | 2 |
\(J_{\overline{x}_2}\)
| 0 | 0 | 1 | 1 | 0 | 0 | 2 | 0 | 0 | 2 |
\(J_{x_3}\)
| 1 | 1 | 0 | 0 | 0 | 0 | 0 | 2 | 0 | 2 |
\(J_{\overline{x}_3}\)
| 0 | 0 | 0 | 1 | 1 | 0 | 0 | 2 | 0 | 2 |
\(J_{x_4}\)
| 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 2 | 2 |
\(J_{\overline{x}_4}\)
| 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 2 | 2 |