Linear weighted-task-sum - scheduling prioritized tasks on a single resource

Optimized task scheduling is in general an NP-hard problem, even if the tasks are prioritized like surgeries in hospitals. Better pruning algorithms for the constraints within Such constraint optimization problems, in particular for the constraints representing the objectives to be optimized, will result in faster convergence of branch & bound algorithms. This paper presents new pruning rules for linear weighted (task) sums where the summands are the start times of tasks to be scheduled on an exclusively available resource and weighted by the tasks' priorities. The presented pruning rules are proven to be correct and the speed-up of the optimization is shown in comparison with well-known general-purpose pruning rules for weighted sums.