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
Discrete Optimization
Paper
Scheduling split intervals with non-uniform demands
Abstract
We study the problem of maximizing the throughput of jobs wherein each job consists of multiple tasks. Consider a system offering a capacity of one unit. We are given a set of jobs, each consisting of a sequence of r tasks. Each task is associated with a demand and an interval where it should be scheduled. Each job has a profit associated with it. The objective is to select a subset of jobs having the maximum profit such that at any point of time the cumulative demand of the selected jobs does not exceed the system capacity. Prior work has presented O(r)-approximation algorithm for two special cases: (i) unit demands – all tasks have a demand of one unit; (ii) uniform demands – for any job, all its constituent tasks have the same demand. We study the general setting wherein the tasks of a job can have non-uniform demands. We present an O(r)-approximation for the case where all the tasks have demands at most 1∕2. The prior algorithms are based on the fractional local ratio technique, which we do not know how to generalize for the setting of non-uniform demands. Instead, we devise an algorithm based on the randomized rounding strategy. Our approach also provides alternative simpler algorithms for the unit and uniform demand settings. We next extend the algorithms to the more generic scenario wherein each task is associated with a processing time and a window consisting of release time and deadline, and design pseudo-polynomial time O(r)-approximation procedures.