World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

THE PRICE OF MULTI-ORGANIZATION CONSTRAINT IN UNRELATED PARALLEL MACHINE SCHEDULING

    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 α-cooperative multi-organization scheduling problem (α-MOSP), where α ≥ 1 is a parameter representing the degree of cooperativeness. α-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 α times of that in the case where those jobs are executed by itself.

    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 α = 1, while the degradation ratio is bounded by α/(α - 1) for α > 1. This implies that weak cooperation improves the makespan dramatically. Second, we study the complexity of α-MOSP. We show its strongly NP-hardness and inapproximability for the approximation factor less than max{(α + 1)/α, 3/2}. We also show the hardness of transformation from an optimal schedule under no multi-organization constraint to an optimal schedule for α-MOSP. This result is a witness for inexistence of a general polynomial-time transformation algorithm that preserves the approximation ratio.

    The conference version of this paper is published in the proceedings of 2009 International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT 2009).

    References

    • F. Pascual, K. Rzadca and D. Trystram, Concurrency and Computation: Practice and Experience 21(7), 905 (2009). Crossref, ISIGoogle Scholar
    • J. Y.-T.   Leung (ed.) , Handbook of Scheduling: Algorithms, Models, and Performance Analysis ( CRC Press , 2004 ) . CrossrefGoogle Scholar
    • M. R.   Garey and D. S.   Johnson , Computers and Intractability: A Guide to the Theory of NP-Completeness ( Freeman , 1979 ) . Google Scholar
    • O. H. Ibarra and C. E. Kim, Journal of the ACM 24(2), 280 (1977). Crossref, ISIGoogle Scholar
    • E. Davis and J. M. Jaffe, Journal of the ACM 28(4), 721 (1981). Crossref, ISIGoogle Scholar
    • J. K. Lenstra, D. B. Shmoys and É. Tardos, Mathematical Programming 46(3), 259 (1990). Crossref, ISIGoogle Scholar
    • E. V. Shchepin and N. Vakhania, Operations Research Letters 33, 127 (2005). Crossref, ISIGoogle Scholar
    • G. Christodoulou, E. Koutsoupias and A. Nanavati, Coordination mechanisms, Proceedings of the 31st International Colloquium on Automata, Languages and Programming (2004) pp. 345–357. Google Scholar
    • E. Koutsoupias and C. Papadimitriou, Worst-case equilibria, Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science (1999) pp. 404–413. Google Scholar
    • A. S. Schulz and N. E. Stier-Moses, On the performance of user equilibria in traffic networks, Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (2003) pp. 86–87. Google Scholar
    • N. Immorlicaet al., Theoretical Computer Science 410, 1589 (2009). Crossref, ISIGoogle Scholar
    • E. Angel, E. Bampis and F. Pascual, The price of approximate stability for scheduling selfish tasks on two links, Proceedings of the 12th International Euro-Par Conference (2006) pp. 157–166. Google Scholar
    • E. Angel, E. Bampis and F. Pascual, Theoretical Computer Science 369, 157 (2006). Crossref, ISIGoogle Scholar
    • G. Christodoulou, L. Gourvès and F. Pascual, Scheduling selfish tasks: About the performance of truthful algorithms, Proceedings of the 13th Annual International Computing and Combinatorics Conference (2007) pp. 187–197. Google Scholar
    • J. Cohenet al., Analysis of multi-organization scheduling algorithms, Proceedings of the 16th International Euro-Par Conference (2010) pp. 367–379. Google Scholar
    • K. Rzadca and D. Trystram, European Journal of Operational Research 199, 647 (2009). Crossref, ISIGoogle Scholar
    • R. Subrata, A. Y. Zomaya and B. Landfeldt, Journal of Parallel and Distributed Computing 70, 84 (2010). Crossref, ISIGoogle Scholar
    • N. Nisan and A. Ronen, Games and Economic Behavior 35, 166 (2001). Crossref, ISIGoogle Scholar
    • G. Christodoulou, E. Koutsoupias and A. Vidali, A lower bound for scheduling mechanisms, Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (2007) pp. 1163–1170. Google Scholar
    • R. Lavi and C. Swamy, Truthful mechanism design for multi-dimensional scheduling via cycle monotonicity, Proceedings of the 8th ACM Conference on Electronic Commerce (2007) pp. 252–261. Google Scholar
    • G. Christodoulou, E. Koutsoupias and A. Kovács, ACM Transactions on Algorithms 6(38), 1 (2010). Crossref, ISIGoogle Scholar
    • O. Jahnet al., Operations Research 53, 600 (2005). Crossref, ISIGoogle Scholar
    • A. S. Schulz and N. E. Stier-Moses, Networks 48, 223 (2006). Crossref, ISIGoogle Scholar