{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T01:14:24Z","timestamp":1775006064394,"version":"3.50.1"},"publisher-location":"Cham","reference-count":20,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032157904","type":"print"},{"value":"9783032157911","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-3-032-15791-1_14","type":"book-chapter","created":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T00:10:50Z","timestamp":1775002250000},"page":"199-211","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Lower Bounds for\u00a0DAG Scheduling in\u00a0the\u00a0Cloud"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0009-0004-8996-4857","authenticated-orcid":false,"given":"Yury","family":"Semenov","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2836-2524","authenticated-orcid":false,"given":"Oleg","family":"Sukhoroslov","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2026,4,1]]},"reference":[{"issue":"6","key":"14_CR1","doi-asserted-by":"publisher","first-page":"801","DOI":"10.1007\/s10951-010-0191-z","volume":"15","author":"JM van den Akker","year":"2012","unstructured":"van den Akker, J.M., Hoogeveen, J.A., van Kempen, J.W.: Using column generation to solve parallel machine scheduling problems with minmax objective functions. J. Sched. 15(6), 801\u2013810 (2012)","journal-title":"J. Sched."},{"issue":"2","key":"14_CR2","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/s13675-017-0090-6","volume":"6","author":"C Artigues","year":"2018","unstructured":"Artigues, C., Jozefowiez, N., Sarpong, B.: Column generation algorithms for bi-objective combinatorial optimization problems with a min\u2013max objective. EURO J. Comput. Optimiz. 6(2), 117\u2013142 (2018)","journal-title":"EURO J. Comput. Optimiz."},{"key":"14_CR3","doi-asserted-by":"crossref","unstructured":"Val\u00e9rio de Carvalho, J.M.: Exact solution of bin-packing problems using column generation and branch-and-bound. Ann. Oper. Res. 86(0), 629\u2013659 (1999)","DOI":"10.1023\/A:1018952112615"},{"issue":"4","key":"14_CR4","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1016\/j.orl.2005.06.001","volume":"34","author":"A Ceselli","year":"2006","unstructured":"Ceselli, A., Righini, G.: An optimization algorithm for a penalized knapsack problem. Oper. Res. Lett. 34(4), 394\u2013404 (2006)","journal-title":"Oper. Res. Lett."},{"key":"14_CR5","doi-asserted-by":"crossref","unstructured":"Coleman, T., et al.: Wfcommons: a framework for enabling scientific workflow research and development. Future Gener. Comput. Syst. 128, 16\u201327 (2022)","DOI":"10.1016\/j.future.2021.09.043"},{"key":"14_CR6","doi-asserted-by":"crossref","unstructured":"Della Croce, F., Pferschy, U., Scatamacchia, R.: New exact approaches and approximation results for the penalized knapsack problem. Discrete Appl. Math. 253, 122\u2013135 (2019), 14th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2016)","DOI":"10.1016\/j.dam.2017.11.023"},{"issue":"9","key":"14_CR7","doi-asserted-by":"publisher","first-page":"2674","DOI":"10.1016\/j.cor.2005.10.003","volume":"34","author":"M Ehrgott","year":"2007","unstructured":"Ehrgott, M., Gandibleux, X.: Bound sets for biobjective combinatorial optimization problems. Comput. Oper. Res. 34(9), 2674\u20132694 (2007)","journal-title":"Comput. Oper. Res."},{"issue":"6","key":"14_CR8","doi-asserted-by":"publisher","first-page":"922","DOI":"10.1287\/opre.51.6.922.24914","volume":"51","author":"R Freling","year":"2003","unstructured":"Freling, R., Romeijn, H.E., Morales, D.R., Wagelmans, A.P.M.: A branch-and-price algorithm for the multiperiod single-sourcing problem. Oper. Res. 51(6), 922\u2013939 (2003)","journal-title":"Oper. Res."},{"key":"14_CR9","unstructured":"Grandl, R., Kandula, S., Rao, S., Akella, A., Kulkarni, J.: GRAPHENE: packing and Dependency-Aware scheduling for Data-Parallel clusters. In: 12th USENIX Symposium on Operating Systems Design and Implementation (OSDI 16), pp. 81\u201397. USENIX Association, Savannah, GA (2016)"},{"key":"14_CR10","doi-asserted-by":"publisher","DOI":"10.1016\/j.sysarc.2020.101837","volume":"112","author":"P Han","year":"2021","unstructured":"Han, P., Du, C., Chen, J., Ling, F., Du, X.: Cost and makespan scheduling of workflows in clouds using list multiobjective optimization technique. J. Syst. Architect. 112, 101837 (2021)","journal-title":"J. Syst. Architect."},{"issue":"1","key":"14_CR11","doi-asserted-by":"publisher","first-page":"286","DOI":"10.1016\/j.ejor.2022.07.044","volume":"306","author":"M Mesquita-Cunha","year":"2023","unstructured":"Mesquita-Cunha, M., Figueira, J.R., Barbosa-P\u00f3voa, A.P.: New $$\\epsilon $$-constraint methods for multi-objective integer linear programming: a pareto front representation approach. Eur. J. Oper. Res. 306(1), 286\u2013307 (2023)","journal-title":"Eur. J. Oper. Res."},{"key":"14_CR12","unstructured":"Perron, L., Didier, F.: CP-SAT.https:\/\/developers.google.com\/optimization\/cp\/cp_solver\/"},{"key":"14_CR13","unstructured":"Perron, L., Furnon, V.: OR-Tools"},{"key":"14_CR14","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1007\/978-3-642-38527-8_31","volume-title":"Experimental Algorithms","author":"A Pessoa","year":"2013","unstructured":"Pessoa, A., Sadykov, R., Uchoa, E., Vanderbeck, F.: In-out separation and column generation stabilization by dual price smoothing. In: Bonifaci, V., Demetrescu, C., Marchetti-Spaccamela, A. (eds.) Experimental Algorithms, pp. 354\u2013365. Springer, Berlin Heidelberg, Berlin, Heidelberg (2013)"},{"key":"14_CR15","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1007\/978-3-031-78462-0_2","volume-title":"Supercomputing","author":"Y Semenov","year":"2025","unstructured":"Semenov, Y., Sukhoroslov, O.: Bi-objective workflow scheduling in the cloud: What is the real state-of-the-art? In: Voevodin, V., Antonov, A., Nikitenko, D. (eds.) Supercomputing, pp. 20\u201331. Springer Nature Switzerland, Cham (2025)"},{"key":"14_CR16","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1007\/978-3-031-97077-1_22","volume-title":"Mathematical Optimization Theory and Operations Research","author":"Y Semenov","year":"2025","unstructured":"Semenov, Y., Sukhoroslov, O.: MIP models and complexity results for DAG scheduling in the cloud. In: Kochetov, Y., Khachay, M., Eremeev, A., Pardalos, P. (eds.) Mathematical Optimization Theory and Operations Research, pp. 317\u2013331. Springer Nature Switzerland, Cham (2025)"},{"key":"14_CR17","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/978-3-031-41673-6_14","volume-title":"Parallel Computing Technologies","author":"O Sukhoroslov","year":"2023","unstructured":"Sukhoroslov, O.: Scheduling of workflows with task resource requirements in cluster environments. In: Malyshkin, V. (ed.) Parallel Computing Technologies, pp. 177\u2013196. Springer Nature Switzerland, Cham (2023)"},{"key":"14_CR18","doi-asserted-by":"crossref","unstructured":"Tarplee, K.M., Friese, R., Maciejewski, A.A., Siegel, H.J., Chong, E.K.P.: Energy and makespan tradeoffs in heterogeneous computing systems using efficient linear programming techniques. IEEE Trans. Parallel Distrib. Syst. 27(6), 1633\u20131646 (2016)","DOI":"10.1109\/TPDS.2015.2456020"},{"issue":"1","key":"14_CR19","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1007\/BF00934322","volume":"38","author":"B Villarreal","year":"1982","unstructured":"Villarreal, B., Karwan, M.H.: Multicriteria dynamic programming with an application to the integer case. J. Optim. Theory Appl. 38(1), 43\u201369 (1982)","journal-title":"J. Optim. Theory Appl."},{"issue":"4","key":"14_CR20","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1109\/4235.797969","volume":"3","author":"E Zitzler","year":"1999","unstructured":"Zitzler, E., Thiele, L.: Multiobjective evolutionary algorithms: a comparative case study and the strength pareto approach. IEEE Trans. Evol. Comput. 3(4), 257\u2013271 (1999)","journal-title":"IEEE Trans. Evol. Comput."}],"container-title":["Lecture Notes in Computer Science","Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-15791-1_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T00:10:51Z","timestamp":1775002251000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-15791-1_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032157904","9783032157911"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-15791-1_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"1 April 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors have no competing interests to declare that\u00a0are relevant to the content of this article.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"value":"OPTIMA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Optimization and Applications","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Petrovac","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Montenegro","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22 September 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26 September 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"optima2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/conf-optima.ru","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}