[Back]

M. Horn, G. Raidl, E. Rönnberg:
"An A* Algorithm for Solving a Prize-Collecting Sequencing Problem with One Common and Multiple Secondary Resources and Time Windows";
in: "Annals of Operations Research", 10479; Springer, 2018, 235 - 256.

Abstract In the considered sequencing problem, a subset of a given set of jobs is to the be scheduled. A scheduled job has to execute without preemp-tion 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 may not be possible to schedule all jobs. Instead, each job is as-sociated with a prize and the task is to select a subset of jobs which yields a feasible schedule with a maximum total sum of prizes. First, we argue that the problem is NP-hard. Then, we present an exact A* algorithm and derive di erent upper bounds for the total prize; these bounds are based on con-straint and Lagrangian relaxations of a linear programming relaxation of a multidimensional knapsack problem. For comparison, a compact mixed inte-ger programming (MIP) model and a constraint programming model are also presented. An extensive experimental evaluation on two types of problem in-stances shows that the A* algorithm outperforms the other approaches and is able to solve small to medium size instances with up to about 50 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.

https://publik.tuwien.ac.at/files/publik_273227.pdf