{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,3]],"date-time":"2026-06-03T20:59:56Z","timestamp":1780520396997,"version":"3.54.1"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2021,5,29]],"date-time":"2021-05-29T00:00:00Z","timestamp":1622246400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,5,29]],"date-time":"2021-05-29T00:00:00Z","timestamp":1622246400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100005156","name":"Alexander von Humboldt-Stiftung","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100005156","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Sched"],"published-print":{"date-parts":[[2021,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider a variant of the NP-hard problem of assigning jobs to machines to minimize the completion time of the last job. Usually, precedence constraints are given by a partial order on the set of jobs, and each job requires all its predecessors to be completed before it can start. In this paper, we consider a different type of precedence relation that has not been discussed as extensively and is called OR-precedence. In order for a job to start, we require that <jats:italic>at least one<\/jats:italic> of its predecessors is completed\u2014in contrast to <jats:italic>all<\/jats:italic> its predecessors. Additionally, we assume that each job has a release date before which it must not start. We prove that a simple List Scheduling algorithm due to Graham (Bell Syst Tech J 45(9):1563\u20131581, 1966) has an approximation guarantee of 2 and show that obtaining an approximation factor of <jats:inline-formula><jats:alternatives><jats:tex-math>$$4\/3 - \\varepsilon $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mn>4<\/mml:mn>\n                    <mml:mo>\/<\/mml:mo>\n                    <mml:mn>3<\/mml:mn>\n                    <mml:mo>-<\/mml:mo>\n                    <mml:mi>\u03b5<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is NP-hard. Further, we present a polynomial-time algorithm that solves the problem to optimality if preemptions are allowed. The latter result is in contrast to classical precedence constraints where the preemptive variant is already NP-hard. Our algorithm generalizes previous results for unit processing time jobs subject to OR-precedence constraints, but without release dates. The running time of our algorithm is <jats:inline-formula><jats:alternatives><jats:tex-math>$$O(n^2)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:msup>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mn>2<\/mml:mn>\n                    <\/mml:msup>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for arbitrary processing times and it can be reduced to <jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic>) for unit processing times, where <jats:italic>n<\/jats:italic> is the number of jobs. The performance guarantees presented here match the best-known ones for special cases where classical precedence constraints and OR-precedence constraints coincide.\n<\/jats:p>","DOI":"10.1007\/s10951-021-00687-6","type":"journal-article","created":{"date-parts":[[2021,5,29]],"date-time":"2021-05-29T19:02:55Z","timestamp":1622314975000},"page":"319-328","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Makespan minimization with OR-precedence constraints"],"prefix":"10.1007","volume":"24","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8062-3632","authenticated-orcid":false,"given":"Felix","family":"Happach","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2021,5,29]]},"reference":[{"key":"687_CR1","doi-asserted-by":"crossref","unstructured":"Bansal, N., & Khot, S. (2009). Optimal long code test with one free bit. In Proceedings of the 50th annual IEEE symposium on foundations of computer science. (pp. 453\u2013462). IEEE.","DOI":"10.1109\/FOCS.2009.23"},{"issue":"3","key":"687_CR2","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1287\/moor.2.3.275","volume":"2","author":"P Brucker","year":"1977","unstructured":"Brucker, P., Garey, M. R., & Johnson, D. S. (1977). Scheduling equal-length tasks under treelike precedence constraints to minimize maximum lateness. Mathematics of Operations Research, 2(3), 275\u2013284.","journal-title":"Mathematics of Operations Research"},{"issue":"4","key":"687_CR3","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/S0167-6377(97)00040-0","volume":"21","author":"B Chen","year":"1997","unstructured":"Chen, B., & Vestjens, A. P. A. (1997). Scheduling on identical machines: How good is LPT in an on-line setting? Operations Research Letters, 21(4), 165\u2013169.","journal-title":"Operations Research Letters"},{"issue":"2","key":"687_CR4","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/0890-5401(91)90009-Q","volume":"92","author":"J Du","year":"1991","unstructured":"Du, J., Leung, J. Y. T., & Young, G. H. (1991). Scheduling chain-structured tasks to minimize makespan and mean flow time. Information and Computation, 92(2), 219\u2013236.","journal-title":"Information and Computation"},{"key":"687_CR5","doi-asserted-by":"crossref","unstructured":"Erlebach, T., K\u00e4\u00e4b, V., & M\u00f6hring, R. H. (2003). Scheduling AND\/OR-networks on identical parallel machines. In International workshop on approximation and online algorithms, no. 2909 in LNCS. (pp. 123\u2013136). Springer.","DOI":"10.1007\/978-3-540-24592-6_10"},{"issue":"3","key":"687_CR6","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1145\/322077.322090","volume":"25","author":"MR Garey","year":"1978","unstructured":"Garey, M. R., & Johnson, D. S. (1978). Strong NP-completeness results: Motivation, examples, and implications. Journal of the ACM (JACM), 25(3), 499\u2013508.","journal-title":"Journal of the ACM (JACM)"},{"issue":"4","key":"687_CR7","doi-asserted-by":"publisher","first-page":"797","DOI":"10.1137\/S0097539791218664","volume":"24","author":"DW Gillies","year":"1995","unstructured":"Gillies, D. W., & Liu, J. W. S. (1995). Scheduling tasks with AND\/OR precedence constraints. SIAM Journal on Computing, 24(4), 797\u2013810.","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"687_CR8","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1145\/322186.322194","volume":"27","author":"TF Gonzalez","year":"1980","unstructured":"Gonzalez, T. F., & Johnson, D. B. (1980). A new algorithm for preemptive scheduling of trees. Journal of the ACM (JACM), 27(2), 287\u2013312.","journal-title":"Journal of the ACM (JACM)"},{"issue":"9","key":"687_CR9","doi-asserted-by":"publisher","first-page":"1563","DOI":"10.1002\/j.1538-7305.1966.tb01709.x","volume":"45","author":"RL Graham","year":"1966","unstructured":"Graham, R. L. (1966). Bounds for certain multiprocessing anomalies. Bell System Technical Journal, 45(9), 1563\u20131581.","journal-title":"Bell System Technical Journal"},{"issue":"2","key":"687_CR10","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1137\/0117039","volume":"17","author":"RL Graham","year":"1969","unstructured":"Graham, R. L. (1969). Bounds on multiprocessing timing anomalies. SIAM Journal on Applied Mathematics, 17(2), 416\u2013429.","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"687_CR11","doi-asserted-by":"crossref","unstructured":"Graham, R. L., Lawler, E. L., Lenstra, J. K., & Rinnooy Kan, A. H. G. (1979). Optimization and approximation in deterministic sequencing and scheduling: A survey. In Annals of discrete mathematics. (Vol. 5, pp. 287\u2013326). Elsevier.","DOI":"10.1016\/S0167-5060(08)70356-X"},{"key":"687_CR12","doi-asserted-by":"crossref","unstructured":"Hall, L. A., & Shmoys, D. B. (1989). Approximation schemes for constrained scheduling problems. In Proceedings of the 30th annual symposium on foundations of computer science. (pp. 134\u2013139). IEEE.","DOI":"10.1109\/SFCS.1989.63468"},{"issue":"3","key":"687_CR13","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1137\/0217033","volume":"17","author":"DS Hochbaum","year":"1988","unstructured":"Hochbaum, D. S., & Shmoys, D. B. (1988). A polynomial approximation scheme for scheduling on uniform processors: Using the dual approximation approach. SIAM Journal on Computing, 17(3), 539\u2013551.","journal-title":"SIAM Journal on Computing"},{"issue":"6","key":"687_CR14","doi-asserted-by":"publisher","first-page":"841","DOI":"10.1287\/opre.9.6.841","volume":"9","author":"TC Hu","year":"1961","unstructured":"Hu, T. C. (1961). Parallel sequencing and assembly line problems. Operations Research, 9(6), 841\u2013848.","journal-title":"Operations Research"},{"issue":"2","key":"687_CR15","doi-asserted-by":"publisher","first-page":"457","DOI":"10.1137\/090749451","volume":"24","author":"K Jansen","year":"2010","unstructured":"Jansen, K. (2010). An EPTAS for scheduling jobs on uniform processors: using an MILP relaxation with a constant number of integral variables. SIAM Journal on Discrete Mathematics, 24(2), 457\u2013485.","journal-title":"SIAM Journal on Discrete Mathematics"},{"issue":"6","key":"687_CR16","doi-asserted-by":"publisher","first-page":"587","DOI":"10.1016\/j.orl.2004.11.009","volume":"33","author":"B Johannes","year":"2005","unstructured":"Johannes, B. (2005). On the complexity of scheduling unit-time jobs with OR-precedence constraints. Operations Research Letters, 33(6), 587\u2013596.","journal-title":"Operations Research Letters"},{"key":"687_CR17","doi-asserted-by":"crossref","unstructured":"Karp, R. M. (1972). Reducibility among combinatorial problems. In Complexity of computer computations (pp. 85\u2013103). Springer.","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"687_CR18","doi-asserted-by":"crossref","unstructured":"Khot, S. (2002). On the power of unique 2-prover 1-round games. In Proceedings of the 34th annual ACM symposium on theory of computing. (pp. 767\u2013775). ACM.","DOI":"10.1145\/509907.510017"},{"key":"687_CR19","doi-asserted-by":"crossref","unstructured":"Lawler, E. L. (1982). Preemptive scheduling of precedence-constrained jobs on parallel machines. In Deterministic and stochastic scheduling. (pp. 101\u2013123). Springer.","DOI":"10.1007\/978-94-009-7801-0_6"},{"issue":"1","key":"687_CR20","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1287\/opre.26.1.22","volume":"26","author":"JK Lenstra","year":"1978","unstructured":"Lenstra, J. K., & Rinnooy Kan, A. H. G. (1978). Complexity of scheduling under precedence constraints. Operations Research, 26(1), 22\u201335.","journal-title":"Operations Research"},{"key":"687_CR21","doi-asserted-by":"crossref","unstructured":"Lenstra, J. K., Rinnooy Kan, A. H. G., & Brucker, P. (1977). Complexity of machine scheduling problems. In Annals of discrete mathematics. (Vol. 1, pp. 343\u2013362). Elsevier.","DOI":"10.1016\/S0167-5060(08)70743-X"},{"issue":"1","key":"687_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1287\/mnsc.6.1.1","volume":"6","author":"R McNaughton","year":"1959","unstructured":"McNaughton, R. (1959). Scheduling with deadlines and loss functions. Management Science, 6(1), 1\u201312.","journal-title":"Management Science"},{"issue":"1\u20132","key":"687_CR23","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1007\/s10107-014-0830-9","volume":"154","author":"M Mnich","year":"2015","unstructured":"Mnich, M., & Wiese, A. (2015). Scheduling and fixed-parameter tractability. Mathematical Programming, 154(1\u20132), 533\u2013562.","journal-title":"Mathematical Programming"},{"issue":"2","key":"687_CR24","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1137\/S009753970037727X","volume":"33","author":"RH M\u00f6hring","year":"2004","unstructured":"M\u00f6hring, R. H., Skutella, M., & Stork, F. (2004). Scheduling with AND\/OR precedence constraints. SIAM Journal on Computing, 33(2), 393\u2013415.","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"687_CR25","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1287\/opre.30.1.116","volume":"30","author":"CL Monma","year":"1982","unstructured":"Monma, C. L. (1982). Linear-time algorithms for scheduling on parallel processors. Operations Research, 30(1), 116\u2013124.","journal-title":"Operations Research"},{"key":"687_CR26","doi-asserted-by":"crossref","unstructured":"Muntz, R. R., & Coffman Jr, E. G. (1970). Preemptive scheduling of real-time tasks on multiprocessor systems. Journal of the ACM (JACM), 17(2), 324\u2013338.","DOI":"10.1145\/321574.321586"},{"key":"687_CR27","doi-asserted-by":"crossref","unstructured":"Svensson, O. (2010). Conditional hardness of precedence constrained scheduling on identical machines. In Proceedings of the 42nd annual ACM symposium on theory of computing. (pp. 745\u2013754). ACM.","DOI":"10.1145\/1806689.1806791"},{"issue":"3","key":"687_CR28","doi-asserted-by":"publisher","first-page":"384","DOI":"10.1016\/S0022-0000(75)80008-0","volume":"10","author":"JD Ullman","year":"1975","unstructured":"Ullman, J. D. (1975). NP-complete scheduling problems. Journal of Computer and System Sciences, 10(3), 384\u2013393.","journal-title":"Journal of Computer and System Sciences"}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-021-00687-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10951-021-00687-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-021-00687-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,26]],"date-time":"2021-06-26T09:09:00Z","timestamp":1624698540000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10951-021-00687-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,5,29]]},"references-count":28,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,6]]}},"alternative-id":["687"],"URL":"https:\/\/doi.org\/10.1007\/s10951-021-00687-6","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"value":"1094-6136","type":"print"},{"value":"1099-1425","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,5,29]]},"assertion":[{"value":"27 April 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 May 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}