{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,20]],"date-time":"2025-02-20T05:24:59Z","timestamp":1740029099715,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642121999"},{"type":"electronic","value":"9783642122002"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-12200-2_11","type":"book-chapter","created":{"date-parts":[[2010,4,21]],"date-time":"2010-04-21T13:53:05Z","timestamp":1271857985000},"page":"108-119","source":"Crossref","is-referenced-by-count":7,"title":["Local Search Performance Guarantees for Restricted Related Parallel Machine Scheduling"],"prefix":"10.1007","author":[{"given":"Diego","family":"Recalde","sequence":"first","affiliation":[]},{"given":"Cyriel","family":"Rutten","sequence":"additional","affiliation":[]},{"given":"Petra","family":"Schuurman","sequence":"additional","affiliation":[]},{"given":"Tjark","family":"Vredeveld","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"11_CR1","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1016\/j.tcs.2006.05.010","volume":"361","author":"B. Awerbuch","year":"2006","unstructured":"Awerbuch, B., Azar, Y., Richter, Y., Tsur, D.: Tradeoffs in worst-case equilibria. Theoretical Computer Science\u00a0361, 200\u2013209 (2006)","journal-title":"Theoretical Computer Science"},{"key":"11_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/978-3-540-77918-6_4","volume-title":"Approximation and Online Algorithms","author":"T. Brueggemann","year":"2008","unstructured":"Brueggemann, T., Hurink, J.L., Vredeveld, T., Woeginger, G.J.: Very large-scale neighborhoods with performance guarantees for minimizing makespan on parallel machines. In: Kaklamanis, C., Skutella, M. (eds.) WAOA 2007. LNCS, vol.\u00a04927, pp. 41\u201355. Springer, Heidelberg (2008)"},{"issue":"6","key":"11_CR3","doi-asserted-by":"publisher","first-page":"1243","DOI":"10.1080\/00207540310001631584","volume":"42","author":"G. Centeno","year":"2004","unstructured":"Centeno, G., Armacost, R.L.: Minimizing makespan on parallel machines with release time and machine eligibility restrictions. International Journal of Production Research\u00a042(6), 1243\u20131256 (2004)","journal-title":"International Journal of Production Research"},{"key":"11_CR4","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1137\/0209007","volume":"9","author":"Y. Cho","year":"1980","unstructured":"Cho, Y., Sahni, S.: Bounds for list schedules on uniform processors. SIAM Journal on Computing\u00a09, 91\u2013103 (1980)","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"11_CR5","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1145\/1186810.1186814","volume":"3","author":"A. Czumaj","year":"2007","unstructured":"Czumaj, A., Vocking, B.: Tight bounds for worst-case equilibria. ACM Transactions on Algorithms\u00a03(1), 4 (2007)","journal-title":"ACM Transactions on Algorithms"},{"key":"11_CR6","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1007\/BF01930985","volume":"19","author":"G. Finn","year":"1979","unstructured":"Finn, G., Horowitz, E.: A linear time approximation algorithm for multiprocessor scheduling. BIT\u00a019, 312\u2013320 (1979)","journal-title":"BIT"},{"issue":"1","key":"11_CR7","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1142\/S0129626406002514","volume":"16","author":"M. Gairing","year":"2006","unstructured":"Gairing, M., L\u00fccking, T., Mavronicolas, M., Monien, B.: The price of anarchy for restricted parallel links. Parallel Processing Letters\u00a016(1), 117\u2013131 (2006)","journal-title":"Parallel Processing Letters"},{"key":"11_CR8","unstructured":"Gairing, M., L\u00fccking, T., Mavronicolas, M., Monien, B.: Computing nash equilibria for scheduling on restricted parallel links. Theory of Computing Systems (2009), http:\/\/www.springerlink.com\/content\/q7n8267q76716v55\/fulltext.pdf (February 12, 2009)"},{"key":"11_CR9","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979)"},{"issue":"3","key":"11_CR10","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1002\/nav.20202","volume":"54","author":"C.A. Glass","year":"2007","unstructured":"Glass, C.A., Kellerer, H.: Parallel machine scheduling with job assignment restrictions. Naval Research Logistics\u00a054(3), 250\u2013257 (2007)","journal-title":"Naval Research Logistics"},{"key":"11_CR11","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/S0167-5060(08)70356-X","volume":"5","author":"R.L. Graham","year":"1979","unstructured":"Graham, R.L., Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G.: Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics\u00a05, 287\u2013326 (1979)","journal-title":"Annals of Discrete Mathematics"},{"key":"11_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1007\/978-3-540-79309-0_4","volume-title":"Algorithmic Game Theory","author":"M. Hoefer","year":"2008","unstructured":"Hoefer, M., Souza, A.: The influence of link restriction on (random) selfish routing. In: Monien, B., Schroeder, U.-P. (eds.) SAGT 2008. LNCS, vol.\u00a04997, pp. 22\u201332. Springer, Heidelberg (2008)"},{"key":"11_CR13","doi-asserted-by":"publisher","first-page":"1589","DOI":"10.1016\/j.tcs.2008.12.032","volume":"410","author":"N. Immorlica","year":"2009","unstructured":"Immorlica, N., Li, L., Mirrokni, V., Schulz, A.: Coordination mechanism for selfish scheduling. Theoretical Computer Science\u00a0410, 1589\u20131598 (2009)","journal-title":"Theoretical Computer Science"},{"key":"11_CR14","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/j.ijpe.2008.09.003","volume":"116","author":"J.Y.T. Leung","year":"2008","unstructured":"Leung, J.Y.T., Li, C.L.: Scheduling with processing set restrictions: A survey. International Journal of Production Economics\u00a0116, 251\u2013262 (2008)","journal-title":"International Journal of Production Economics"},{"key":"11_CR15","doi-asserted-by":"publisher","first-page":"1325","DOI":"10.1016\/j.ejor.2005.03.023","volume":"174","author":"C.L. Li","year":"2006","unstructured":"Li, C.L.: Scheduling unit-length jobs with machine eligibility restrictions. European Journal of Operational Research\u00a0174, 1325\u20131328 (2006)","journal-title":"European Journal of Operational Research"},{"key":"11_CR16","doi-asserted-by":"publisher","first-page":"458","DOI":"10.1016\/j.ejor.2006.11.027","volume":"184","author":"L.W. Liao","year":"2008","unstructured":"Liao, L.W., Sheen, G.J.: Parallel machine scheduling with machine availability and eligibility constraints. European Journal of Operational Research\u00a0184, 458\u2013467 (2008)","journal-title":"European Journal of Operational Research"},{"key":"11_CR17","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1016\/S0377-2217(02)00914-1","volume":"156","author":"Y. Lin","year":"2004","unstructured":"Lin, Y., Li, W.: Parallel machine scheduling of machine-dependent jobs with unit-length. European Journal of Operational Research\u00a0156, 261\u2013266 (2004)","journal-title":"European Journal of Operational Research"},{"key":"11_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/978-3-540-92185-1_30","volume-title":"Internet and Network Economics","author":"P. Lu","year":"2008","unstructured":"Lu, P., Yu, C.: Worst-case nash equilibria in restricted routing. In: Papadimitriou, C., Zhang, S. (eds.) WINE 2008. LNCS, vol.\u00a05385, pp. 231\u2013238. Springer, Heidelberg (2008)"},{"key":"11_CR19","volume-title":"Theoretical Aspects of Local Search","author":"W. Michiels","year":"2007","unstructured":"Michiels, W., Aarts, E., Korst, J.: Theoretical Aspects of Local Search. Springer, Berlin (2007)"},{"issue":"4","key":"11_CR20","doi-asserted-by":"publisher","first-page":"328","DOI":"10.1002\/nav.20286","volume":"55","author":"J. Ou","year":"2008","unstructured":"Ou, J., Leung, J.Y.T., Li, C.L.: Scheduling parallel machines with inclusive set restrictions. Naval Research Logistics\u00a055(4), 328\u2013338 (2008)","journal-title":"Naval Research Logistics"},{"key":"11_CR21","volume-title":"Scheduling: Theory, Algorithms and Systems","author":"M. Pinedo","year":"2008","unstructured":"Pinedo, M.: Scheduling: Theory, Algorithms and Systems, 3rd edn. Springer, New York (2008); Original edition published by Prentice Hall, Englewood Cliffs, NJ, (1995)","edition":"3"},{"key":"11_CR22","doi-asserted-by":"crossref","unstructured":"Recalde, D., Rutten, C., Vredeveld, T., Schuurman, P.: Local search performance guarantees for restricted related parallel machine scheduling. Technical report, Maastricht University, METEOR Research Memoranda RM\/09\/061, Maastricht, The Netherlands (2009)","DOI":"10.1007\/978-3-642-12200-2_11"},{"issue":"1","key":"11_CR23","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1287\/ijoc.1050.0152","volume":"19","author":"P. Schuurman","year":"2007","unstructured":"Schuurman, P., Vredeveld, T.: Performance guarantees of local search for multiprocessor scheduling. INFORMS Journal of Computing\u00a019(1), 52\u201363 (2007)","journal-title":"INFORMS Journal of Computing"},{"issue":"8","key":"11_CR24","first-page":"2266","volume":"33","author":"E.V. Shchepin","year":"2005","unstructured":"Shchepin, E.V., Vakhania, N.: An optimal rounding gives a better approximation for scheduling unrelated machines. Operations Research Letters\u00a033(8), 2266\u20132278 (2005)","journal-title":"Operations Research Letters"},{"issue":"8","key":"11_CR25","doi-asserted-by":"publisher","first-page":"763","DOI":"10.1080\/07408170304349","volume":"35","author":"G.L. Vairaktarakis","year":"2003","unstructured":"Vairaktarakis, G.L., Cai, X.: The value of processing flexibility in multipurpose machines. IIE Transactions\u00a035(8), 763\u2013774 (2003)","journal-title":"IIE Transactions"},{"key":"11_CR26","volume-title":"Algorithmic Game Theory","author":"B. V\u00f6cking","year":"2007","unstructured":"V\u00f6cking, B.: Selfish load balancing. In: Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V. (eds.) Algorithmic Game Theory, ch.\u00a020. Cambridge University Press, New York (2007)"}],"container-title":["Lecture Notes in Computer Science","LATIN 2010: Theoretical Informatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-12200-2_11.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,20]],"date-time":"2025-02-20T03:12:58Z","timestamp":1740021178000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-12200-2_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642121999","9783642122002"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-12200-2_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}