Pith. Sign in

REVIEW

The Project Scheduling Interdiction Problem with Delay Groups

PaperPDF from arXiv

data files

ReviewThe objections and verdict, as JSON Paper breakdownThe authors' claims, conditions and measurements, as JSON Signed receiptProof this review has not been altered
X Bluesky LinkedIn Reddit Hacker News
Fei Wu, Erik Demeulemeester, Jannik Matuschke

Discrete Mathematics · Submitted 27 Aug 2026 · 38 references

Pith's verdict: Solid new model and mostly rigorous complexity analysis, but Theorem 3.3's group construction needs an edge-coloring fix before the ℓ=1 hardness claim is airtight.

T0 · AI review

How this review was made: An AI referee (deepseek/deepseek-v4-flash) read the paper on September 9, 2026 and answered a fixed list of questions about it. T0 is the starting level every paper gets. The levels describe how deeply Pith has checked the paper, never the authors.

  1. T0 AI review An AI read the paper and answered a fixed list of questions.
  2. T1 Audit Automatic checks that the references and files the paper relies on exist and match.
  3. T2 Compute The paper's code or calculations re-run with the same results.
  4. T3 Formal statement The claims written out in a formal math language a computer can read.
  5. T4 Proof Those claims proved, and the proof checked by computer.

How Pith checks papers →

· 1 major objection · 7 minor · Ask about this paper · The compiled record · Read the full review →
Challenge this review Comment (0) Read on arXiv ↗
Cite ▾
arXiv ID2608.27386 (version 1)
Pith IDVQRK6365, Pith's permanent record of this paper and its review
CitationErik Demeulemeester, Fei Wu, Jannik Matuschke. "The Project Scheduling Interdiction Problem with Delay Groups." arXiv:2608.27386 (2026). https://pith.science/paper/VQRK6365
Cite this reviewBibTeX for Pith's review of this paper
Claim paper

Why Pith says this

Highlight any text to comment on it.

Referee report

How Pith checks papers → · Full audit of this paper → · Review history (2 revisions) →

The paper

The paper claims

Delay groups make project scheduling interdiction NP-hard even with a single group and continuous knapsack constraints.

The reading

This paper introduces delay groups to model correlated disruptions in project scheduling, where a shared cause simultaneously slows all dependent activities. Taking an adversarial perspective, it asks which $k$ groups an interdictor should disrupt to maximize the project makespan, with delays chosen from group-specific uncertainty sets. The paper establishes that this problem is $NP$-hard for general polyhedral uncertainty sets, even with a single delay group and continuous relaxation of the interdictor's decision variables. For budgeted uncertainty sets, hardness holds both when every activity in a disrupted group is delayed and when exactly one activity per group may be delayed; additionally, the former case admits no polynomial-time approximation within $1-1/e+\varepsilon$ unless $P=NP$. Despite these negative results, the paper devises two structure-based heuristics that achieve near-optimal solutions on networks up to 5,000 activities, in some cases outperforming an exact solver.

What carries the argument

Delay groups are the central object: a partition of activities into subsets whose delays are jointly described by an uncertainty set (polyhedral or budgeted). The paper's hardness proofs rely on reductions from Partition (for polyhedral uncertainty), Max $k$-cover (for budgeted all-delayed), and 3-SAT (for budgeted one-delayed), while the heuristic algorithms exploit dynamic programming on paths (for the singe-activity-per-group variant) and per-group decomposition (for the all-delayed variant).

Extended reading notes

Core claim

The paper proves that the Project Scheduling Interdiction Problem with Delay Groups (PSIP-DG) is $NP$-hard for general polyhedral uncertainty sets even when only one delay group exists and the interdiction variables are continuous (Corollary 3.1). For budgeted uncertainty, PSIP-DG remains $NP$-hard both when all activities in a disrupted group are delayed (Theorem 3.2) and when exactly one activity per group may be delayed (Theorem 3.3). Furthermore, when all activities of a disrupted group are delayed, no polynomial-time algorithm can approximate PSIP-DG within $1-1/e+\varepsilon$ for any $\varepsilon>0$ unless $P=NP$ (Corollary 3.2). These results establish that the correlated nature of delays—captured by delay groups—introduces computational hardness beyond what independent-activity interdiction models exhibit.

Load-bearing premise

The assumption that delay groups are disjoint and that overlapping groups can be handled by duplicating activities in a serial chain, which may alter the precedence structure in a way that does not exactly preserve the true project dependencies.

Editorial extensions

