Name
Abstract | ||
|---|---|---|
We consider a scheduling problem where the processing time of any job is dependent on the usage of a discrete renewable resource, e.g. personnel. An amount of k units of that resource can be allocated to the jobs at any time, and the more of that resource is allocated to a job, the smaller its processing time. The objective is to find a resource allocation and a schedule that minimizes the makespan. We explicitly allow for succinctly encodable time-resource tradeoff functions, which calls for mathematical programming techniques other than those that have been used before. Utilizing a (nonlinear) integer mathematical program, we obtain the first polynomial time approximation algorithm for the scheduling problem, with performance bound (3+@e) for any @e0. Our approach relies on a fully polynomial time approximation scheme to solve the nonlinear mathematical programming relaxation. We also derive lower bounds for the approximation. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1016/j.disopt.2009.05.002 | Discrete Optimization |
Keywords | Field | DocType |
integer mathematical program,resource allocation,computational complexity,polynomial time approximation algorithm,nonlinear mathematical programming relaxation,approximation algorithms,nonlinear programming,time-resource tradeoff,scheduling problem,k unit,processing time,scheduling job,mathematical programming technique,polynomial time approximation scheme,discrete renewable resource,scheduling,mathematical programming,lower bound,renewable resources,fully polynomial time approximation scheme,publication | Approximation algorithm,Mathematical optimization,Nonlinear system,Job shop scheduling,Scheduling (computing),Computer science,Nonlinear programming,Theoretical computer science,Resource allocation,Polynomial-time approximation scheme,Computational complexity theory | Journal |
Volume | Issue | ISSN |
6 | 4 | Discrete Optimization |
Citations | PageRank | References |
7 | 0.63 | 12 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alexander Grigoriev | 1 | 203 | 24.23 |
| Marc Uetz | 2 | 456 | 43.99 |