CS Paper Radar

The Project Scheduling Interdiction Problem with Delay Groups

Fei Wu, Erik Demeulemeester, Jannik Matuschke

cs.DM ·submitted 2026-08-27 17:20 UTC · v1
publishedtheory

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+ε$ 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.

Closest papers

Nearest neighbours by meaning across the whole index.

Speed-Robust Scheduling for Total Completion Time

cs.DS cs.DM ·2026-11-16 ·Moritz Buchem, Nicole Megow, Morten Weber
similarity 0.56
Abstract

We study two-stage speed-robust scheduling for minimizing total completion time. Jobs must be partitioned into $M$ bags before an adversary reveals the speeds of at most $M$ machines. Each bag is then assigned to one available machine, and the jobs on each machine may be processed in any order independent of the bags. We compare with an optimal schedule that knows the speeds in advance and assigns jobs individually. This model has been studied for makespan minimization. We initiate its study for total completion time, as suggested by Stein and Zhong (TALG 2020). For an unknown number of identical machines, we show that the optimal deterministic robustness factor is exactly~$13/12$, both for unit-size jobs and for arbitrary processing times. For infinitesimally small jobs, the factor lies between $31/30\approx1.0333$ and $28/27\approx1.0370$, well below the optimal makespan factor of about $1.2071$. General speeds make the problem strictly harder: no deterministic algorithm is better than $1.2669$-robust, already for infinitesimally small jobs. We give a $25/16$-robust algorithm for arbitrary processing times and improve the guarantee to $1681/1152\approx1.4592$ for infinitesimally small jobs. Our main tools are a layer decomposition that extends guarantees from unit-size jobs to arbitrary processing times when one assignment satisfies them for every prefix in non-increasing processing-time order, and a threshold analysis of the bag counts produced by greedy assignment rules.

0.31

Scheduling with Mandatory Breaks: NP-Hardness and an Additive-One Approximation

cs.DS ·2026-09-28 ·Shreyas Ghildiyal, Muralidhara V N
similarity 0.56
Abstract

In classical fixed-interval scheduling, each job of a given set must be processed during a prescribed time interval. The goal is to assign each job to exactly one machine such that no two jobs assigned to the same machine overlap in their interiors, and the number of machines used is minimized. Without further constraints this is interval graph coloring and is solvable in polynomial time through greedy approaches. We study a variant in which every used machine must remain idle during a contiguous \emph{break} of prescribed length $x$ somewhere in the scheduling horizon. We show that this additional constraint makes the problem hard, except when $x\le1$. First, for every fixed $x\ge2$, deciding whether $k$ machines suffice for the assignment of a given set of jobs is NP-complete, even when all coordinates are bounded linearly in the number of jobs, so machine minimization is strongly NP-hard. Second, for $x=1$, we give a polynomial-time algorithm that solves the problem exactly. Finally, we give a deterministic polynomial-time algorithm that, on every feasible instance, outputs a schedule using at most $\OPT+1$ machines, where $\OPT$ is the true minimum. Unless $\mathrm{P}=\mathrm{NP}$, no polynomial-time algorithm guarantees $\OPT$ machines for any fixed $x\ge2$, so the additive guarantee of one is best possible.

0.07

The Complexity of Value Optimization in Sporadic Task Systems

cs.CC cs.DS ·2026-10-26 ·Christopher Harbourne, Nathan Fisher, Kecheng Yang, Pontus Ekberg, Sanjoy Baruah +1 more
theory similarity 0.56
Abstract · 31 pages, 5 figures, 2 tables

Value-based Task Selection (VTS) asks whether a real-time system can select tasks whose total value reaches a required target while preserving every deadline. We study its threshold decision form for finite collections of independent sporadic tasks scheduled preemptively on one processor. We prove that this problem is $Σ_2^P$-complete for both constrained and arbitrary deadlines, even when all numerical parameters are encoded in unary. The existential choice is the selected task set, while the universal condition requires every processor-demand window to remain feasible. Our hardness reduction already uses constrained-deadline tasks. It represents universal assignments by Chinese Remainder Theorem timestamps and uses polynomial-weight local selector locks to enforce a valid existential assignment. The reduction produces polynomially many tasks, and every generated execution time, deadline, period, task value, and target is polynomially bounded in the source-instance size.

0.25

Integrality gap preserving reductions

cs.DM cs.DS ·2026-09-17 ·Koppány István Encz, Monaldo Mastrolilli, Eleonora Vercesi
theory similarity 0.55
Abstract · 30 pages, 2 figures

We propose a framework for the systematic study of integrality gaps of combinatorial optimization problems with respect to a fixed linear programming formulation. The method, called \emph{integrality gap preserving reduction}, consists of iteratively shrinking the input universe of the problem while guaranteeing that gap-maximizing instances remain selected. When the subset of remaining instances becomes specific enough, we calculate the integrality gap explicitly. Besides applying integrality gap preserving reductions to three well-known optimization problems via their standard linear programming formulations (weighted vertex cover problem, multiple knapsack problem, and unrelated machine scheduling problem), we analyse the restricted assignment problem via its configuration LP relaxation. We prove that the integrality gap is equal to $1$ for three ``easy'' subclasses of the problem that are either solvable in polynomial time or admit a PTAS (e.g., the all-one processing time case). For some remaining cases, we improve the current lower bound using our technique.

0.42

Planning and Scheduling Business Processes under Control-Flow Uncertainty: Extended Version

cs.AI ·2026-09-04 ·Michel Kunkler, Stefanie Rinderle-Ma
similarity 0.54
Abstract