If this is right

  • Project managers assessing worst-case schedule risk must consider correlated delay groups rather than independent activities, because the combined effect of simultaneous group disruptions can far exceed the sum of individual group impacts.
  • The $NP$-hardness of PSIP-DG even with a single group shows that robust scheduling problems with coupling constraints among activities are fundamentally harder than traditional project interdiction problems.
  • The $1-1/e+\varepsilon$ inapproximability bound for the all-delayed case implies that no efficient near-optimal solution can be guaranteed for that variant unless $P=NP$.
  • The group selection search (GSS) heuristic offers a practical tool for large instances (up to 5,000 activities) where exact solvers time out, finding solutions within 1.5% of the best known incumbent in seconds.
  • The results transfer to resource-constrained settings: any extension that preserves the longest-path structure inherits the same hardness, while extensions with resource conflicts require fundamentally different modeling.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The transformation that duplicates activities to enforce disjoint delay groups may alter the project network's dependency structure in subtle ways (e.g., creating artificial precedence chains), so practitioners should verify that the transformed network preserves the original critical path relationships.
  • If delay groups are allowed to overlap without duplication, the problem likely remains $NP$-hard but may admit different approximation approaches that exploit overlapping structure.
  • The data requirements of the model (nominal durations, delay ranges, group membership) are light compared to distributional models, making it suitable for one-off projects where historical delay distributions are unavailable.
  • An interesting testable extension would be to replace the budget constraint with a cost vector over groups and investigate whether the approximability landscape changes.
Original abstract

Large-scale projects are frequently delayed by correlated disruptions: when a shared input such as a common supplier, a specialized team, or a supporting platform degrades, all dependent activities are slowed down simultaneously. This paper introduces delay groups to capture such disruptions: a delay group is a set of activities whose delays stem from a common cause, described jointly by an uncertainty set. Our model takes the perspective of an interdictor that, subject to a budget of $k$ groups, selects which groups to disrupt so as to maximize the project makespan. The interdictor can extend activity durations within each disrupted group by delays from a group-specific uncertainty set, while non-disrupted activities keep their nominal duration. We study the complexity of the resulting Project Scheduling Interdiction Problem with Delay Groups (PSIP-DG), which provides a worst-case stress test of the schedule. The problem is computationally intractable ($N\!P$-hard) for general polyhedral uncertainty sets, even for a single delay group with a continuous knapsack constraint. For budgeted uncertainty sets, we prove $N\!P$-hardness both when all activities of a disrupted group are delayed and when only one activity per group may be delayed, and derive an inapproximability bound of $1-1/e+\epsilon$ for the former case. We further develop a greedy heuristic with approximation guarantee $k$ and two structure-based heuristics with initializations and neighborhoods from tractable special cases. Experiments on $5{,}000$-activity networks show that the heuristics match the solution quality of an exact solver at substantially lower running times, in some cases finding strictly better solutions.

The compiled record

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-09-23: 1 request, 7,168 input tokens.

What the abstract itself states, as probabilities: claims first 0.08 · states limitation 0.83 · human participants 0.02 · controlled comparison 0.11 · randomized assignment 0.02 · states quantitative result 0.98 · compares with prior results 0.72 · mentions code or data availability 0.02.

The abstract, sentence by sentence

arXiv listing abstract v1. Results and the main claim are underlined; .

Large-scale projects are frequently delayed by correlated disruptions: when a shared input such as a common supplier, a specialized team, or a supporting platform degrades, all dependent activities are slowed down simultaneously. This paper introduces delay groups to capture such disruptions: a delay group is a set of activities whose delays stem from a common cause, described jointly by an uncertainty set. Our model takes the perspective of an interdictor that, subject to a budget of $k$ groups, selects which groups to disrupt so as to maximize the project makespan. The interdictor can extend activity durations within each disrupted group by delays from a group-specific uncertainty set, while non-disrupted activities keep their nominal duration. We study the complexity of the resulting Project Scheduling Interdiction Problem with Delay Groups (PSIP-DG), which provides a worst-case stress test of the schedule. The problem is computationally intractable ($N\!P$-hard) for general polyhedral uncertainty sets, even for a single delay group with a continuous knapsack constraint. For budgeted uncertainty sets, we prove $N\!P$-hardness both when all activities of a disrupted group are delayed and when only one activity per group may be delayed, and derive an inapproximability bound of $1-1/e+\epsilon$ for the former case. We further develop a greedy heuristic with approximation guarantee $k$ and two structure-based heuristics with initializations and neighborhoods from tractable special cases. Experiments on $5{,}000$-activity networks show that the heuristics match the solution quality of an exact solver at substantially lower running times, in some cases finding strictly better solutions.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#sentencerolethe authors' own workstates the main conclusionstrength
s0 Large-scale projects are frequently delayed by correlated disruptions: when a shared input such as a common supplier, a specialized team, or a supporting platform degrades, all dependent activities are slowed down simultaneously. background 1.00 0.07 0.02 asserted 0.98
s1 This paper introduces delay groups to capture such disruptions: a delay group is a set of activities whose delays stem from a common cause, described jointly by an uncertainty set. contribution 0.73 0.81 0.05 asserted 1.00
s2 Our model takes the perspective of an interdictor that, subject to a budget of $k$ groups, selects which groups to disrupt so as to maximize the project makespan. method 0.75 0.51 0.08 asserted 0.99
s3 The interdictor can extend activity durations within each disrupted group by delays from a group-specific uncertainty set, while non-disrupted activities keep their nominal duration. method 0.99 0.37 0.04 asserted 1.00
s4 We study the complexity of the resulting Project Scheduling Interdiction Problem with Delay Groups (PSIP-DG), which provides a worst-case stress test of the schedule. contribution 0.90 0.85 0.09 asserted 0.94
s5 The problem is computationally intractable ($N\!P$-hard) for general polyhedral uncertainty sets, even for a single delay group with a continuous knapsack constraint. result 0.97 0.83 0.14 asserted 1.00
s6 For budgeted uncertainty sets, we prove $N\!P$-hardness both when all activities of a disrupted group are delayed and when only one activity per group may be delayed, and derive an inapproximability bound of $1-1/e+\epsilon$ for the former case. result 0.95 0.96 0.18 asserted 1.00
s7 We further develop a greedy heuristic with approximation guarantee $k$ and two structure-based heuristics with initializations and neighborhoods from tractable special cases. method 0.68 0.97 0.10 asserted 1.00
s8 Experiments on $5{,}000$-activity networks show that the heuristics match the solution quality of an exact solver at substantially lower running times, in some cases finding strictly better solutions. result 1.00 0.96 0.21 asserted 1.00

