A Series-Parallel digraph based relaxation for the COMPLETION constraint

In 2011, Kovács and Beck defined the completion global constraint for minimizing the weighted flowtime for a single resource. This constraint is part of the cost-based domain filtering approach and as such, aims at removing values from the variables domains that cannot lead to a solution with a better cost than the best one found so far. The completion constraint uses a polynomial time relaxation that minimizes the weighted mean busy time on a single unary capacity resource with release dates and preemption. In this ongoing work, we consider another polynomial time relaxation that directly minimizes the weighted completion time without preemption where the precedence constraints form a Series-Parallel digraph. This is one of the first attempt use a relaxation without preemption. We discuss how to build a Series-Parallel digraph from the time windows of the tasks or directly working on their interval graph.