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.ESA.2018.32
URN: urn:nbn:de:0030-drops-94959
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9495/
Go to the corresponding LIPIcs Volume Portal


Gálvez, Waldo ; Soto, José A. ; Verschae, José

Symmetry Exploitation for Online Machine Covering with Bounded Migration

pdf-format:
LIPIcs-ESA-2018-32.pdf (0.5 MB)


Abstract

Online models that allow recourse are highly effective in situations where classical models are too pessimistic. One such problem is the online machine covering problem on identical machines. In this setting, jobs arrive one by one and must be assigned to machines with the objective of maximizing the minimum machine load. When a job arrives, we are allowed to reassign some jobs as long as their total size is (at most) proportional to the processing time of the arriving job. The proportionality constant is called the migration factor of the algorithm.
By rounding the processing times, which yields useful structural properties for online packing and covering problems, we design first a simple (1.7 + epsilon)-competitive algorithm using a migration factor of O(1/epsilon) which maintains at every arrival a locally optimal solution with respect to the Jump neighborhood. After that, we present as our main contribution a more involved (4/3+epsilon)-competitive algorithm using a migration factor of O~(1/epsilon^3). At every arrival, we run an adaptation of the Largest Processing Time first (LPT) algorithm. Since the new job can cause a complete change of the assignment of smaller jobs in both cases, a low migration factor is achieved by carefully exploiting the highly symmetric structure obtained by the rounding procedure.

BibTeX - Entry

@InProceedings{glvez_et_al:LIPIcs:2018:9495,
  author =	{Waldo G{\'a}lvez and Jos{\'e} A. Soto and Jos{\'e} Verschae},
  title =	{{Symmetry Exploitation for Online Machine Covering with Bounded Migration}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{32:1--32:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Yossi Azar and Hannah Bast and Grzegorz Herman},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9495},
  URN =		{urn:nbn:de:0030-drops-94959},
  doi =		{10.4230/LIPIcs.ESA.2018.32},
  annote =	{Keywords: Machine Covering, Bounded Migration, Online, Scheduling, LPT}
}

Keywords: Machine Covering, Bounded Migration, Online, Scheduling, LPT
Collection: 26th Annual European Symposium on Algorithms (ESA 2018)
Issue Date: 2018
Date of publication: 14.08.2018


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI