Source-linked AI summary
The Project Scheduling Interdiction Problem with Delay Groups
Fei Wu, Erik Demeulemeester, Jannik Matuschke
TL;DR
The paper models project delays caused by disruptions affecting multiple activities through common delay groups and an interdiction perspective. It establishes computational hardness for the resulting problem, including budgeted uncertainty when either one or all activities per group may be delayed.
Problem
Large-scale project disruptions can affect several activities simultaneously when they share an underlying supplier, specialized team, or supporting platform.
Method
The paper introduces delay groups and models an interdictor that selects groups to disrupt, maximizing project makespan under group-specific delay uncertainty.
Results
The problem is NP-hard for general polyhedral uncertainty sets and for budgeted uncertainty when either at most one or all activities within each group can be delayed.
Takeaways & Limitations
The model extends network interdiction to represent correlated activity delays and uses worst-case makespan as a schedule stress test.
Takeaways & Limitations
The analysis focuses on the extreme cases where each group affects either one activity or an unrestricted number of activities, while open problems remain between known hardness results.
Abstract
from arXiv · showhide
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+ε$ 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.
1. Introduction
The paper introduces delay groups to model correlated activity slowdowns and formulates their worst-case impact as an interdiction problem. It establishes computational hardness and develops approximation and heuristic methods for identifying vulnerable groups and stress-testing project schedules.
- Motivation and model: Delay groups represent activities slowed by a common cause, with their joint delays described by an uncertainty set.The model targets shared suppliers, specialist teams, and supporting platforms whose degradation affects dependent activities together.
- Complexity: The problem is NP-hard even without resource constraints, including restricted settings with a single group or groups of at most two activities.The hardness arises from both selecting groups and allocating delays within groups.
- Motivation and model: PSIP-DG lets an interdictor attack at most k groups, choose feasible group delay vectors, and maximize the project makespan.The resulting worst-case completion time serves as a schedule stress test under bounded correlated disruptions.
- Complexity: The paper proves NP-hardness for continuous PSIP with non-uniform interdiction costs and uses this result to establish hardness for PSIP-DG.The analysis also covers budgeted uncertainty when all activities or only one activity per group may be delayed.
- Complexity: PSIP-DG has no (1−1/e+ε)-approximation for any ε > 0 unless P = NP.This inapproximability result applies to the relevant restricted case and quantifies a limit on efficient approximation.
- Algorithms and experiments: A greedy heuristic with guarantee k and two structure-based heuristics provide near-optimal solutions much faster than exact optimization on large networks.On large-scale instances, GSS matches Gurobi’s best solution quality within one hour and can sometimes find strictly better solutions.
2. Problem definition
PSIP-DG models a precedence-constrained project in which an interdictor selects delay groups and feasible activity delays to maximize the longest-path makespan. The formulation supports polyhedral and budgeted uncertainty, including cases where all or only one activity in a group may be delayed.
- Project network: A project is represented by an acyclic PERT network whose nodes are activities and whose arcs encode precedence constraints.Dummy nodes mark project start and finish, and the makespan is the longest path from the start dummy to the end dummy.
- Delay groups: Delay groups partition the activities, with each group Vr associated with an uncertainty set Qr of feasible delay vectors.The formulation assumes groups are disjoint; overlapping memberships can be transformed using sequential duplicate copies without changing makespan.
- Interdiction model: The interdictor chooses a subset S of at most k groups and delay vectors for attacked groups, then maximizes the longest-path length under prolonged durations.Binary variables indicate attacked groups, while start times and duration changes enforce the project scheduling formulation.
- Uncertainty sets: Polyhedral uncertainty sets encode group delays through linear inequalities, including aggregate constraints that trade delay assigned to one activity against delays assigned to others.A shared-team example uses individual upper bounds together with a total-delay bound βr.
- Budgeted uncertainty: Budgeted uncertainty limits the number of delayed activities in each group to ℓr while assigning fixed delay increments Δi.The paper studies PSIP-DGB,∞, where all group activities may be delayed, and PSIP-DGB,1, where only one may be delayed.
- Illustrative example: In the illustrative instance, the nominal makespan is 13 and the optimal attack on V2 and V3 raises it to 18 along path 0–3–5–8–9.Although each single-group attack yields makespan 15, combinations differ because selected groups interact through the project network.
3. Complexity results for PSIP-DG
PSIP-DG has tractable special cases, but its optimization becomes NP-hard under general polyhedral and budgeted uncertainty, including restricted delay-group settings.
- Tractable cases: O(k|E|) dynamic programming solves PSIP when each activity forms its own singleton delay group.Here |E| denotes the number of project-network edges.
- Tractable cases: When each delay group is an anti-chain, disruptions across groups are independent and the problem reduces to separate per-group computations.The resulting longest-path subproblem is solvable in O(ℓr|E|) time, and the overall value is the maximum per-group value.
- General uncertainty: NP-hardness already holds for PSIP with continuous interdiction and non-uniform costs.The result is counterintuitive because interdiction variables are continuous rather than binary.
- General uncertainty: PSIP-DG is NP-hard under polyhedral uncertainty even with a single delay group.The reduction establishes hardness for the continuous case and implies the corresponding binary-policy result.
- Budgeted uncertainty: PSIP-DGB,∞ is NP-complete and cannot be approximated within 1 −1/e + ϵ unless P = NP.The inapproximability result follows from the reduction from Max k-cover.
- Budgeted uncertainty: PSIP-DGB,1 remains NP-complete even when only one activity per group may be delayed.The hardness persists for relatively small groups larger than one, under the stated budget condition.
4. Heuristic algorithms for PSIP-DG_B
The paper develops a greedy method and two complementary local-search heuristics for budgeted PSIP-DG, using exact subproblem evaluations and tractable-case initializations.
- Structure-based heuristics: SRS searches over paths, while GSS searches over interdiction policies, solving the other variable block exactly for each candidate.SRS uses dynamic programming for restricted interdiction; GSS uses longest-path evaluation for candidate policies.
- Greedy heuristic: The greedy heuristic adds delay groups one at a time in non-increasing attack-profit order.At each step it selects the group that increases a longest path the most and computes its individual impact through MAX(ℓ, r).
- Greedy heuristic: k-approximation is guaranteed for the greedy heuristic.The proof bounds the optimal makespan increase using the first selected group’s impact.
- Structure-based heuristics: SRS initializes from a longest-path relaxation, whereas GSS starts with the k groups having the largest individual contributions.Both heuristics use tractable special cases to construct their initial solutions.
- Motivation for search: Group interactions make individual impacts insufficient because the makespan-increase function is neither additive nor submodular.In the example, W1 = W2 = W3 = 2, but f({2, 3}) = 5 and f({1, 3}) = 4.
- Neighborhood search: Neighborhood candidates are filtered approximately but evaluated exactly, and the search stops at a neighbor limit or when no improvement remains.This procedure applies to the local exploration underlying the structure-based heuristics.
5. Computational study
The computational study evaluates SRS and GSS on generated PSIP-DGB networks against Gurobi, using solution quality and running time. Results show variant-dependent strengths, with GSS especially effective on large and extra-large PSIP-DGB,∞ instances.
- Experimental setup: The study compares SRS and GSS with an exact Gurobi MIP approach using solution quality and running time as metrics.Quality is measured against Gurobi’s best solution within 3,600 seconds, which is optimal when optimality is proven.
- Experimental setup: The experiments use RanGen networks with 50–900 activities and additional layered DAGs containing up to 5,000 nodes.Generated instances vary in network structure, density, and size.
- PSIP-DGB,1: SRS outperforms GSS on PSIP-DGB,1, finding an optimal solution on 85.4% of instances and staying within 1% of optimum on 94.7%.Its average search improvement is limited because initial paths are already close to optimal.
- PSIP-DGB,∞: GSS outperforms SRS on PSIP-DGB,∞, with Gap below 1.4% across instance sets while requiring less than 0.5 seconds on average.SRS achieves lower average Gap in the reported comparison but requires up to four seconds on average.
- Comparison with Gurobi: For instance 900_0.1_60_5_ii, GSS reaches a 0.14% Gap and 0.75% DGap in 0.12 seconds, while Gurobi takes 3,582 seconds.Across medium, large, and extra-large sets, GSS remains within 0.45%–1.31% Gap and uses substantially less time.
6. Conclusions
The paper formulates PSIP-DG for correlated activity delays, establishes complexity and approximation results, and develops heuristics that perform well computationally. It also identifies tractable structures and several directions for extending and validating the framework.
- PSIP-DG models an interdictor selecting delay groups within a limited budget to maximize project completion time under group-specific uncertainty sets.
- NP-hardness holds for continuous PSIP with non-uniform costs, general polyhedral uncertainty sets, and budgeted uncertainty even when one or all group activities may be delayed.
- Two structure-based heuristics use tractable special cases: SRS improves candidate paths, while GSS improves attacked-group selections.
- SRS achieves higher solution quality for PSIP-DGB,1, whereas GSS performs better for PSIP-DGB,∞ and can match or exceed Gurobi solutions with less running time.
- The study is limited to the extreme cases of one or unrestricted affected activities per group, leaving intermediate group-delay structures open.
Appendix A. Algorithm details
Appendix A details dynamic-programming routines for longest-path and fixed-path delay calculations, plus path-neighborhood construction.
- Dynamic programming: The appendix describes dynamic programming for the singly constrained longest-path problem.Algorithm A.1 takes a DAG with node durations and delay increments and returns a longest path, delayed-node set, and maximum length.
- Fixed-path delay: Algorithms A.2 and A.3 compute maximum delay on a fixed path under group-wise budget constraints for PSIP-DGB,1 and PSIP-DGB,∞.Their outputs include maximum delay and either attacked nodes or a mapping from groups to attacked nodes.
- Path neighborhoods: Algorithm A.4 constructs path neighborhoods using a path segment, budget, segment length, and per-group delay cap.It returns neighbor paths together with the base path length and base policy.
- Dynamic programming: The longest-path routine topologically orders the DAG and updates predecessor-based states for each node and interdiction budget.Transitions compare nominal and delayed activity durations before backtracking from the terminal state.
- Dynamic programming: The routine reconstructs the selected path and delayed activity set by backtracking through predecessor and delay records.Backtracking starts from the terminal state with budget k.
20: return p∗, V ∗, l∗
The fixed-path dynamic programs track delay and attacked-node choices under a group budget, while the neighborhood routine generates modified paths around a base path.
- PSIP-DGB,1: Algorithm A.2 takes a path and budget k and returns maximum delay with a set of interdicted nodes.Its dynamic-programming state is initialized across groups and budget values.
- PSIP-DGB,∞: Algorithm A.3 takes a path, delay groups, node delays, and budget k and returns maximum delay with a group-to-attacked-node mapping.The state stores an empty map initially and updates it when a higher value is found.
- Path neighborhoods: The path-neighborhood routine takes a path, budget, segment length, and per-group delay cap, then returns neighbor paths, base length, and base policy.It limits the subproblem budget by min{k, 2 · num}.
- Path neighborhoods: For each segment, the routine combines a modified subpath with the unchanged prefix and suffix of the original path.Remaining nodes are sorted by non-increasing delay increments to form an optimistic bound outside the segment.
Appendix B.1. MILP formulation used with Gurobi
The MILP formulation linearizes the nonlinear PSIP-DGB objective by splitting each physical arc into nominal and delayed alternatives controlled by binary decisions.
- Linearization: The original PSIP-DGB formulation contains products of binary variables, producing a nonlinear objective.The paper linearizes it using an arc-splitting technique.
- Linearization: Arc splitting replaces each physical arc with two parallel arcs having fixed lengths, while binary decisions determine which arcs carry flow.This preserves the choice between nominal and delayed traversal within a linear formulation.
- Flow variables: For each arc, two flow variables represent the default length d_i and delayed length d_i + ∆_i.The objective is then written using these nominal and delayed arc alternatives.
- MILP solution: The resulting MILP is solved with Gurobi for PSIP-DGB,1 and PSIP-DGB,∞.The parameter ℓ equals 1 or is sufficiently large to satisfy ℓ ≥ |V_r| for every group.
Appendix B.2. Statistics for the test instances
Appendix B.2 reports test-instance statistics, including extra-large layered-DAG instances generated at several edge densities and group-budget values.
- Test problem statistics: The test problem statistics are reported in Table B.5.The supplied caption identifies the table but does not provide its numerical contents.
- Instance generation: Extra-large instances use a layered-DAG generator with sparse, medium, and dense edge densities.The generator setting does not apply to I2 for these instances.
- Instance generation: The extra-large instance sets use m = 100 and k ∈ {3, 5, 10, 15, 30, 50}.These values are specified per target size.
- Instance sizes: For extra-large sets, |V| denotes target size, while the actual number of activities varies around that target.The nominal 2000-size instances contain about 2,100 to 2,400 nodes.
Appendix B.3. Results for extra-large instances in the case of PSIP-DGB,1
On extra-large PSIP-DGB,1 instances, both heuristics start near optimality and improve very little, while Gurobi remains a fast exact reference.
- At most 1.00% for GSS and 0.10% for SRS, the average improvement over the initial solution is minimal.The SRS relaxation is particularly tight for this variant.
- SRS explores only a handful of neighbors, with N as low as 1, and its Gap rounds to 0.00% on every set.
- GSS is likewise near-optimal, with Gap ≤0.09%.
- Gurobi solves these instances in 2.33 seconds on average and remains the exact reference, so the heuristics provide no runtime advantage here.
- The reported averages use k ∈{3, 5, 10, 15, 30, 50} with m = 100, and gaps are measured against the true optimum.
Appendix B.4. Results for extra-large instances in the case of PSIP-DGB,∞
For extra-large PSIP-DGB,∞ instances, the comparison tracks heuristic and solver performance using runtime, optimality counts, and gap measures.
- Gurobi’s optimality count records how many of the six k-values were solved to proven optimality within one hour.
- A negative Gap or DGap means GSS is better than Gurobi on the corresponding averaged comparison.
- T(s) denotes average CPU time.