A probe-based algorithm for piecewise linear optimization in scheduling
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.
- On the optimality of linear schedules
- Line search method for solving a non-preemptive strictly periodic scheduling problem
- Probe backtrack search for minimal perturbation in dynamic scheduling
- An experimental study of LP-based approximation algorithms for scheduling problems
- scientific article; zbMATH DE number 1131737
- Synthesizing optimization algorithms for scheduling partially ordered set of problems
- scientific article; zbMATH DE number 1418275
- scientific article; zbMATH DE number 1982192
- On the optimality of exact and approximation algorithms for scheduling problems
- A note on appointment scheduling with piecewise linear cost functions
This page was built for publication: A probe-based algorithm for piecewise linear optimization in scheduling
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1861934)
