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.MFCS.2020.84
URN: urn:nbn:de:0030-drops-127459
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12745/
Go to the corresponding LIPIcs Volume Portal

Thắng, Nguyễn Kim

An Improved Approximation Algorithm for Scheduling Under Arborescence Precedence Constraints

pdf-format:
LIPIcs-MFCS-2020-84.pdf (0.5 MB)

Abstract

We consider a scheduling problem on unrelated machines with precedence constraints. There are m unrelated machines and n jobs and every job has to be processed non-preemptively in some machine. Moreover, jobs have precedence constraints; specifically, a precedence constraint j ≺ j' requires that job j' can only be started whenever job j has been completed. The objective is to minimize the total completion time.
The problem has been widely studied in more restricted machine environments such as identical or related machines. However, for unrelated machines, much less is known. In the paper, we study the problem where the precedence constraints form a forest of arborescences. We present a O((log n)² / (log log n)³)-approximation algorithm - that improves the best-known guarantee of O((log n)² / log log n) due to Kumar et al. a decade ago. The analysis relies on a dual-fitting method in analyzing the Lagrangian function of non-convex programs.

BibTeX - Entry

@InProceedings{thng:LIPIcs:2020:12745,
  author =	{Nguyễn Kim Thắng},
  title =	{{An Improved Approximation Algorithm for Scheduling Under Arborescence Precedence Constraints}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{84:1--84:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Javier Esparza and Daniel Kr{\'a}ľ},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12745},
  URN =		{urn:nbn:de:0030-drops-127459},
  doi =		{10.4230/LIPIcs.MFCS.2020.84},
  annote =	{Keywords: Scheduling, Precedence Constraints, Lagrangian Duality}
}

Keywords: Scheduling, Precedence Constraints, Lagrangian Duality
Collection: 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
Issue Date: 2020
Date of publication: 18.08.2020

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