Approximation algorithms for parallel machine scheduling with speed-up resources

Lin Chen, Deshi Ye, Guochuan Zhang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish
Title of host publicationApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 19th International Workshop, APPROX 2016 and 20th International Workshop, RANDOM 2016
EditorsKlaus Jansen, Claire Mathieu, Jose D. P. Rolim, Chris Umans
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770187
DOIs
StatePublished - Sep 1 2016
Event19th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2016 and the 20th International Workshop on Randomization and Computation, RANDOM 2016 - Paris, France
Duration: Sep 7 2016Sep 9 2016

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume60
ISSN (Print)1868-8969

Conference

Conference19th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2016 and the 20th International Workshop on Randomization and Computation, RANDOM 2016
CountryFrance
CityParis
Period09/7/1609/9/16

Keywords

  • Approximation Algorithms
  • Linear Programming
  • Scheduling

Fingerprint Dive into the research topics of 'Approximation algorithms for parallel machine scheduling with speed-up resources'. Together they form a unique fingerprint.

  • Cite this

    Chen, L., Ye, D., & Zhang, G. (2016). Approximation algorithms for parallel machine scheduling with speed-up resources. In K. Jansen, C. Mathieu, J. D. P. Rolim, & C. Umans (Eds.), Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 19th International Workshop, APPROX 2016 and 20th International Workshop, RANDOM 2016 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 60). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2016.5