Optimization Online


Resource Allocation with Time Intervals

Andreas Darmann (andreas.darmann***at***uni-graz.at)
Ulrich Pferschy (pferschy***at***uni-graz.at)
Joachim Schauer (joachim.schauer***at***uni-graz.at)

Abstract: We study a resource allocation problem where jobs have the following characteristics: Each job consumes some quantity of a bounded resource during a certain time interval and induces a given profit. We aim to select a subset of jobs with maximal total profit such that the total resource consumed at any point in time remains bounded by the given resource capacity. While this case is trivially $\mathcal{NP}$-hard in general and polynomially solvable for uniform resource consumptions, our main result shows the $\mathcal{NP}$-hardness for the case of general resource consumptions but uniform profit values, i.e.\ for the case of maximizing the number of performed jobs. This result applies even for proper time intervals. We also give a deterministic (1/2-\eps)$-- approximation algorithm for the general problem on proper intervals improving upon the currently known $1/3$ ratio for general intervals. Finally, we study the worst-case performance ratio of a simple greedy algorithm.

Keywords: resource allocation, proper intervals, unsplittable flow

Category 1: Combinatorial Optimization

Category 2: Applications -- OR and Management Sciences (Scheduling )

Citation: The final version of this article appeared in Theoretical Computer Science: http://www.sciencedirect.com/science/article/pii/S0304397510004639 DOI: 10.1016/j.tcs.2010.08.028

Download: [PDF]

Entry Submitted: 09/21/2009
Entry Accepted: 09/21/2009
Entry Last Modified: 12/01/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society