[Back]


Publications in Scientific Journals:

J. Maschler, G. Raidl:
"Multivalued decision diagrams for prize-collecting job sequencing with one common and multiple secondary resources";
Annals of Operations Research, 302 (2021), 507 - 531.



English abstract:
Multivalued decision diagrams (MDD) are a powerful tool for approaching combinatorial
optimization problems. Relatively compact relaxed and restrictedMDDsare 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 restrictedMDDs 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


"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
http://dx.doi.org/10.1007/s10479-019-03479-6

Electronic version of the publication:
https://publik.tuwien.ac.at/files/publik_301809.pdf


Created from the Publication Database of the Vienna University of Technology.