{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,22]],"date-time":"2025-10-22T23:17:51Z","timestamp":1761175071908,"version":"build-2065373602"},"reference-count":18,"publisher":"Polish Information Processing Society","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.15439\/2025f6496","type":"proceedings-article","created":{"date-parts":[[2025,10,22]],"date-time":"2025-10-22T07:44:23Z","timestamp":1761119063000},"page":"553-563","source":"Crossref","is-referenced-by-count":0,"title":["The Power of Preemptions in Scheduling on Shareable Resources"],"prefix":"10.15439","volume":"43","author":[{"ORCID":"https:\/\/orcid.org\/0009-0002-8688-7687","authenticated-orcid":true,"given":"Omer","family":"Lapidot","sequence":"first","affiliation":[{"name":"Reichman University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8409-562X","authenticated-orcid":true,"given":"Tami","family":"Tamir","sequence":"additional","affiliation":[{"name":"Reichman University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"6175","published-online":{"date-parts":[[2025,10,15]]},"reference":[{"key":"ref1","doi-asserted-by":"crossref","unstructured":"H. Br\u00e4sel, D. Kluge, and F. Werner, A polynomial algorithm for the\n[n\/m\/0, ti j = 1, tree\/Cmax ] open shop problem, European Journal\nof Operational Research, 72(1):125\u2013134, 1994.","DOI":"10.1016\/0377-2217(94)90335-2"},{"key":"ref2","doi-asserted-by":"crossref","unstructured":"R. Canetti and S. Irani. Bounding the power of preemption in randomized\nscheduling. SIAM Journal on Computing, 27(4):993\u20131015, 1998.","DOI":"10.1137\/S0097539795283292"},{"key":"ref3","doi-asserted-by":"crossref","unstructured":"I. G. Drobouchevitch. Three-machine open shop with a bottleneck\nmachine revisited. Journal of Scheduling, 24(2):197\u2013208, 2021.","DOI":"10.1007\/s10951-020-00652-9"},{"key":"ref4","doi-asserted-by":"crossref","unstructured":"T. Fiala. An algorithm for the open-shop problem. Mathematics of\nOperations Research, 8(1):100\u2013109, 1983.","DOI":"10.1287\/moor.8.1.100"},{"key":"ref5","unstructured":"M.R. Garey and D.S. Johnson. Computers and Intractability: A Guide to\nthe Theory of NP-Completeness, 1979."},{"key":"ref6","doi-asserted-by":"crossref","unstructured":"T. Gonzalez and S. Sahni. Open shop scheduling to minimize finish time.\nJ. ACM, 23(4):665\u2013679, 1976.","DOI":"10.1145\/321978.321985"},{"key":"ref7","doi-asserted-by":"crossref","unstructured":"J.R.Correa, M.Skutella, and J.Verschae. The power of preemption on\nunrelated machines and applications to scheduling orders. Mathematics\nof Operations Research, 37(2):379\u2013398, 2012.","DOI":"10.1287\/moor.1110.0520"},{"key":"ref8","doi-asserted-by":"crossref","unstructured":"N. Karmakar and R. Karp. An efficient approximation scheme for the\none-dimensional bin packing problem. In Proc. 23rd IEEE Symp. on\nFoundations of Computer Science, pages 312\u2013320, 1982.","DOI":"10.1109\/SFCS.1982.61"},{"key":"ref9","doi-asserted-by":"crossref","unstructured":"A. Levin. Approximation schemes for the generalized extensible bin\npacking problem. Algorithmica, 84(2):325\u2013343, 2022.","DOI":"10.1007\/s00453-021-00895-8"},{"key":"ref10","doi-asserted-by":"crossref","unstructured":"C. Liu and R. Bulfin. Scheduling open shops with unit execution times\nto minimize functions of due dates. Operations Research, 36(4):553\u2013559,\n1988.","DOI":"10.1287\/opre.36.4.553"},{"key":"ref11","doi-asserted-by":"crossref","unstructured":"R. McNaughton. Scheduling with deadlines and loss functions. Manage.\nSci., 6:1\u201312, 1959.","DOI":"10.1287\/mnsc.6.1.1"},{"key":"ref12","doi-asserted-by":"crossref","unstructured":"B. Naderi, M. Zandieh, and M. Yazdani. Polynomial time approximation algorithms for proportionate open-shop scheduling. International\nTransactions in Operational Research, 21(6):1031\u20131044, 2014.","DOI":"10.1111\/itor.12087"},{"key":"ref13","doi-asserted-by":"crossref","unstructured":"A. S. Schulz and M. Skutella. Scheduling unrelated machines by randomized rounding. SIAM Journal on Discrete Mathematics, 15(4):450\u2013469, 2002.","DOI":"10.1137\/S0895480199357078"},{"key":"ref14","doi-asserted-by":"crossref","unstructured":"S. Sevastyanov and G. Woeginger. Makespan minimization in open\nshops: A polynomial time approximation scheme. Math. Program.,\n82:191\u2013198, 1998.","DOI":"10.1007\/BF01585871"},{"key":"ref15","doi-asserted-by":"crossref","unstructured":"H. Shachnai and T. Tamir. Multiprocessor scheduling with machine\nallotment and parallelism constraints. Algorithmica, 32(4):651\u2013678, 2002.","DOI":"10.1007\/s00453-001-0098-3"},{"key":"ref16","unstructured":"B. Takand. Towards power of preemption on parallel machines. MPhil\nthesis, University of Greenwich, 2016."},{"key":"ref17","doi-asserted-by":"crossref","unstructured":"D. P. Williamson, L. A. Hall, J. A. Hoogeveen, C. A. J. Hurkens,\nJ. K. Lenstra, S. V. Sevast\u2019janov, and D. B. Shmoys. Short shop schedules.\nOperations Research, 45(2):288\u2013294, 1997.","DOI":"10.1287\/opre.45.2.288"},{"key":"ref18","doi-asserted-by":"crossref","unstructured":"R. Zhang, N. Horesh, E. Kontou, and Y, Zhou, Electric vehicle community charging hubs in multi-unit dwellings: Scheduling and techno-economic assessment, Transportation Research Part D: Transport and\nEnvironment, Vol. 120, 2023.","DOI":"10.1016\/j.trd.2023.103776"}],"event":{"name":"20th Conference on Computer Science and Intelligence Systems (FedCSIS)","theme":"Computer Science and Intelligence Systems","location":"Krak\u00f3w, Poland","acronym":"FedCSIS","number":"20","start":{"date-parts":[[2025,9,14]]},"end":{"date-parts":[[2025,9,17]]}},"container-title":["Annals of Computer Science and Information Systems","Proceedings of the 20th Conference on Computer Science and Intelligence Systems (FedCSIS)"],"original-title":[],"deposited":{"date-parts":[[2025,10,22]],"date-time":"2025-10-22T07:49:26Z","timestamp":1761119366000},"score":1,"resource":{"primary":{"URL":"https:\/\/annals-csis.org\/Volume_43\/drp\/6496.html"}},"subtitle":[],"proceedings-subject":"Computer Science and Information Systems","short-title":[],"issued":{"date-parts":[[2025,10,15]]},"references-count":18,"URL":"https:\/\/doi.org\/10.15439\/2025f6496","relation":{},"ISSN":["2300-5963"],"issn-type":[{"value":"2300-5963","type":"print"}],"subject":[],"published":{"date-parts":[[2025,10,15]]}}}