Dynamic Interval Scheduling with Random Start and End Times
Abstract
We study sequential interval scheduling with random task start and end times. Task weights and the discrete distributions of task intervals are known, but each task's realized interval is revealed only upon commitment; this also eliminates tasks that conflict with the committed task. The objective is to maximize the expected weight of a conflict-free schedule. We propose two models that differ in how conflicts are enforced, develop relaxations and bounds for each, and present a computational study.
Fields of Study & Subjects
Scheduling and Optimization Algorithms
Scheduling and Timetabling Solutions
Optimization and Search Problems
Publication details
- Journal / source
- arXiv (Cornell University)
- Publication date
- 6 February 2026
- Language
- EN
- Document type
- Preprint