{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,17]],"date-time":"2026-06-17T16:39:35Z","timestamp":1781714375076,"version":"3.54.5"},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662232064","type":"print"},{"value":"9783662252093","type":"electronic"}],"license":[{"start":{"date-parts":[[1991,1,1]],"date-time":"1991-01-01T00:00:00Z","timestamp":662688000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1991]]},"DOI":"10.1007\/978-3-662-25209-3_12","type":"book-chapter","created":{"date-parts":[[2013,8,21]],"date-time":"2013-08-21T05:33:51Z","timestamp":1377063231000},"page":"166-178","source":"Crossref","is-referenced-by-count":39,"title":["Periodic Multiprocessor Scheduling"],"prefix":"10.1007","author":[{"given":"Jan","family":"Korst","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Emile","family":"Aarts","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jan Karel","family":"Lenstra","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jaap","family":"Wessels","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"12_CR1","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1287\/opre.29.3.501","volume":"29","author":"JJ Bartholdi","year":"1981","unstructured":"Bartholdi, J.J. [ 1981 ], A guaranteed-accuracy round-off algorithm for cyclic scheduling and set covering, Operations Research 29, 501 - 510.","journal-title":"Operations Research"},{"key":"12_CR2","doi-asserted-by":"publisher","first-page":"1074","DOI":"10.1287\/opre.28.5.1074","volume":"28","author":"JJ Bartholdi","year":"1980","unstructured":"Bartholdi, J.J., J.B. Orlin, and H.D. Ratliff [ 1980 ], Cyclic scheduling via integer programs with circular ones, Operations Research 28, 1074 - 1085.","journal-title":"Operations Research"},{"key":"12_CR3","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/0020-0190(83)90002-9","volume":"16","author":"AA Bertossi","year":"1983","unstructured":"Bertossi, A.A. and M.A. Bonuccelli [ 1983 ], Preemptive scheduling of periodic jobs in uniform multiprocessor systems, Information Processing Letters 16, 3 - 6.","journal-title":"Information Processing Letters"},{"key":"12_CR4","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/0166-218X(85)90024-1","volume":"12","author":"AA Bertossi","year":"1985","unstructured":"Bertossi, A.A. and M.A. Bonuccelli [ 1985 ], A polynomial feasibility test for preemptive periodic scheduling of unrelated processors, Discrete Applied Mathematics 12, 195 - 201.","journal-title":"Discrete Applied Mathematics"},{"key":"12_CR5","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/0166-218X(86)90040-5","volume":"15","author":"RE Burkard","year":"1986","unstructured":"Burkard, R.E. [ 1986 ], Optimal schedules for periodically recurring events, Discrete Applied Mathematics 15, 167 - 180.","journal-title":"Discrete Applied Mathematics"},{"key":"12_CR6","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/0020-0190(89)90209-3","volume":"30","author":"H Chetto","year":"1989","unstructured":"Chetto, H. and M. Chetto [ 1989 ], Scheduling periodic and sporadic tasks in a real-time system, Information Processing Letters 30, 177 - 184.","journal-title":"Information Processing Letters"},{"key":"12_CR7","first-page":"49","volume-title":"Algorithms Design and Computer System Design","author":"EG Coffmann Jr.","year":"1984","unstructured":"Coffmann, E.G., Jr., M.R. Garey, and D.S. Johnson [ 1984 ], Approximation algorithms for bin packing - an updated survey, in: G. Ausiello, M. Lucertini, and P. Serafini (Eds.), Algorithms Design and Computer System Design, CISM Courses and Lectures 284, Springer, Vienna, 49 - 106."},{"key":"12_CR8","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1287\/opre.26.1.127","volume":"26","author":"SK Dhall","year":"1978","unstructured":"Dhall, S.K. and C.L. Liu [ 1978 ], On a real-time scheduling problem, Operations Research 26, 127 - 140.","journal-title":"Operations Research"},{"key":"12_CR9","doi-asserted-by":"publisher","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J Edmonds","year":"1965","unstructured":"Edmonds, J. [ 1965 ], Paths, trees and flowers, Canadian Journal of Mathematics 17, 449 - 467.","journal-title":"Canadian Journal of Mathematics"},{"key":"12_CR10","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H","author":"MR Garey","year":"1979","unstructured":"Garey, M.R. and D.S. Johnson [ 1979 ], Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman and Co., San Francisco."},{"key":"12_CR11","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1137\/0601025","volume":"1","author":"MR Garey","year":"1980","unstructured":"Garey, M.R., D.S. Johnson, G.L. Miller, and C.H. Papadimitriou [ 1980 ], The complexity of coloring circular arcs and chords, SIAM Journal on Algebraic and Discrete Methods 1, 216 - 227.","journal-title":"SIAM Journal on Algebraic and Discrete Methods"},{"key":"12_CR12","first-page":"530","volume":"12","author":"MJ Gonzalez","year":"1975","unstructured":"Gonzalez, M.J. and J.W. Soh [ 1975 ], Periodic job scheduling in a distributed processor system, IEEE Transactions on Aerospace and Electronic Systems 12, 530 - 536.","journal-title":"IEEE Transactions on Aerospace and Electronic Systems"},{"key":"12_CR13","doi-asserted-by":"publisher","first-page":"807","DOI":"10.1109\/TC.1979.1675260","volume":"28","author":"UI Gupta","year":"1979","unstructured":"Gupta, U.I., D.T. Lee, and J.Y.-T. Leung [ 1979 ], An optimal solution for the channel-assignment problem, IEEE Transaction on Computers 28, 807 - 810.","journal-title":"IEEE Transaction on Computers"},{"key":"12_CR14","doi-asserted-by":"crossref","unstructured":"Hashimoto, A. and J. Stevens [ 1971 ], Wire routing by optimizing channel assignment with large apertures, Proceedings of the 8th Design Automation Conference, 155 - 169.","DOI":"10.1145\/800158.805069"},{"key":"12_CR15","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1137\/0202019","volume":"2","author":"JE Hoperoft","year":"1973","unstructured":"Hoperoft, J.E. and R.M. Karp [ 1973 ], An n 5\/2 algorithm for maximum matchings in bipartite graphs, SIAM Journal on Computing 2, 225 - 231.","journal-title":"SIAM Journal on Computing"},{"key":"12_CR16","volume-title":"Philips Research Manuscript","author":"JHM Korst","year":"1991","unstructured":"Korst, J.H.M., E.H.L. Aarts, J.K. Lenstra, and J. Wessels [ 1991 ], Periodic Assignment and Graph Colouring, Philips Research Manuscript."},{"key":"12_CR17","first-page":"285","volume-title":"Computer Architecture and Networks","author":"J Labetoulle","year":"1974","unstructured":"Labetoulle, J. [ 1974 ], Some theorems on real time scheduling, in: E. Gelenbe and R. Mahl (Eds.), Computer Architecture and Networks, North-Holland, Amsterdam, 285 - 293."},{"key":"12_CR18","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1016\/0020-0190(81)90066-1","volume":"12","author":"EL Lawler","year":"1981","unstructured":"Lawler, E.L. and C.U. Martel [ 1981 ], Scheduling periodically occurring tasks on multiple processors, Information Processing Letters 12, 9 - 12.","journal-title":"Information Processing Letters"},{"key":"12_CR19","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/0020-0190(80)90123-4","volume":"11","author":"JY-T Leung","year":"1980","unstructured":"Leung, J.Y.-T. and M.L. Merrill [ 1980 ], A note on preemptive scheduling of periodic, real-time tasks, Information Processing Letters 11, 115 - 118.","journal-title":"Information Processing Letters"},{"key":"12_CR20","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0166-5316(82)90024-4","volume":"2","author":"JY-T Leung","year":"1982","unstructured":"Leung, J.Y.-T. and J. Whitehead [ 1982 ], On the complexity of fixed-priority scheduling of periodic, real-time tasks, Performance Evaluation 2, 237 - 250.","journal-title":"Performance Evaluation"},{"key":"12_CR21","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1145\/321738.321743","volume":"20","author":"CL Liu","year":"1973","unstructured":"Liu, C.L. and J.W. Layland [ 1973 ], Scheduling algorithms for multiprogramming in a hard real-time environment, Journal of the Association for Computing Machinery 20, 46 - 61.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"12_CR22","doi-asserted-by":"publisher","first-page":"760","DOI":"10.1287\/opre.30.4.760","volume":"30","author":"JB Orlin","year":"1982","unstructured":"Orlin, J.B. [ 1982 ], Minimizing the number of vehicles to meet a fixed periodic schedule: an application of periodic posets, Operations Research 30, 760 - 776.","journal-title":"Operations Research"},{"key":"12_CR23","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1137\/0602012","volume":"2","author":"JB Orlin","year":"1981","unstructured":"Orlin, J.B., M.A. Bonuccelli, and D.P. Bovet [ 1981 ], An 0(n 2 ) algorithm for coloring proper circular arc graphs, SIAM Journal on Algebraic and Discrete Methods 2, 88 - 93.","journal-title":"SIAM Journal on Algebraic and Discrete Methods"},{"key":"12_CR24","doi-asserted-by":"publisher","first-page":"690","DOI":"10.1287\/opre.33.3.690","volume":"33","author":"KS Park","year":"1985","unstructured":"Park, K.S. and D.K. Yun [ 1985 ], Optimal scheduling of periodic activities, Operations Research 33, 690 - 695.","journal-title":"Operations Research"},{"key":"12_CR25","doi-asserted-by":"publisher","first-page":"550","DOI":"10.1137\/0402049","volume":"2","author":"P Serafini","year":"1989","unstructured":"Serafini, P. and W. Ukovich [ 1989 ], A mathematical model for periodic scheduling problems, SIAM Journal on Discrete Mathematics 2, 550 - 581.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"12_CR26","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1016\/0166-218X(89)90011-5","volume":"25","author":"W-K Shih","year":"1989","unstructured":"Shih, W.-K. and W.-L. Hsu [ 1989 ], An 0(n 1 . 5 ) algorithm to color proper circular arcs, Discrete Applied Mathematics 25, 321 - 323.","journal-title":"Discrete Applied Mathematics"},{"key":"12_CR27","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1137\/0129040","volume":"29","author":"A Tucker","year":"1975","unstructured":"Tucker, A [ 1975 ], Coloring a family of circular arcs, SIAM Journal on Applied Mathematics 29, 493 - 552.","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"12_CR28","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/0166-218X(89)90008-5","volume":"25","author":"J Vince","year":"1989","unstructured":"Vince, J. [ 1989 ], Scheduling periodic events, Discrete Applied Mathematics 25, 299 - 310.","journal-title":"Discrete Applied Mathematics"}],"container-title":["Lecture Notes in Computer Science","Parle \u201991 Parallel Architectures and Languages Europe"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-25209-3_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,1,20]],"date-time":"2019-01-20T12:50:55Z","timestamp":1547988655000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-25209-3_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991]]},"ISBN":["9783662232064","9783662252093"],"references-count":28,"aliases":["10.1007\/bfb0035103"],"URL":"https:\/\/doi.org\/10.1007\/978-3-662-25209-3_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991]]}}}