{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:16:40Z","timestamp":1759637800277},"reference-count":15,"publisher":"World Scientific Pub Co Pte Ltd","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Parallel Process. Lett."],"published-print":{"date-parts":[[2012,6]]},"abstract":"<jats:p>We consider the parallel computing environment where m organizations provide machines and several jobs to be executed. While cooperation of organizations is required to minimize the global makespan, each organization also expects the faster completion of its own jobs primarily and thus it is not necessarily cooperative. To handle the situations, we formulate the \u03b1-cooperative multi-organization scheduling problem (\u03b1-MOSP), where \u03b1 \u2265 1 is a parameter representing the degree of cooperativeness. \u03b1-MOSP minimizes the makespan under the multi-organization constraint that each organization does not allow the completion time of its own jobs to be delayed \u03b1 times of that in the case where those jobs are executed by itself.<\/jats:p><jats:p>First, we reveal the relation between the makespan and the degree of cooperativeness. We show that the multi-organization constraint may degrade the optimal makespan by m times for \u03b1 = 1, while the degradation ratio is bounded by \u03b1\/(\u03b1 - 1) for \u03b1 &gt; 1. This implies that weak cooperation improves the makespan dramatically. Second, we study the complexity of \u03b1-MOSP. We show its strongly NP-hardness and inapproximability for the approximation factor less than max {(\u03b1 + 1)\/\u03b1, 3\/2}. We also show the hardness of transformation from an optimal schedule under no multi-organization constraint to an optimal schedule for \u03b1-MOSP. This result is a witness for inexistence of a general polynomial-time transformation algorithm that preserves the approximation ratio.<\/jats:p>","DOI":"10.1142\/s0129626412500065","type":"journal-article","created":{"date-parts":[[2012,5,14]],"date-time":"2012-05-14T12:03:00Z","timestamp":1336996980000},"page":"1250006","source":"Crossref","is-referenced-by-count":1,"title":["THE PRICE OF MULTI-ORGANIZATION CONSTRAINT IN UNRELATED PARALLEL MACHINE SCHEDULING"],"prefix":"10.1142","volume":"22","author":[{"given":"FUKUHITO","family":"OOSHITA","sequence":"first","affiliation":[{"name":"Graduate School of Information Science and Technology, Osaka University, 1-5 Yamadaoka, Suita, Osaka 565-0871, Japan"}]},{"given":"TOMOKO","family":"IZUMI","sequence":"additional","affiliation":[{"name":"College of Information Science and Engineering, Ritsumeikan University, 1-1-1 Noji higashi, Kusatsu, Shiga 525-8577, Japan"}]},{"given":"TAISUKE","family":"IZUMI","sequence":"additional","affiliation":[{"name":"Graduate School of Engineering, Nagoya Institute of Technology, Gokiso-tyo, Syowa-ku, Nagoya, Aichi 466-8555, Japan"}]}],"member":"219","published-online":{"date-parts":[[2012,5,16]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.1378"},{"key":"rf2","doi-asserted-by":"crossref","DOI":"10.1201\/9780203489802","volume-title":"Handbook of Scheduling: Algorithms, Models, and Performance Analysis","author":"Leung J. Y.-T.","year":"2004"},{"key":"rf3","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey M. R.","year":"1979"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1145\/322003.322011"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1145\/322276.322284"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585745"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2004.05.004"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.12.032"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.07.057"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2007.06.067"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2009.09.003"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1006\/game.1999.0790"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1145\/1721837.1721854"},{"key":"rf22","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1040.0197"},{"key":"rf23","doi-asserted-by":"publisher","DOI":"10.1002\/net.20133"}],"container-title":["Parallel Processing Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129626412500065","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,15]],"date-time":"2022-01-15T16:00:46Z","timestamp":1642262446000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129626412500065"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,5,16]]},"references-count":15,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2012,5,16]]},"published-print":{"date-parts":[[2012,6]]}},"alternative-id":["10.1142\/S0129626412500065"],"URL":"https:\/\/doi.org\/10.1142\/s0129626412500065","relation":{},"ISSN":["0129-6264","1793-642X"],"issn-type":[{"value":"0129-6264","type":"print"},{"value":"1793-642X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,5,16]]}}}