DROPS

Document

DOI: 10.4230/LIPIcs.STACS.2017.22

Parameterized and Approximation Results for Scheduling with a Low Rank Processing Time Matrix

Authors: Lin Chen, Dániel Marx, Deshi Ye, and Guochuan Zhang

Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)

Abstract

We study approximation and parameterized algorithms for R||C_max, focusing on the problem when the rank of the matrix formed by job processing times is small. Bhaskara et al. initiated the study of approximation algorithms with respect to the rank, showing that R||C_max admits a QPTAS (Quasi-polynomial time approximation scheme) when the rank is 2, and becomes APX-hard when the rank is 4. We continue this line of research. We prove that R||C_max is APX-hard even if the rank is 3, resolving an open problem. We then show that R||C_max is FPT parameterized by the rank and the largest job processing time p_max. This generalizes the parameterized results on P||C_max and R||C_max with few different types of machines. We also provide nearly tight lower bounds under Exponential Time Hypothesis which suggests that the running time of the FPT algorithm is unlikely to be improved significantly.

Cite as

Lin Chen, Dániel Marx, Deshi Ye, and Guochuan Zhang. Parameterized and Approximation Results for Scheduling with a Low Rank Processing Time Matrix. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 22:1-22:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.STACS.2017.22,
  author =	{Chen, Lin and Marx, D\'{a}niel and Ye, Deshi and Zhang, Guochuan},
  title =	{{Parameterized and Approximation Results for Scheduling with a Low Rank Processing Time Matrix}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{22:1--22:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Vollmer, Heribert and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.22},
  URN =		{urn:nbn:de:0030-drops-70110},
  doi =		{10.4230/LIPIcs.STACS.2017.22},
  annote =	{Keywords: APX-hardness, Parameterized algorithm, Scheduling, Exponential Time Hypothesis}
}

Document

DOI: 10.4230/LIPIcs.APPROX-RANDOM.2016.5

Approximation Algorithms for Parallel Machine Scheduling with Speed-up Resources

Authors: Lin Chen, Deshi Ye, and Guochuan Zhang

Published in: LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)

Abstract

We consider the problem of scheduling with renewable speed-up resources. Given m identical machines, n jobs and c different discrete resources, the task is to schedule each job non-preemptively onto one of the machines so as to minimize the makespan. In our problem, a job has its original processing time, which could be reduced by utilizing one of the resources. As resources are different, the amount of the time reduced for each job is different depending on the resource it uses. Once a resource is being used by one job, it can not be used simultaneously by any other job until this job is finished, hence the scheduler should take into account the job-to-machine assignment together with the resource-to-job assignment. We observe that, the classical unrelated machine scheduling problem is actually a special case of our problem when m=c, i.e., the number of resources equals the number of machines. Extending the techniques for the unrelated machine scheduling, we give a 2-approximation algorithm when both m and c are part of the input. We then consider two special cases for the problem, with m or c being a constant, and derive PTASes (Polynomial Time Approximation Schemes) respectively. We also establish the relationship between the two parameters m and c, through which we are able to transform the PTAS for the case when m is constant to the case when c is a constant. The relationship between the two parameters reveals the structure within the problem, and may be of independent interest.

Cite as

Lin Chen, Deshi Ye, and Guochuan Zhang. Approximation Algorithms for Parallel Machine Scheduling with Speed-up Resources. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 5:1-5:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.APPROX-RANDOM.2016.5,
  author =	{Chen, Lin and Ye, Deshi and Zhang, Guochuan},
  title =	{{Approximation Algorithms for Parallel Machine Scheduling with Speed-up Resources}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
  pages =	{5:1--5:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-018-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{60},
  editor =	{Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.5},
  URN =		{urn:nbn:de:0030-drops-66283},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2016.5},
  annote =	{Keywords: approximation algorithms, scheduling, linear programming}
}

Search Results

Documents authored by Ye, Deshi

Parameterized and Approximation Results for Scheduling with a Low Rank Processing Time Matrix

Abstract

Cite as

Approximation Algorithms for Parallel Machine Scheduling with Speed-up Resources

Abstract

Cite as

Thanks for your feedback!

Could not send message