{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:42:28Z","timestamp":1750308148795,"version":"3.41.0"},"reference-count":17,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2006,3,1]],"date-time":"2006-03-01T00:00:00Z","timestamp":1141171200000},"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":["SIGMETRICS Perform. Eval. Rev."],"published-print":{"date-parts":[[2006,3]]},"abstract":"<jats:p>\n            One of the important performance enhancing capabilities of modern disk drives, is the ability to permute the order of service of incoming I\/O requests in order to minimize total access time. Given a batch (set) of I\/O requests, the problem of finding the optimal order of service is known as the\n            <jats:italic>Batched Disk Scheduling Problem<\/jats:italic>\n            (BDSP). BDSP is a well known instance of the Asymmetric Traveling Salesman Problem (ATSP), in fact it has been used as one of a few principal test cases for the examination of heuristic algorithms for the ATSP, [4], [12]. To specify an instance of BDSP amounts to a choice of a model for the mechanical motion of the disk and a choice of locations and lengths of the requested I\/O in the batch. The distance between requests is the amount of time needed by the disk to move from the end of one request to the beginning of the other, thus the amount of time needed to read the data itself,\n            <jats:italic>Transfer time<\/jats:italic>\n            , is not counted since it is independent of the order of the requests, only the order dependent\n            <jats:italic>Access time<\/jats:italic>\n            is computed.\n          <\/jats:p>","DOI":"10.1145\/1138085.1138094","type":"journal-article","created":{"date-parts":[[2007,1,17]],"date-time":"2007-01-17T18:32:02Z","timestamp":1169058722000},"page":"36-41","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Batched disk scheduling with delays"],"prefix":"10.1145","volume":"33","author":[{"given":"Eitan","family":"Bachmat","sequence":"first","affiliation":[{"name":"Ben-Gurion U., Beer-Sheva, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vladimir","family":"Braverman","sequence":"additional","affiliation":[{"name":"UCLA, Los Angeles"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2006,3]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_2_1_1_1","DOI":"10.5555\/874062.875487"},{"doi-asserted-by":"publisher","key":"e_1_2_1_2_1","DOI":"10.1145\/509907.509951"},{"volume-title":"2005","author":"Bachmat E.","unstructured":"E. Bachmat , Analysis of disk scheduling with linear seek functions, increasing subsequences and space-time geometry , Submitted, 2005 . Available at www.cs.bgu.ac.il\/ebachmat.]] E. Bachmat, Analysis of disk scheduling with linear seek functions, increasing subsequences and space-time geometry, Submitted, 2005. Available at www.cs.bgu.ac.il\/ebachmat.]]","key":"e_1_2_1_3_1"},{"volume-title":"Instance Generators, and Tests, ALENEX 2001 Proceedings","author":"Cirasella J.","unstructured":"J. Cirasella , D. S. Johnson , L. A. McGeoch , and W. Zhang , The Asymmetric Traveling Salesman Problem: Algorithms , Instance Generators, and Tests, ALENEX 2001 Proceedings , Springer Lecture Notes in Computer Science 2153, A. L. Buchsbaum and J. Snoeyink (eds.), 32--59.]] J. Cirasella, D. S. Johnson, L. A. McGeoch, and W. Zhang, The Asymmetric Traveling Salesman Problem: Algorithms, Instance Generators, and Tests, ALENEX 2001 Proceedings, Springer Lecture Notes in Computer Science 2153, A. L. Buchsbaum and J. Snoeyink (eds.), 32--59.]]","key":"e_1_2_1_4_1"},{"key":"e_1_2_1_5_1","series-title":"SIAM Journal of computing, 1(3)","volume-title":"Analysis of scanning policies for reducing disk seek times","author":"Coffman E.G.","year":"1972","unstructured":"E.G. Coffman , L.A. Klimko and B. Ryan , Analysis of scanning policies for reducing disk seek times , SIAM Journal of computing, 1(3) , 1972 .]] E.G. Coffman, L.A. Klimko and B.Ryan, Analysis of scanning policies for reducing disk seek times, SIAM Journal of computing, 1(3), 1972.]]"},{"key":"e_1_2_1_6_1","volume-title":"Universita of Pisa technical report, 20\/94","author":"Gallo G.","year":"1994","unstructured":"G. Gallo , F. Malucelli and M. Marre , Hamiltonian paths algorithms for disk scheduling , Universita of Pisa technical report, 20\/94 , 1994 .]] G. Gallo, F. Malucelli and M. Marre, Hamiltonian paths algorithms for disk scheduling, Universita of Pisa technical report, 20\/94, 1994.]]"},{"doi-asserted-by":"publisher","key":"e_1_2_1_7_1","DOI":"10.1007\/BF02392620"},{"doi-asserted-by":"publisher","key":"e_1_2_1_8_1","DOI":"10.1145\/321784.321789"},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.1080\/01621459.1963.10500830"},{"doi-asserted-by":"publisher","key":"e_1_2_1_10_1","DOI":"10.1145\/359024.359034"},{"key":"e_1_2_1_11_1","volume-title":"HP labs technical report, HPL-CSP-91-7rev1","author":"Jacobson D.","year":"1991","unstructured":"D. Jacobson and J. Wilkes , Disk scheduling algorithms based on rotational position , HP labs technical report, HPL-CSP-91-7rev1 , 1991 .]] D. Jacobson and J. Wilkes, Disk scheduling algorithms based on rotational position, HP labs technical report, HPL-CSP-91-7rev1, 1991.]]"},{"key":"e_1_2_1_12_1","volume-title":"The Traveling Salesman Problem and its Variations","author":"Johnson D. S.","year":"2002","unstructured":"D. S. Johnson , G. Gutin , L. A. McGeoch , A. Yeo , W. Zhang , and A. Zverovich , Experimental Analysis of Heuristics for the ATSP , The Traveling Salesman Problem and its Variations , G. Gutin and A. Punnen, Editors, Kluwer Academic Publishers , Dordrecht , 2002 , 445--487.]] D. S. Johnson, G. Gutin, L. A. McGeoch, A. Yeo, W. Zhang, and A. Zverovich, Experimental Analysis of Heuristics for the ATSP, The Traveling Salesman Problem and its Variations, G. Gutin and A. Punnen, Editors, Kluwer Academic Publishers, Dordrecht, 2002, 445--487.]]"},{"doi-asserted-by":"publisher","key":"e_1_2_1_13_1","DOI":"10.1098\/rspa.1999.0364"},{"key":"e_1_2_1_14_1","first-page":"23","volume-title":"Proceedings of the 1st Workshop on Algorithms and Architecture for Self-Managing Systems","author":"Riska A.","year":"2003","unstructured":"A. Riska , E. Riedel and S. Iren , Managing Overload Via Adaptive Scheduling , in Proceedings of the 1st Workshop on Algorithms and Architecture for Self-Managing Systems , pages 23 - 24 , San-Diego, CA , June 2003 .]] A. Riska, E. Riedel and S. Iren, Managing Overload Via Adaptive Scheduling, in Proceedings of the 1st Workshop on Algorithms and Architecture for Self-Managing Systems, pages 23-24, San-Diego, CA, June 2003.]]"},{"doi-asserted-by":"publisher","key":"e_1_2_1_15_1","DOI":"10.5555\/1025129.1026087"},{"doi-asserted-by":"publisher","key":"e_1_2_1_16_1","DOI":"10.1017\/S0963548303005601"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the Usenix technical conference, 313--324","author":"Seltzer M.","year":"1990","unstructured":"M. Seltzer , Chen P. and J. Ousterhout , Disk scheduling revisited , Proceedings of the Usenix technical conference, 313--324 , winter 1990 .]] M. Seltzer, Chen P. and J. Ousterhout, Disk scheduling revisited, Proceedings of the Usenix technical conference, 313--324, winter 1990.]]"}],"container-title":["ACM SIGMETRICS Performance Evaluation Review"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1138085.1138094","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1138085.1138094","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:18:41Z","timestamp":1750263521000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1138085.1138094"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,3]]},"references-count":17,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2006,3]]}},"alternative-id":["10.1145\/1138085.1138094"],"URL":"https:\/\/doi.org\/10.1145\/1138085.1138094","relation":{},"ISSN":["0163-5999"],"issn-type":[{"type":"print","value":"0163-5999"}],"subject":[],"published":{"date-parts":[[2006,3]]},"assertion":[{"value":"2006-03-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}