<div class="csl-bib-body">
<div class="csl-entry">Maschler, J., & Raidl, G. (2021). Multivalued decision diagrams for prize-collecting job sequencing with one common and multiple secondary resources. <i>Annals of Operations Research</i>, <i>302</i>, 507–531. https://doi.org/10.1007/s10479-019-03479-6</div>
</div>
-
dc.identifier.issn
0254-5330
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/20286
-
dc.description.abstract
Multivalued decision diagrams (MDD) are a powerful tool for approaching combinatorial optimization problems. Relatively compact relaxed and restricted MDDs are applied to obtain dual bounds and heuristic solutions and provide opportunities for new branching schemes. We consider a prize-collecting sequencing problem in which a subset of given jobs has to be found that is schedulable and yields maximum total prize. The primary aim of this work is to study different methods for creating relaxed MDDs for this problem. To this end, we adopt and extend the two main MDD compilation approaches found in the literature: top down construction and incremental refinement. In a series of computational experiments these methods are compared. The results indicate that for our problem the incremental refinement method produces MDDs with stronger bounds. Moreover, heuristic solutions are derived by compiling restricted MDDs and by applying a general variable neighborhood search (GVNS). Here we observe that the top down construction of restricted MDDs is able to yield better solutions as the GVNS on small to medium-sized instances.
en
dc.language.iso
en
-
dc.publisher
SPRINGER
-
dc.relation.ispartof
Annals of Operations Research
-
dc.rights.uri
http://creativecommons.org/licenses/by/4.0/
-
dc.subject
incremental refinement
en
dc.subject
multivalued decision diagram
en
dc.subject
particle therapy patient scheduling
en
dc.subject
sequencing
en
dc.title
Multivalued decision diagrams for prize-collecting job sequencing with one common and multiple secondary resources