{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,31]],"date-time":"2022-03-31T20:18:19Z","timestamp":1648757899864},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2019,11,21]],"date-time":"2019-11-21T00:00:00Z","timestamp":1574294400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,11,21]],"date-time":"2019-11-21T00:00:00Z","timestamp":1574294400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"TU Wien"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Ann Oper Res"],"published-print":{"date-parts":[[2021,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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.\n<\/jats:p>","DOI":"10.1007\/s10479-019-03479-6","type":"journal-article","created":{"date-parts":[[2019,11,21]],"date-time":"2019-11-21T19:37:11Z","timestamp":1574365031000},"page":"507-531","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Multivalued decision diagrams for prize-collecting job sequencing with one common and multiple secondary resources"],"prefix":"10.1007","volume":"302","author":[{"given":"Johannes","family":"Maschler","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"G\u00fcnther R.","family":"Raidl","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,11,21]]},"reference":[{"issue":"3","key":"3479_CR1","doi-asserted-by":"publisher","first-page":"665","DOI":"10.1016\/j.ejor.2016.05.036","volume":"255","author":"A Allahverdi","year":"2016","unstructured":"Allahverdi, A. (2016). A survey of scheduling problems with no-wait in process. European Journal of Operational Research, 255(3), 665\u2013686.","journal-title":"European Journal of Operational Research"},{"key":"3479_CR2","doi-asserted-by":"crossref","unstructured":"Andersen, H. R., Hadzic, T., Hooker, J. N., & Tiedemann, P. (2007). A constraint store based on multivalued decision diagrams. In Principles and practice of constraint programming\u2014CP 2007 (pp. 118\u2013132). Berlin: Springer.","DOI":"10.1007\/978-3-540-74970-7_11"},{"key":"3479_CR3","doi-asserted-by":"crossref","unstructured":"Bergman, D., van Hoeve, W.-J., & Hooker, J. N. (2011). Manipulating MDD relaxations for combinatorial optimization. In Integration of AI and OR techniques in constraint programming for combinatorial optimization problems (pp. 20\u201335). Berlin: Springer.","DOI":"10.1007\/978-3-642-21311-3_5"},{"issue":"2","key":"3479_CR4","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1287\/ijoc.2013.0561","volume":"26","author":"D Bergman","year":"2014","unstructured":"Bergman, D., Cire, A. A., van Hoeve, W.-J., & Hooker, J. N. (2014a). Optimization bounds from binary decision diagrams. INFORMS Journal on Computing, 26(2), 253\u2013268.","journal-title":"INFORMS Journal on Computing"},{"issue":"2","key":"3479_CR5","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1007\/s10732-014-9238-1","volume":"20","author":"D Bergman","year":"2014","unstructured":"Bergman, D., Cire, A. A., van Hoeve, W.-J., & Yunes, T. (2014b). BDD-based heuristics for binary optimization. Journal of Heuristics, 20(2), 211\u2013234.","journal-title":"Journal of Heuristics"},{"key":"3479_CR6","volume-title":"Artificial intelligence: Foundations, theory, and algorithms","author":"D Bergman","year":"2016","unstructured":"Bergman, D., Cire, A. A., van Hoeve, W.-J., & Hooker, J. N. (2016a). Decision diagrams for optimization. In B. O\u2019Sullivan & M. Wooldridge (Eds.), Artificial intelligence: Foundations, theory, and algorithms. Cham: Springer."},{"issue":"1","key":"3479_CR7","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1287\/ijoc.2015.0648","volume":"28","author":"D Bergman","year":"2016","unstructured":"Bergman, D., Cire, A. A., van Hoeve, W.-J., & Hooker, J. N. (2016b). Discrete optimization with decision diagrams. INFORMS Journal on Computing, 28(1), 47\u201366.","journal-title":"INFORMS Journal on Computing"},{"issue":"6","key":"3479_CR8","doi-asserted-by":"publisher","first-page":"1411","DOI":"10.1287\/opre.2013.1221","volume":"61","author":"AA Cire","year":"2013","unstructured":"Cire, A. A., & Hoeve, W. V. (2013). Multivalued decision diagrams for sequencing problems. Operations Research, 61(6), 1411\u20131428.","journal-title":"Operations Research"},{"key":"3479_CR9","series-title":"Lecture notes in computer science","doi-asserted-by":"crossref","first-page":"448","DOI":"10.1007\/978-3-540-85958-1_30","volume-title":"Approximate compilation of constraints into multivalued decision diagrams","author":"T Hadzic","year":"2008","unstructured":"Hadzic, T., Hooker, J. N., O\u2019Sullivan, B., & Tiedemann, P. (2008). Approximate compilation of constraints into multivalued decision diagrams (pp. 448\u2013462)., Lecture notes in computer science Berlin: Springer."},{"key":"3479_CR10","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/978-1-4419-1665-5_3","volume-title":"Handbook of metaheuristics","author":"P Hansen","year":"2010","unstructured":"Hansen, P., Mladenovi\u0107, N., Brimberg, J., & P\u00e9rez, J. A. M. (2010). Variable neighborhood search. In M. Gendreau & J.-Y. Potvin (Eds.), Handbook of metaheuristics (pp. 61\u201386). New York: Springer."},{"issue":"1","key":"3479_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ejor.2009.11.005","volume":"207","author":"S Hartmann","year":"2010","unstructured":"Hartmann, S., & Briskorn, D. (2010). A survey of variants and extensions of the resource-constrained project scheduling problem. European Journal of Operational Research, 207(1), 1\u201314.","journal-title":"European Journal of Operational Research"},{"key":"3479_CR12","doi-asserted-by":"crossref","unstructured":"Hoda, S., van Hoeve, W.-J., & Hooker, J. N. (2010). A systematic approach to MDD-based constraint programming. In Principles and practice of constraint programming\u2014CP 2010 (pp. 266\u2013280). Berlin: Springer.","DOI":"10.1007\/978-3-642-15396-9_23"},{"key":"3479_CR13","doi-asserted-by":"crossref","unstructured":"Hooker, J. N. (2013). Decision diagrams and dynamic programming. In CPAIOR 2013: Integration of AI and OR techniques in constraint programming for combinatorial optimization problems, volume 7874 of LNCS (pp. 94\u2013110). Springer.","DOI":"10.1007\/978-3-642-38171-3_7"},{"key":"3479_CR14","doi-asserted-by":"crossref","unstructured":"Horn, M., Raidl, G., & Blum, C. (2017). Job sequencing with one common and multiple secondary resources: A problem motivated from particle therapy for cancer treatment. In Giuffrida, G., Nicosia, G., Pardalos, P., & Umeton, R. (Eds.), MOD 2017: Machine learning, optimization, and big data\u2014Third international conference, volume 10710 of LNCS (pp. 506\u2013518). Springer.","DOI":"10.1007\/978-3-319-72926-8_42"},{"key":"3479_CR15","unstructured":"Horn, M., Raidl, G., & R\u00f6nnberg, E. (2018). An A* algorithm for solving a prize-collecting sequencing problem with one common and multiple secondary resources and time windows. In PATAT 2018: Proceedings of the 12th international conference of the practice and theory of automated timetabling (pp. 235\u2013256). Vienna, Austria."},{"issue":"3","key":"3479_CR16","doi-asserted-by":"publisher","first-page":"887","DOI":"10.1016\/j.ejor.2016.11.035","volume":"259","author":"J Kinable","year":"2017","unstructured":"Kinable, J., Cire, A. A., & van Hoeve, W. J. (2017). Hybrid optimization methods for time-dependent sequencing problems. European Journal of Operational Research, 259(3), 887\u2013897.","journal-title":"European Journal of Operational Research"},{"issue":"4","key":"3479_CR17","doi-asserted-by":"publisher","first-page":"985","DOI":"10.1002\/j.1538-7305.1959.tb01585.x","volume":"38","author":"CY Lee","year":"1959","unstructured":"Lee, C. Y. (1959). Representation of switching circuits by binary-decision programs. Bell System Technical Journal, 38(4), 985\u2013999.","journal-title":"Bell System Technical Journal"},{"key":"3479_CR18","doi-asserted-by":"publisher","unstructured":"Maschler, J., & Raidl, G. R. (2018a). Particle therapy patient scheduling with limited starting time variations of daily treatments. International Transactions in Operational Research. https:\/\/doi.org\/10.1111\/itor.12579.","DOI":"10.1111\/itor.12579"},{"key":"3479_CR19","unstructured":"Maschler, J., & Raidl, G. R. (2018b). Multivalued decision diagrams for a prize-collecting sequencing problem. In PATAT 2018: Proceedings of the 12th international conference of the practice and theory of automated timetabling (pp. 375\u2013397), Vienna, Austria."},{"key":"3479_CR20","unstructured":"Maschler, J., Riedler, M., Stock, M., & Raidl, G. R. (2016). Particle therapy patient scheduling: First heuristic approaches. In PATAT 2016: Proceedings of the 11th international conference of the practice and theory of automated timetabling (pp. 223\u2013244), Udine, Italy."},{"issue":"2","key":"3479_CR21","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1016\/j.omega.2007.02.002","volume":"37","author":"SF Rad","year":"2009","unstructured":"Rad, S. F., Ruiz, R., & Boroojerdian, N. (2009). New high performing heuristics for minimizing makespan in permutation flowshops. Omega, 37(2), 331\u2013345.","journal-title":"Omega"},{"issue":"1","key":"3479_CR22","doi-asserted-by":"publisher","first-page":"573","DOI":"10.1111\/itor.12445","volume":"27","author":"M Riedler","year":"2017","unstructured":"Riedler, M., Jatschka, T., Maschler, J., & Raidl, G. R. (2017). An iterative time-bucket refinement algorithm for a high-resolution resource-constrained project scheduling problem. International Transactions in Operational Research, 27(1), 573\u2013613.","journal-title":"International Transactions in Operational Research"},{"issue":"1\u20132","key":"3479_CR23","first-page":"235","volume":"82","author":"JAA Van der Veen","year":"1998","unstructured":"Van der Veen, J. A. A., W\u00f6ginger, G. J., & Zhang, S. (1998). Sequencing jobs that require common resources on a single machine: A solvable case of the TSP. Mathematical Programming, 82(1\u20132), 235\u2013254.","journal-title":"Mathematical Programming"}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-019-03479-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10479-019-03479-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-019-03479-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,17]],"date-time":"2021-06-17T16:16:41Z","timestamp":1623946601000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10479-019-03479-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11,21]]},"references-count":23,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,7]]}},"alternative-id":["3479"],"URL":"https:\/\/doi.org\/10.1007\/s10479-019-03479-6","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"value":"0254-5330","type":"print"},{"value":"1572-9338","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,11,21]]},"assertion":[{"value":"21 November 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}