{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T03:14:06Z","timestamp":1767928446483,"version":"3.49.0"},"publisher-location":"Cham","reference-count":29,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030782290","type":"print"},{"value":"9783030782306","type":"electronic"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"DOI":"10.1007\/978-3-030-78230-6_14","type":"book-chapter","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T23:06:15Z","timestamp":1623884775000},"page":"214-230","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Two Deadline Reduction Algorithms for\u00a0Scheduling Dependent Tasks on\u00a0Parallel Processors"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2482-5042","authenticated-orcid":false,"given":"Claire","family":"Hanen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2170-6366","authenticated-orcid":false,"given":"Alix Munier","family":"Kordon","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4567-1823","authenticated-orcid":false,"given":"Theo","family":"Pedersen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,6,17]]},"reference":[{"key":"14_CR1","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1023\/A:1018995000688","volume":"92","author":"P Baptiste","year":"1999","unstructured":"Baptiste, P., Le Pape, C., Nuijten, W.: Satisfiability tests and time-bound adjustments for cumulative scheduling problems. Ann. Oper. Res. 92, 305\u2013333 (1999)","journal-title":"Ann. Oper. Res."},{"key":"14_CR2","doi-asserted-by":"crossref","unstructured":"Bellenguez-Morineau, O.: Methods to solve multi-skill project scheduling problem. 4OR 6(1), 85\u201388 (2008)","DOI":"10.1007\/s10288-007-0038-4"},{"key":"14_CR3","unstructured":"Bonifas, N.: A $$\\cal{O}(n^2 \\log (n))$$ propagation for the energy reasoning. In: Congr\u00e8s ROADEF, February 2016"},{"issue":"3","key":"14_CR4","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/s10951-016-0507-8","volume":"20","author":"A Carlier","year":"2017","unstructured":"Carlier, A., Hanen, C., Kordon, A.M.: The equivalence of two classical list scheduling algorithms for dependent typed tasks with release dates, due dates and precedence delays. J. Sched. 20(3), 303\u2013311 (2017). https:\/\/doi.org\/10.1007\/s10951-016-0507-8","journal-title":"J. Sched."},{"issue":"3","key":"14_CR5","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1051\/ro\/1991250303111","volume":"25","author":"J Carlier","year":"1991","unstructured":"Carlier, J., Latapie, B.: Une m\u00e9thode arborescente pour r\u00e9soudre les probl\u00e8mes cumulatifs. RAIRO - Oper. Res. Rech. Op\u00e9rationnelle 25(3), 311\u2013340 (1991)","journal-title":"RAIRO - Oper. Res. Rech. Op\u00e9rationnelle"},{"key":"14_CR6","doi-asserted-by":"crossref","unstructured":"Carlier, J., Pinson, E., Sahli, A., Jouglet, A.: An $$\\cal{O}(n^2)$$ algorithm for time-bound adjustments for the cumulative scheduling problem. Eur. J. Oper. Res. 286(2), 468\u2013476 (2020)","DOI":"10.1016\/j.ejor.2020.03.079"},{"key":"14_CR7","unstructured":"Carlier, J., Pinson, E., Sahli, A., Jouglet, A.: Comparison of three classical lower bounds for the cumulative scheduling problem. (submitted) (2021)"},{"key":"14_CR8","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, Third Edition. The MIT Press, 3rd edn., Cambridge (2009)"},{"key":"14_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1007\/978-3-319-10428-7_22","volume-title":"Principles and Practice of Constraint Programming","author":"A Derrien","year":"2014","unstructured":"Derrien, A., Petit, T.: A new characterization of relevant intervals for energetic reasoning. In: O\u2019Sullivan, B. (ed.) CP 2014. LNCS, vol. 8656, pp. 289\u2013297. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-10428-7_22"},{"issue":"2","key":"14_CR10","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1145\/321694.321699","volume":"19","author":"J Edmonds","year":"1972","unstructured":"Edmonds, J., Karp, R.M.: Theoretical improvements in algorithmic efficiency for network flow problems. J. ACM (JACM) 19(2), 248\u2013264 (1972)","journal-title":"J. ACM (JACM)"},{"key":"14_CR11","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1137\/0206029","volume":"6","author":"MR Garey","year":"1977","unstructured":"Garey, M.R., Johnson, D.S.: Two-processor scheduling with start-time and deadlines. SIAM J. Comput. 6, 416\u2013426 (1977)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"14_CR12","doi-asserted-by":"publisher","first-page":"921","DOI":"10.1145\/48014.61051","volume":"35","author":"AV Goldberg","year":"1988","unstructured":"Goldberg, A.V., Tarjan, R.E.: A new approach to the maximum-flow problem. J. ACM (JACM) 35(4), 921\u2013940 (1988)","journal-title":"J. ACM (JACM)"},{"issue":"8","key":"14_CR13","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1145\/2628036","volume":"57","author":"AV Goldberg","year":"2014","unstructured":"Goldberg, A.V., Tarjan, R.E.: Efficient maximum flow algorithms. Commun. ACM 57(8), 82\u201389 (2014)","journal-title":"Commun. ACM"},{"key":"14_CR14","doi-asserted-by":"crossref","unstructured":"Graham, R., Lawler, E., Lenstra, J., Kan, A.: Optimization and approximation in deterministic sequencing and scheduling: a survey. In: Hammer, P., Johnson, E., Korte, B. (eds.) Discrete Optimization II, Annals of Discrete Mathematics, vol. 5, pp. 287\u2013326. Elsevier (1979)","DOI":"10.1016\/S0167-5060(08)70356-X"},{"key":"14_CR15","doi-asserted-by":"crossref","unstructured":"Hanen, C., Munier Kordon, A.: Two deadline reduction algorithms for scheduling dependent typed-tasks systems. In: ROADEF conference (2020)","DOI":"10.1007\/978-3-030-78230-6_14"},{"key":"14_CR16","unstructured":"Hanen, C., Munier Kordon, A., Pedersen, T.: Two deadline reduction algorithm for scheduling dependent tasks on parallel processors (extended version) (2021). https:\/\/hal.archives-ouvertes.fr\/hal-03200297"},{"issue":"4","key":"14_CR17","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1007\/s10951-009-0101-4","volume":"12","author":"C Hanen","year":"2009","unstructured":"Hanen, C., Zinder, Y.: The worst-case analysis of the Garey-Johnson algorithm. J. Sched. 12(4), 389\u2013400 (2009)","journal-title":"J. Sched."},{"issue":"5","key":"14_CR18","doi-asserted-by":"publisher","first-page":"1187","DOI":"10.1016\/j.cor.2011.05.022","volume":"39","author":"M Haouari","year":"2012","unstructured":"Haouari, M., Kooli, A., N\u00e9ron, E.: Enhanced energetic reasoning-based lower bounds for the resource constrained project scheduling problem. Comput. Oper. Res. 39(5), 1187\u20131194 (2012)","journal-title":"Comput. Oper. Res."},{"issue":"3","key":"14_CR19","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1007\/s10951-013-0354-9","volume":"17","author":"M Haouari","year":"2014","unstructured":"Haouari, M., Kooli, A., N\u00e9ron, E., Carlier, J.: A preemptive bound for the resource constrained project scheduling problem. J. Sched. 17(3), 237\u2013248 (2014)","journal-title":"J. Sched."},{"key":"14_CR20","unstructured":"Jackson, J.R.: Scheduling a production line to minimize maximum tardiness. management science research project (1955)"},{"issue":"2","key":"14_CR21","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1016\/S0004-3702(02)00362-4","volume":"143","author":"P Laborie","year":"2003","unstructured":"Laborie, P.: Algorithms for propagating resource constraints in AI planning and scheduling: Existing approaches and new results. Artif. Intell. 143(2), 151\u2013188 (2003)","journal-title":"Artif. Intell."},{"key":"14_CR22","doi-asserted-by":"crossref","unstructured":"Laborie, P., Nuijten, W.: Constraint Programming Formulations and propagation Algorithms, chap. 4, pp. 63\u201372. Wiley, Hoboken (2008)","DOI":"10.1002\/9780470611227.ch4"},{"key":"14_CR23","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1145\/383721.383733","volume":"23","author":"A Leung","year":"2001","unstructured":"Leung, A., Palem, K.V., Pnueli, A.: Scheduling time-constrained instructions on pipelined processors. ACM Trans. Program. Lang. Syst. 23, 73\u2013103 (2001)","journal-title":"ACM Trans. Program. Lang. Syst."},{"issue":"1","key":"14_CR24","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1007\/s10601-011-9115-6","volume":"17","author":"M Lombardi","year":"2012","unstructured":"Lombardi, M., Milano, M.: Optimal methods for resource allocation and scheduling: a cross-disciplinary survey. Constr. An Int. J. 17(1), 51\u201385 (2012)","journal-title":"Constr. An Int. J."},{"issue":"3","key":"14_CR25","doi-asserted-by":"publisher","first-page":"812","DOI":"10.1145\/322326.322337","volume":"29","author":"C Martel","year":"1982","unstructured":"Martel, C.: Preemptive scheduling with release times, deadlines, and due times. J. Assoc. Comput. Mach. 29(3), 812\u2013829 (1982)","journal-title":"J. Assoc. Comput. Mach."},{"key":"14_CR26","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.dam.2020.11.024","volume":"290","author":"A Munier Kordon","year":"2021","unstructured":"Munier Kordon, A.: A fixed-parameter algorithm for scheduling unit dependent tasks on parallel machines with time windows. Discret. Appl. Math. 290, 1\u20136 (2021)","journal-title":"Discret. Appl. Math."},{"key":"14_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1007\/978-3-319-93031-2_34","volume-title":"Integration of Constraint Programming, Artificial Intelligence, and Operations Research","author":"Y Ouellet","year":"2018","unstructured":"Ouellet, Y., Quimper, C.-G.: A $$O(n \\log ^2 n)$$ checker and $$O(n^2 \\log n)$$ filtering algorithm for the energetic reasoning. In: van Hoeve, W.-J. (ed.) CPAIOR 2018. LNCS, vol. 10848, pp. 477\u2013494. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-93031-2_34"},{"key":"14_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"629","DOI":"10.1007\/978-3-319-98334-9_41","volume-title":"Principles and Practice of Constraint Programming","author":"A Tesch","year":"2018","unstructured":"Tesch, A.: Improving energetic propagations for cumulative scheduling. In: Hooker, J. (ed.) CP 2018. LNCS, vol. 11008, pp. 629\u2013645. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-98334-9_41"},{"key":"14_CR29","doi-asserted-by":"publisher","first-page":"384","DOI":"10.1016\/S0022-0000(75)80008-0","volume":"10","author":"J Ullman","year":"1975","unstructured":"Ullman, J.: NP-complete scheduling problems. J. Comput. Syst. Sci. 10, 384\u2013393 (1975)","journal-title":"J. Comput. Syst. Sci."}],"container-title":["Lecture Notes in Computer Science","Integration of Constraint Programming, Artificial Intelligence, and Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-78230-6_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,31]],"date-time":"2022-12-31T12:07:58Z","timestamp":1672488478000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-78230-6_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030782290","9783030782306"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-78230-6_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"17 June 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CPAIOR","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Vienna","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Austria","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"5 July 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 July 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cpaior2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/cpaior2021.dbai.tuwien.ac.at\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"75","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"30","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"40% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"6","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Due to the COVID-19 pandemic the conference was held online.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}