Abstract
We consider the problem of scheduling with renewable speedup resources. Given m identical machines, n jobs and c different discrete resources, the task is to schedule each job nonpreemptively 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 jobtomachine assignment together with the resourcetojob 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 2approximation 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.
BibTeX  Entry
@InProceedings{chen_et_al:LIPIcs:2016:6628,
author = {Lin Chen and Deshi Ye and Guochuan Zhang},
title = {{Approximation Algorithms for Parallel Machine Scheduling with Speedup Resources}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
pages = {5:15:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770187},
ISSN = {18688969},
year = {2016},
volume = {60},
editor = {Klaus Jansen and Claire Mathieu and Jos{\'e} D. P. Rolim and Chris Umans},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6628},
URN = {urn:nbn:de:0030drops66283},
doi = {10.4230/LIPIcs.APPROXRANDOM.2016.5},
annote = {Keywords: approximation algorithms, scheduling, linear programming}
}
Keywords: 

approximation algorithms, scheduling, linear programming 
Collection: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016) 
Issue Date: 

2016 
Date of publication: 

06.09.2016 