Scheduling activities in business processes can improve efficiency (e.g., reduce makespan), but is challenging because the exact sequence of activities required to complete a case is often uncertain due to decisions based on data that emerges during execution. Nevertheless, probabilistic information regarding such decisions can often be estimated or derived from historical execution logs, and can help anticipate which execution paths are likely to lead to successful completion. Planning with particular execution paths affects feasibility, i.e., the probability of successful completion, and the expected number of superfluous activities that are planned but never executed. We frame the problem as a chance-constrained optimization problem and present two formulations: A decomposed approach with two stages, a planning stage that minimizes the expected number of superfluous activities subject to a feasibility constraint, and a scheduling stage that minimizes the makespan over the planned activities; and an integrated approach that combines planning and scheduling into a single formulation. Evaluation on two real-world and one synthetic dataset shows that the integrated approach yields superior makespans but is intractable at scale, while the decomposed approach scales to large settings.

0.22

Approximation algorithms for identical parallel machine scheduling with assignment costs

cs.DS ·2026-10-24 ·Wei Li
similarity 0.54
Abstract

We study non-preemptive scheduling on identical parallel machines in which assigning job $j$ to machine $M_i$ incurs the cost $c_{ij}=a_iw_j+b_j$. The processing times $p_j$ and the cost weights $w_j$ are independent, and the number of machines is part of the input. For every fixed $\varepsilon\in(0,1]$ and every deadline $T$ for which a schedule with makespan at most $T$ exists, we give a polynomial-time algorithm that computes a schedule with makespan at most $(1+\varepsilon)T$ whose total assignment cost does not exceed the minimum under the deadline $T$. Using this algorithm as a subroutine, we obtain a polynomial-time approximation scheme for minimizing the makespan under a total cost budget whose schedules always satisfy the budget; this answers an open question for costs $c_{ij}=l_ic_j$ with $c_j$ independent of $p_j$. For the lexicographic problem, in which the total assignment cost is minimized among all schedules of minimum makespan, we obtain in polynomial time a schedule with makespan at most $1+\varepsilon$ times the minimum and total assignment cost at most that of a lexicographically optimal schedule; this improves the makespan guarantees of earlier algorithms for additive and multiplicative costs. For costs $c_{ij}=s_i+a_iw_j$, where $s_i$ is charged for each job processed on $M_i$, the same guarantees are obtained in quasi-polynomial time.

0.24

Diverse Schedules for Makespan Minimization on Unrelated Machines

cs.DS ·2026-10-20 ·Sebastian Bruchhold, Matthias Mnich, Karolina Tammemaa, Morten Weber, Michalis Xefteris +1 more
similarity 0.53
Abstract · Updated funding acknowledgment, scientific content unchanged

We study makespan minimization on unrelated machines with the additional goal of constructing diverse schedules: Instead of outputting a single schedule, we seek a collection of schedules with provable makespan guarantees and substantially different job assignments. Committing to a single schedule in advance may be undesirable. Processing times may be uncertain, and constraints or domain knowledge may emerge later, so $k$ schedules of similar quality offer meaningful alternatives. We measure pairwise diversity by the weighted Hamming distance between job assignments and study the two standard objectives in the diverse-solutions literature: max-sum diversity, which maximizes the total pairwise distance between schedules, and max-min diversity, which maximizes the smallest pairwise distance. For the max-sum objective, we show that optimal diversity can be achieved in polynomial time without sacrificing the classic makespan approximation factor. For every feasible makespan target $T$, we can compute $k$ schedules of makespan at most $2T$ whose max-sum diversity is optimal among all $k$ schedules of makespan at most $T$. Therefore, we match the classic factor-$2$ makespan guarantee of Lenstra, Shmoys, and Tardos (Math. Prog., 1990) and preserve optimal diversity. For the max-min objective, we show that the diversity problem is inherently harder. Namely, we show that, even without makespan constraints, deciding whether three schedules of given pairwise diversity exist is NP-hard. We complete this with two complementary bicriteria approximation algorithms for every fixed $k$ and $\varepsilon \in (0,1)$. The first preserves almost all of the optimal max-min diversity with makespan at most $(3\lceil12/\varepsilon\rceil+1)T$. The second keeps the makespan arbitrarily close to the classic $2$ guarantee while achieving a $\frac{1}{2}(1-\varepsilon)$ fraction of the optimal max-min diversity.

0.20

Online Bin Packing with Dispatch Deadlines

cs.DS ·2026-11-05 ·Pei-Lin Chiang, Wing-Kai Hon, Kazuo Iwama, Li-Tzu Yang
published similarity 0.52
Abstract · 16 pages, 1 figure. Full version of a paper to appear in the 37th International Symposium on Algorithms and Computation (ISAAC 2026)

We study a generalization of online bin packing by introducing dispatch deadlines. Items arrive over time in an online fashion. Each item has an arrival time, a size in $(0,1]$, and a deadline, all of which are revealed only when the item arrives. The algorithm must immediately and irrevocably assign the item to a unit-capacity bin that has not yet been dispatched. Each bin must be dispatched no later than the earliest deadline of the items assigned to it, and once it is dispatched, it cannot be used for future items. The goal is to minimize the number of bins used. Applications arise naturally in logistics. Additionally, the offline version of this problem has appeared under several names, including the clique partition problem in weighted interval graphs and the BinSchedule problem. This problem is also a special case of online bin packing with conflicts and is closely related to online bin packing models with delay costs. We study the competitive ratios of several classical online bin packing algorithms when applied to this problem, and show that a similar hierarchy of competitive ratios carries over. Our main technical results are that the competitive ratio of First-Fit is exactly $16/7 \approx 2.28571$, and that no deterministic online algorithm has a competitive ratio less than $11/5 = 2.2$, showing that First-Fit is quite close to best possible. In addition, Next-Fit and Worst-Fit have competitive ratio exactly $3$, and every algorithm in the Any-Fit class has competitive ratio between $16/7$ and $3$.

0.36