A polynomial activity insertion algorithm in a multi-resource schedule with cumulative constraints and multiple modes

摘要

In this paper, a polynomial activity insertion algorithm in a multi-resource schedule with cumulative constraints, general precedence relations and multiple modes is proposed. Insertion objective is to minimize the resulting impact on maximum lateness, while keeping some essential characteristics of the initial schedule. A new disjunctive arc-based representation with multiple capacities associated to resource arcs is proposed. Under specific constraints, some simple dominance rules allow to find an optimal insertion position in the digraph with low-computational requirements.