### 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 + \varepsilon)$ for any $\varepsilon > 0$. 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.

Original language | English |
---|---|

Pages (from-to) | 414-419 |

Number of pages | 6 |

Journal | Discrete optimization |

Volume | 6 |

Issue number | 4 |

DOIs | |

Publication status | Published - Nov 2009 |

### Keywords

- Time-resource tradeoff
- Approximation algorithms
- Mathematical Programming
- Scheduling
- Computational Complexity

## Fingerprint Dive into the research topics of 'Scheduling jobs with time-resource tradeoff via nonlinear programming'. Together they form a unique fingerprint.

## Cite this

Grigoriev, A., & Uetz, M. J. (2009). Scheduling jobs with time-resource tradeoff via nonlinear programming.

*Discrete optimization*,*6*(4), 414-419. https://doi.org/10.1016/j.disopt.2009.05.002