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 discrete start and end time distributions are given but the actual times are 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.