About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
HiPC 2011
Conference paper
Maximizing throughput of jobs with multiple resource requirements
Abstract
We consider the problem of scheduling jobs that require multiple resources such as memory, bandwidth and processors. For each job, the input specifies start time, finish time and profit; the input also specifies the job's requirement for each resource. Each resource has a fixed capacity (called bandwidth). A feasible solution is a subset of jobs such that for any timeslot and any resource, the total requirement of the jobs active at the timeslot does not exceed the capacity of the resource. The goal is to maximize the profit of the jobs selected. We present an approximation algorithm with provable guarantees and effective heuristics for this problem. The algorithm has an approximation ratio of O(r), where r is the number of resources. We present an experimental evaluation of our algorithms that exhibit their effectiveness. © 2011 IEEE.