What kind of paper the classifier reports this is: theoretical result 0.59 · evidence from proof or derivation 0.81.

What was examined, and what was not

sources read
  • arXiv listing abstract v1
not examined
  • full text
  • figures and tables
  • references and citing sentences
  • relations to other papers
levels run
  • P abstract
not run
  • S sections
  • T body sentences
  • C citations
  • R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

Figures
Figure 1. Project network (left) and delay groups Vr, duration vector d, delay vector ∆, and interdiction budget k (right). In this setting, PSIP-DGB evaluates which delay groups and activities, if disrupted, would cause the largest increase in the project makespan. Under nominal durations the project makespan is 13, while an 8
Figure 2. Construction of the reduction from Partition to PSIP Let ℓ ∗ (x) denote the length of the longest path in the constructed instance under the solution x ∈ [0, 1]n. Each 0-(n + 1)-path contains either vi1 or vi2, hence ℓ ∗ (x) = max{2c1x1, c1} + · · · + max{2cnxn, cn} = 2b + X i∈[n]:xi>0.5 2cixi − ci . (1) Next, we show that if the optimal solution value of the PSIP instance is 3b, then there also is a feasible solution to the Partition instance. Consider an optimal extreme point solution x ∗ to the PSIP instance with value ℓ ∗ (x ∗ ) = 3b. By Observation 3.3, there exists a
Figure 3. Construction of the reduction from Max k-cover to PSIP-DG Now suppose that U has a set cover I of size k. For each subset S ∈ I, let VS be the associated delay group and the delay groups selected by the interdictor are VI = {VS : S ∈ I}. We have |VI | = |I| = k. Furthermore, for any i ∈ [n], there exists S ′ ∈ I such that ui ∈ S ′ , and thus, Aui ∩ VS′ ̸= ∅. The interdictor can increase all the activities’ durations to 1 within V , then P e=(i,j)∈E ye
Figure 4. Construction of the reduction from 3-SAT to PSIP-DGB,1 The collection of delay groups V is constructed as described above, where m = |V|. Let dv = 0 for all v ∈ V and ∆r(v) = 1 for v ∈ Vr and r ∈ [m]. The interdiction budget is set as k = q · mq, which completes the construction of the problem instance. Next, we show that the maximum interdicted project makespan is q · mq if and only if there exists a satisfying truth assignment for the 3-SAT instance. First, assume there exists a truth assignment A fulfilling all clauses. For each i ∈ [q], there exists i(A) ∈ [3] such that ℓii(A) ∈…
Figure 5. DGap of the initial (grey) and final (black) solutions of SRS and GSS for both variants. relaxation of the model (Section 4.2.1); for the case where ℓ = 1, this relaxation is especially tight, so the initial path is nearly optimal and the search converges after exploring only a few neighbors. On the other hand, in PSIP-DGB,∞ the situation is reversed: the initial solution of GSS is already good, whereas that of SRS is far from optimal. The initial DGap of GSS lies between about 4% and 8%, while SRS starts with an initial DGap of 10% to 17%. Consequently, the search phase of SRS must…
Figure 6. Running time (a) and solution quality (b) of GSS versus Gurobi on the extra-large PSIP-DGB,∞ instances. Faint markers are individual instances, solid lines are means; in (b), a negative Gap (dark red) means that GSS finds a better solution than Gurobi’s incumbent. 6. Conclusions We study the structural impact of correlated disruptions on precedence-based project scheduling by introducing delay groups into a network interdiction model. Our model builds on earlier interdiction models (Brown et al., 2009) and can serve as a basis for future extensions to more general project settings.…

Figures reproduced from arXiv:2608.27386 by the authors.

References

Discussion

Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.