Name
Abstract | ||
|---|---|---|
We study resource constrained scheduling problems where the objective is to compute feasible preemptive schedules minimizing the makespan and using no more resources than what are available. We present approximation schemes along with some inapproximibility results showing how the approximability of the problem changes in terms of the number of resources. The results are based on linear programming formulations (though with exponentially many variables) and some interesting connections between resource constrained scheduling and (multidimensional, multiple-choice, and cardinality constrained) variants of the classical knapsack problem. In order to prove the results we generalize a method by Grigoriadis et al. for the max-min resource sharing problem to the case with weak approximate block solvers (i.e. with only constant, logarithmic, or even worse approximation ratios). Finally we present applications of the above results in fractional graph coloring and multiprocessor task scheduling. |
Year | Venue | Keywords |
|---|---|---|
2002 | SIAM Journal on Discrete Mathematics | linear programming,approximation algorithms,scheduling,polynomial time approximation scheme |
Field | DocType | Citations |
Discrete mathematics,Approximation algorithm,Mathematical optimization,Job shop scheduling,Scheduling (computing),Computer science,Schedule,Linear programming,Knapsack problem,Time complexity,Graph coloring | Conference | 24 |
PageRank | References | Authors |
1.52 | 45 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Klaus Jansen | 1 | 789 | 82.68 |
| Lorant Porkolab | 2 | 271 | 21.28 |