A probe-based algorithm for piecewise linear optimization in scheduling (Q1861934)

The authors consider the following problem. There is a set of activities. The cost of each activity depends on its start time and assigned resources, this dependency being described by a piecewise linear (PL) function. The start times are all discrete and are constrained by a given set of temporal constraints. The resource constraints state that at each time point of the schedule horizon, the activities do not consume more than the available resources. The cost of the schedule is measured by a non-convex PL objective function which is the sum of the costs of the activities. The objective is to generate a schedule that is resource feasible, satisfies the given temporal constraints, and minimizes the cost by timing the activities appropriately. The authors note that the problem under consideration is NP-hard. To solve it, the authors present the so called probe backtrack hybrid algorithm where Constraint Programming (CP) search is supported and driven by a (integer) linear programming solver running on a well-controlled subproblem which is dynamically tightened. Some probing strategies are systematically evaluated and compared. The authors show how the subproblem structure and the piecewise linearity are exploited by the search.