{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,1]],"date-time":"2026-09-01T04:27:20Z","timestamp":1788236840179,"version":"build-2803163510"},"reference-count":13,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2000,1]]},"abstract":"<jats:p>In this paper we study the performance of off-line multiprocessor real-time schedules that allow task migration compared to those that forbid migration. We consider an off-line scheduling problem in which a given collection of tasks, each with a release time, computation time, and deadline, are to be run on a multiprocessor system. A preemptive schedule allows the execution of a task to be temporarily suspended and resumed at a later time. A migrative schedule allows the task to resume on any processor whereas a nonmigrative schedule allows the task to resume only on the processor in which it was initially started. A schedule value is the summation of all the values of all the tasks that were completed by their deadlines. In this paper we assume that a task's value is proportional to its computation time.<\/jats:p>\n                  <jats:p>We present lower and upper bound results. For a system with n processors, we construct a nonmigrative schedule that is guaranteed to achieve at least $1-( 1-\\frac 1{2n}) ^n$ of the optimal migrative schedule value.<\/jats:p>\n                  <jats:p>In addition, we show task sets for which even an optimal nonmigrative schedule achieves at most n\/(2n-1) of the optimal migrative value. Asymptotically (as $n\\rightarrow \\infty $) our upper bound approaches 1\/2 and the lower bound approaches $1 - {1\\over \\sqrt{e}} \\sim 0.3935$.<\/jats:p>","DOI":"10.1137\/s0097539797326241","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"511-527","source":"Crossref","is-referenced-by-count":5,"title":["The Power of Migration in Multiprocessor Scheduling of Real-Time Systems"],"prefix":"10.1137","volume":"30","author":[{"given":"Gilad","family":"Koren","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Emanuel","family":"Dar","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Amihood","family":"Amir","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,27]]},"reference":[{"key":"R1","unstructured":"A. Bar\u2010Noy, R. Canetti, S. Kutten, Y. Mansour, and B. Schieber,\n                      Bandwidth allocation with preemption\n                      , in Proceedings of the 27th ACM Symposium on Theory of Computing, ACM, New York, 1995, pp. 616\u2013625."},{"key":"R2","unstructured":"A. Bar\u2010Noy, Y. Mansour, and B. Schieber,\n                      private communication\n                      , IBM T. J. Watson Research Center, Yorktown Heights, NY, 1992."},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1007\/BF00365406"},{"key":"R3","unstructured":"conference version appeared in Proceedings of the 12th Real\u2010Time Systems Symposium, San Antonio, TX, 1991, pp. 106\u2013115."},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1049\/sej.1991.0015"},{"key":"R5","unstructured":"S.\u2010C. Cheng and J. A. Stankovic,\n                      Scheduling algorithms for hard real\u2010time systems: A brief survey\n                      , in Hard Real\u2010Time Systems, J. Stankovic and K. Ramamritham, eds., IEEE Computer Society Press, Los Alamitos, CA, 1988, pp. 150\u2013173."},{"key":"R6","unstructured":"M. L. Dertouzos,\n                      Control robotics: The procedural control of physical processes\n                      , in Proceedings of the IFIF Congress, Stockholm, Sweden, 1974, North\u2010Holland, Amsterdam, 1974, pp. 807\u2013813."},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1109\/32.58762"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1145\/174147.174148"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90165-1"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792236882"},{"key":"R11","unstructured":"C. D. Locke,\n                      Best\u2010Effort Decision Making for Real\u2010Time Scheduling\n                      , Ph.D. thesis, Computer Science Department, Carnegie\u2010Mellon University, Pittsburgh, PA, 1986."},{"key":"R12","unstructured":"J. Ullman,\n                      Complexity of sequencing problems\n                      , in Computer and Job\u2010Shop Scheduling Theory, E. G. Coffman Jr., ed., Wiley, New York, 1976."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539797326241","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:22:00Z","timestamp":1787336520000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539797326241"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,1]]},"references-count":13,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2000,1]]}},"alternative-id":["10.1137\/S0097539797326241"],"URL":"https:\/\/doi.org\/10.1137\/s0097539797326241","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2000,1]]}}}