License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2020.14
URN: urn:nbn:de:0030-drops-133582
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13358/
Nguyen, Trung Thanh ;
Rothe, Jörg
Bi-Criteria Approximation Algorithms for Load Balancing on Unrelated Machines with Costs
Abstract
We study a generalized version of the load balancing problem on unrelated machines with cost constraints: Given a set of m machines (of certain types) and a set of n jobs, each job j processed on machine i requires p_{i,j} time units and incurs a cost c_{i,j}, and the goal is to find a schedule of jobs to machines, which is defined as an ordered partition of n jobs into m disjoint subsets, in such a way that some objective function of the vector of the completion times of the machines is optimized, subject to the constraint that the total costs by the schedule must be within a given budget B. Motivated by recent results from the literature, our focus is on the case when the number of machine types is a fixed constant and we develop a bi-criteria approximation scheme for the studied problem. Our result generalizes several known results for certain special cases, such as the case with identical machines, or the case with a constant number of machines with cost constraints. Building on the elegant technique recently proposed by Jansen and Maack [K. Jansen and M. Maack, 2019], we construct a more general approach that can be used to derive approximation schemes to a wider class of load balancing problems with constraints.
BibTeX - Entry
@InProceedings{nguyen_et_al:LIPIcs:2020:13358,
author = {Trung Thanh Nguyen and J{\"o}rg Rothe},
title = {{Bi-Criteria Approximation Algorithms for Load Balancing on Unrelated Machines with Costs}},
booktitle = {31st International Symposium on Algorithms and Computation (ISAAC 2020)},
pages = {14:1--14:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-173-3},
ISSN = {1868-8969},
year = {2020},
volume = {181},
editor = {Yixin Cao and Siu-Wing Cheng and Minming Li},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/13358},
URN = {urn:nbn:de:0030-drops-133582},
doi = {10.4230/LIPIcs.ISAAC.2020.14},
annote = {Keywords: bi-criteria approximation algorithm, polynomial-time approximation algorithm, load balancing, machine scheduling}
}
|
Keywords: |
|
bi-criteria approximation algorithm, polynomial-time approximation algorithm, load balancing, machine scheduling |
|
Collection: |
|
31st International Symposium on Algorithms and Computation (ISAAC 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
04.12.2020 |
