{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T12:19:39Z","timestamp":1759666779220,"version":"3.41.0"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2019,6,30]],"date-time":"2019-06-30T00:00:00Z","timestamp":1561852800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Parallel Comput."],"published-print":{"date-parts":[[2019,6,30]]},"abstract":"<jats:p>\n            A fundamental problem in parallel and distributed processing is the partial serialization that is imposed due to the need for mutually exclusive access to common resources. In this article, we investigate the problem of optimally scheduling (in terms of makespan) a set of jobs, where each job consists of the same number\n            <jats:italic>L<\/jats:italic>\n            of unit-duration tasks, and each task either accesses exclusively one resource from a given set of resources or accesses a fully shareable resource. We develop and establish the optimality of a fast polynomial-time algorithm to find a schedule with the shortest makespan for any number of jobs and for any number of resources for the case of\n            <jats:italic>L<\/jats:italic>\n            = 2. In the notation commonly used for job-shop scheduling problems, this result means that the problem\n            <jats:italic>J<\/jats:italic>\n            |\n            <jats:italic>d<\/jats:italic>\n            <jats:sub>\n              <jats:italic>ij<\/jats:italic>\n            <\/jats:sub>\n            =1,\n            <jats:italic>n<\/jats:italic>\n            <jats:sub>\n              <jats:italic>j<\/jats:italic>\n            <\/jats:sub>\n            =2|\n            <jats:italic>C<\/jats:italic>\n            <jats:sub>max<\/jats:sub>\n            is polynomially solvable, adding to the polynomial solutions known for the problems\n            <jats:italic>J<\/jats:italic>\n            2 |\n            <jats:italic>n<\/jats:italic>\n            <jats:sub>\n              <jats:italic>j<\/jats:italic>\n            <\/jats:sub>\n            \u2264 2 |\n            <jats:italic>C<\/jats:italic>\n            <jats:sub>max<\/jats:sub>\n            and\n            <jats:italic>J<\/jats:italic>\n            2 |\n            <jats:italic>d<\/jats:italic>\n            <jats:sub>\n              <jats:italic>ij<\/jats:italic>\n            <\/jats:sub>\n            = 1 |\n            <jats:italic>C<\/jats:italic>\n            <jats:sub>max<\/jats:sub>\n            (whereas other closely related versions such as\n            <jats:italic>J<\/jats:italic>\n            2 |\n            <jats:italic>n<\/jats:italic>\n            <jats:sub>\n              <jats:italic>j<\/jats:italic>\n            <\/jats:sub>\n            \u2264 3 |\n            <jats:italic>C<\/jats:italic>\n            <jats:sub>max<\/jats:sub>\n            ,\n            <jats:italic>J<\/jats:italic>\n            2 |\n            <jats:italic>d<\/jats:italic>\n            <jats:sub>\n              <jats:italic>ij<\/jats:italic>\n            <\/jats:sub>\n            \u2208 { 1,2} |\n            <jats:italic>C<\/jats:italic>\n            <jats:sub>max<\/jats:sub>\n            ,\n            <jats:italic>J<\/jats:italic>\n            3 |\n            <jats:italic>n<\/jats:italic>\n            <jats:sub>\n              <jats:italic>j<\/jats:italic>\n            <\/jats:sub>\n            \u2264 2 |\n            <jats:italic>C<\/jats:italic>\n            <jats:sub>max<\/jats:sub>\n            ,\n            <jats:italic>J<\/jats:italic>\n            3 |\n            <jats:italic>d<\/jats:italic>\n            <jats:sub>\n              <jats:italic>ij<\/jats:italic>\n            <\/jats:sub>\n            =1 |\n            <jats:italic>C<\/jats:italic>\n            <jats:sub>max<\/jats:sub>\n            , and\n            <jats:italic>J<\/jats:italic>\n            |\n            <jats:italic>d<\/jats:italic>\n            <jats:sub>\n              <jats:italic>ij<\/jats:italic>\n            <\/jats:sub>\n            =1,\n            <jats:italic>n<\/jats:italic>\n            <jats:sub>\n              <jats:italic>j<\/jats:italic>\n            <\/jats:sub>\n            \u2264 3|\n            <jats:italic>C<\/jats:italic>\n            <jats:sub>max<\/jats:sub>\n            are all known to be NP-complete). For the general case\n            <jats:italic>L<\/jats:italic>\n            &gt; 2 (i.e., for the job-shop problem\n            <jats:italic>J<\/jats:italic>\n            |\n            <jats:italic>d<\/jats:italic>\n            <jats:sub>\n              <jats:italic>ij<\/jats:italic>\n            <\/jats:sub>\n            =1,\n            <jats:italic>n<\/jats:italic>\n            <jats:sub>\n              <jats:italic>j<\/jats:italic>\n            <\/jats:sub>\n            =\n            <jats:italic>L<\/jats:italic>\n            &gt; 2|\n            <jats:italic>C<\/jats:italic>\n            <jats:sub>max<\/jats:sub>\n            ), we present a competitive heuristic and provide experimental comparisons with other heuristic versions and, when possible, with the ideal integer linear programming formulation.\n          <\/jats:p>","DOI":"10.1145\/3342562","type":"journal-article","created":{"date-parts":[[2019,8,8]],"date-time":"2019-08-08T12:30:31Z","timestamp":1565267431000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Scheduling Mutual Exclusion Accesses in Equal-Length Jobs"],"prefix":"10.1145","volume":"6","author":[{"given":"Dimitri","family":"Kagaris","sequence":"first","affiliation":[{"name":"Southern Illinois University, Carbondale, IL"}]},{"given":"Sourav","family":"Dutta","sequence":"additional","affiliation":[{"name":"Southern Illinois University, Carbondale, IL"}]}],"member":"320","published-online":{"date-parts":[[2019,8,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTAS.2013.6531098"},{"key":"e_1_2_1_2_1","volume-title":"Retrieved","author":"Berkelaar M.","year":"2019","unstructured":"M. Berkelaar , K. Eikland , and P. Notebaert . 2004. Package \u201cLpsolve .\u201d Retrieved July 16, 2019 from https:\/\/cran.r-project.org\/web\/packages\/lpSolve\/index.html. M. Berkelaar, K. Eikland, and P. Notebaert. 2004. Package \u201cLpsolve.\u201d Retrieved July 16, 2019 from https:\/\/cran.r-project.org\/web\/packages\/lpSolve\/index.html."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(83)90012-4"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1080.0572"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2016.2621768"},{"key":"e_1_2_1_6_1","unstructured":"T. H. Cormen C. Stein R. L. Rivest and C. E. Leiserson. 2001. Introduction to Algorithms. McGraw-Hill.   T. H. Cormen C. Stein R. L. Rivest and C. E. Leiserson. 2001. Introduction to Algorithms. McGraw-Hill."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPPW.2009.59"},{"volume-title":"Graph Algorithms","author":"Even S.","key":"e_1_2_1_8_1","unstructured":"S. Even . 1979. Graph Algorithms . Computer Science Press . S. Even. 1979. Graph Algorithms. Computer Science Press."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1956-045-5"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/0204035"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.26.1.36"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.7.1.57"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70356-X"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2015.2468223"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.7.3.354"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)90012-4"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800030307"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/0202019"},{"volume-title":"Proceedings of the 2016 IEEE Real-Time Systems Symposium. 111--122","author":"Huang W.","key":"e_1_2_1_19_1","unstructured":"W. Huang , M. Yang , and J. Chen . 2016. Resource-oriented partitioned scheduling in multiprocessor systems: How to partition and how to share? In Proceedings of the 2016 IEEE Real-Time Systems Symposium. 111--122 . W. Huang, M. Yang, and J. Chen. 2016. Resource-oriented partitioned scheduling in multiprocessor systems: How to partition and how to share? In Proceedings of the 2016 IEEE Real-Time Systems Symposium. 111--122."},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"E. Lawler J. K. Lenstra A. H. G. Rinnooy Kan and D. B. Shmoys. 1993. Sequencing and scheduling: Algorithms and complexity. In Handbooks in Operations Research and Management Science S. C. Graves A. H. G. Rinnooy Kan and P. H. Zipkin (Eds.). Vol. 4. Elsevier 455--522.  E. Lawler J. K. Lenstra A. H. G. Rinnooy Kan and D. B. Shmoys. 1993. Sequencing and scheduling: Algorithms and complexity. In Handbooks in Operations Research and Management Science S. C. Graves A. H. G. Rinnooy Kan and P. H. Zipkin (Eds.). Vol. 4. Elsevier 455--522.","DOI":"10.1016\/S0927-0507(05)80189-6"},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","unstructured":"J. K. Lenstra A. H. G. Rinnooy Kan and P. Brucker. 1977. Complexity of machine scheduling problems. Annals of Discrete Mathematics 1 (1977) 343--362.  J. K. Lenstra A. H. G. Rinnooy Kan and P. Brucker. 1977. Complexity of machine scheduling problems. Annals of Discrete Mathematics 1 (1977) 343--362.","DOI":"10.1016\/S0167-5060(08)70743-X"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70821-5"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2006.47"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2016.2537821"},{"volume-title":"Deterministic Scheduling Theory","author":"Parker R. G.","key":"e_1_2_1_25_1","unstructured":"R. G. Parker . 1996. Deterministic Scheduling Theory . Chapman 8 Hall. R. G. Parker. 1996. Deterministic Scheduling Theory. Chapman 8 Hall."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2012.311"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1002\/jos.95"},{"volume-title":"Handbook of Scheduling\u2014Algorithms, Models, and Performance Analysis, J. Y.-T","author":"Timkovsky V. G.","key":"e_1_2_1_28_1","unstructured":"V. G. Timkovsky . 2004. Cycle shop scheduling . In Handbook of Scheduling\u2014Algorithms, Models, and Performance Analysis, J. Y.-T . Leung (Ed.). Chapman 8 Hall, 7.1--7.22. V. G. Timkovsky. 2004. Cycle shop scheduling. In Handbook of Scheduling\u2014Algorithms, Models, and Performance Analysis, J. Y.-T. Leung (Ed.). Chapman 8 Hall, 7.1--7.22."},{"volume-title":"Complexity of sequencing problems","author":"Ullman J. D.","key":"e_1_2_1_29_1","unstructured":"J. D. Ullman . 1976. Complexity of sequencing problems . In Computer and Job Shop Scheduling Theory, E. G. Coffman (Ed.). Wiley , 139--164. J. D. Ullman. 1976. Complexity of sequencing problems. In Computer and Job Shop Scheduling Theory, E. G. Coffman (Ed.). Wiley, 139--164."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.45.2.288"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2379776.2379780"}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3342562","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3342562","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:23:01Z","timestamp":1750202581000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3342562"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,30]]},"references-count":31,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,6,30]]}},"alternative-id":["10.1145\/3342562"],"URL":"https:\/\/doi.org\/10.1145\/3342562","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"type":"print","value":"2329-4949"},{"type":"electronic","value":"2329-4957"}],"subject":[],"published":{"date-parts":[[2019,6,30]]},"assertion":[{"value":"2017-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-08-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}