Scheduling with Interjob Communication on Parallel Processors
J. König, A. Mäcker, F. Meyer auf der Heide, S. Riechers, in: Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA), 2016, pp. 563--577.
Download
157-chp_3A10.1007_2F978-3-319-48749-6_41.pdf
753.15 KB
Conference Paper
Author
König, Jürgen;
Mäcker, AlexanderLibreCat;
Meyer auf der Heide, FriedhelmLibreCat;
Riechers, Sören
Abstract
Consider a scheduling problem in which a set of jobs with interjob communication, canonically represented by a weighted tree, needs to be scheduled on m parallel processors interconnected by a shared communication channel. In each time step, we may allow any processed job to use a certain capacity of the channel in order to satisfy (parts of) its communication demands to adjacent jobs processed in parallel. The goal is to find a schedule that minimizes the makespan and in which communication demands of all jobs are satisfied.We show that this problem is NP-hard in the strong sense even if the number of processors and the maximum degree of the underlying tree is constant.Consequently, we design and analyze simple approximation algorithms with asymptotic approximation ratio 2-2/m in case of paths and a ratio of 5/2 in case of arbitrary trees.
Publishing Year
Proceedings Title
Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA)
forms.conference.field.series_title_volume.label
LNCS
Page
563--577
LibreCat-ID
Cite this
König J, Mäcker A, Meyer auf der Heide F, Riechers S. Scheduling with Interjob Communication on Parallel Processors. In: Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA). LNCS. ; 2016:563--577. doi:10.1007/978-3-319-48749-6_41
König, J., Mäcker, A., Meyer auf der Heide, F., & Riechers, S. (2016). Scheduling with Interjob Communication on Parallel Processors. In Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA) (pp. 563--577). https://doi.org/10.1007/978-3-319-48749-6_41
@inproceedings{König_Mäcker_Meyer auf der Heide_Riechers_2016, series={LNCS}, title={Scheduling with Interjob Communication on Parallel Processors}, DOI={10.1007/978-3-319-48749-6_41}, booktitle={Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA)}, author={König, Jürgen and Mäcker, Alexander and Meyer auf der Heide, Friedhelm and Riechers, Sören}, year={2016}, pages={563--577}, collection={LNCS} }
König, Jürgen, Alexander Mäcker, Friedhelm Meyer auf der Heide, and Sören Riechers. “Scheduling with Interjob Communication on Parallel Processors.” In Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA), 563--577. LNCS, 2016. https://doi.org/10.1007/978-3-319-48749-6_41.
J. König, A. Mäcker, F. Meyer auf der Heide, and S. Riechers, “Scheduling with Interjob Communication on Parallel Processors,” in Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA), 2016, pp. 563--577.
König, Jürgen, et al. “Scheduling with Interjob Communication on Parallel Processors.” Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA), 2016, pp. 563--577, doi:10.1007/978-3-319-48749-6_41.
Main File(s)
File Name
157-chp_3A10.1007_2F978-3-319-48749-6_41.pdf
753.15 KB
Access Level
Closed Access
Last Uploaded
2018-03-21T12:50:29Z
Google Scholar