A probe-based algorithm for piecewise linear optimization in scheduling (Q1861934)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A probe-based algorithm for piecewise linear optimization in scheduling |
scientific article |
Statements
A probe-based algorithm for piecewise linear optimization in scheduling (English)
0 references
10 March 2003
0 references
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.
0 references
linear programming
0 references
constraint programming
0 references
scheduling
0 references
hybrid algorithms
0 references