Search: onr:"swepub:oai:DiVA.org:liu-164869" >
A* Search for Prize...
Abstract
Subject headings
Close
- We consider a sequencing problem with time windows, in which a subset of a given set of jobs shall be scheduled. A scheduled job has to execute without preemption and during this time, the job needs both a common resource for a part of the execution as well as a secondary resource for the whole execution time. The common resource is shared by all jobs while a secondary resource is shared only by a subset of the jobs. Each job has one or more time windows and due to these, it is not possible to schedule all jobs. Instead, each job is associated with a prize and the task is to select a subset of jobs which yields a feasible schedule with a maximum sum of prizes. First, we argue that the problem is NP-hard. Then, we present an exact A* algorithm and derive different upper bounds for the total prize; these bounds are based on constraint and Lagrangian relaxations of a linear programming relaxation of a multidimensional knapsack problem. For comparison, a compact mixed integer programming (MIP) model and a constraint programming model are also presented. An extensive experimental evaluation on three types of problem instances shows that the A* algorithm outperforms the other approaches and is able to solve small to medium size instances with up to about 40 jobs to proven optimality. In cases where A* does not prove that an optimal solution is found, the obtained upper bounds are stronger than those of the MIP model.
Subject headings
- NATURVETENSKAP -- Matematik -- Beräkningsmatematik (hsv//swe)
- NATURAL SCIENCES -- Mathematics -- Computational Mathematics (hsv//eng)
Keyword
- Sequencing; A* algorithm; Particle therapy patient scheduling
Publication and Content Type
- ref (subject category)
- art (subject category)
Find in a library
To the university's database