Top

Journal of Scheduling

Published in:

16-02-2017

Improved algorithms for resource allocation under varying capacity

Authors: Venkatesan T. Chakaravarthy, Anamitra R. Choudhury, Shalmoli Gupta, Sambudha Roy, Yogish Sabharwal

Published in: Journal of Scheduling | Issue 3/2018

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We consider the problem of scheduling a set of jobs on a system that offers certain resource, wherein the amount of resource offered varies over time. For each job, the input specifies a set of possible scheduling instances, where each instance is given by starting time, ending time, profit and resource requirement. A feasible solution selects a subset of job instances such that at any timeslot, the total requirement by the chosen instances does not exceed the resource available at that timeslot, and at most one instance is chosen for each job. The above problem falls under the well-studied framework of unsplittable flow problem on line. The generalized notion of scheduling possibilities captures the standard setting concerned with release times and deadlines. We present improved algorithms based on the primal–dual paradigm, where the improvements are in terms of approximation ratio, running time and simplicity.

previous article The triangle scheduling problem

next article Flexible bandwidth assignment with application to optical networks

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Adamaszek, A., & Wiese, A. (2013). Approximation schemes for maximum weight independent set of rectangles. In 54th Annual IEEE symposium on foundations of computer science, FOCS (pp. 400–409).

Adamaszek, A., Chalermsook, P., Ene, A., & Wiese, A. (2016). Submodular unsplittable flow on trees. In Proceedings of the 18th conference on integer programming and combinatorial optimization (IPCO).

Agarwal, P., Kreveld, M., & Suri, S. (1998). Label placement by maximum independent set in rectangles. Computational Geometry, 11(3–4), 209–218.CrossRef

Akcoglu, K., Aspnes, J., Dasgupta, B., & Kao, M. (2000). Opportunity cost algorithms for combinatorial auctions. In E. Kontoghiorghes, B. Rustem, & S. Siokos (Eds.), Applied optimization: Computational methods in decision-making, economics and finance (pp. 455–476) Kluwer Academic Publishers.

Anagnostopoulos, A., Grandoni, F., Leonardi, S., & Wiese, A. (2013). Constant integrality gap LP formulations of unsplittable flow on a path. In Proceedings of the 16th international conference on integer programming and combinatorial optimization (IPCO) (pp. 25–36).

Anagnostopoulos, A., Grandoni, F., Leonardi, S., & Wiese, A. (2014). A mazing \(2+\epsilon \) approximation for Unsplittable Flow on a Path. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on discrete algorithms, SODA (pp. 26–41).

Bansal, N., Chakrabarti, A., Epstein, A., & Schieber, B. (2006). A quasi-PTAS for unsplittable flow on line graphs. In Proceedings of the 38th annual ACM symposium on theory of computing, STOC (pp. 721–729).

Bansal, N., Friggstad, Z., Khandekar, R., & Salavatipour, M. (2009). A logarithmic approximation for unsplittable flow on line graphs. In Proceedings of the twentieth annual ACM-SIAM symposium on discrete algorithms, SODA (pp. 702–709).

Bar-Noy, A., Bar-Yehuda, R., Freund, A., Naor, J., & Schieber, B. (2001). A unified approach to approximating resource allocation and scheduling. Journal of the ACM, 48(5), 1069–1090.CrossRef

Bar-Noy, A., Guha, S., Noar, J., & Schieber, B. (2001). Approximating the throughput of multiple machines in real-time scheduling. SIAM Journal on Computing SICOMP, 31(2), 331–352.CrossRef

Berman, P., & Dasgupta, B. (2000). Multi-phase algorithms for throughput maximization for real-time scheduling. Journal of Combinatorial Optimization, 4(3), 307–323.CrossRef

Bonsma, P., Schulz, J., & Wiese, A. (2011). A constant factor approximation algorithm for unsplittable flow on paths. In IEEE 52nd annual symposium on foundations of computer science, FOCS (pp. 47–56).

Calinescu, G., Chakrabarti, A., Karloff, H. J., & Rabani, Y. (2002). Improved approximation algorithms for resource allocation. In Integer programming and combinatorial optimization, 9th International IPCO (pp. 401–414).

Chakaravarthy, V., Choudhury, A. R., & Sabharwal, Y. (2010). A near-linear time constant factor algorithm for unsplittable flow problem on line with bag constraints. In IARCS annual conference on foundations of software technology and theoretical computer science, FSTTCS (pp. 181–191).

Chakaravarthy, V., Choudhury, A., Roy, S., & Sabharwal, Y. (2013). Distributed algorithms for scheduling on line and tree networks with non-uniform bandwidths. In 27th IEEE international symposium on parallel and distributed processing, IPDPS (pp. 973–984).

Chakaravarthy, V., Pandit, V., Sabharwal, Y., & Seetharam, D. (2010). Varying bandwidth resource allocation problem with bag constraints. In 24th IEEE international symposium on parallel and distributed processing, IPDPS (pp. 1–10).

Chakaravarthy, V., Roy, S., & Sabharwal, Y. (2012). Distributed algorithms for scheduling on line and tree networks. In ACM symposium on principles of distributed computing, PODC (pp. 345–354).

Chakrabarti, A., Chekuri, C., Gupta, A., & Kumar, A. (2007). Approximation algorithms for the unsplittable flow problem. Algorithmica, 47(1), 53–78.CrossRef

Chalermsook, P., & Chuzhoy, J. (2009). Maximum independent set of rectangles. In Proceedings of the twentieth annual ACM-SIAM symposium on discrete algorithms, SODA (pp. 892–901).

Chekuri, C., Ene, A., & Korula, N. (2009). Unsplittable flow in paths and trees and column-restricted packing integer programs. In Proceedings of the 12th international workshop on approximation, randomization, and combinatorial optimization (APPROX) (pp.42–55).

Chekuri, C., Mydlarz, M., & Shepherd, F. (2007). Multicommodity demand flow in a tree and packing integer programs. ACM Transactions on Algorithms, 3(3), 27. doi:10.1145/1273340.1273343.

Chuzhoy, J., Ostrovsky, R., & Rabani, Y (2001). Approximation algorithms for the job interval selection problem and related scheduling problems. In 42nd Annual symposium on foundations of computer science, FOCS (pp. 348–356).

Elbassioni, K., Garg, N., Gupta, D., Kumar, A., Narula, V., & Pal, A. (2012). Approximation Algorithms for the Unsplittable Flow Problem on Paths and Trees. In IARCS annual conference on foundations of software technology and theoretical computer science, FSTTCS (pp. 267–275).

Erlebach, T., & Spieksma, F. (2003). Interval selection: Applications, algorithms, and lower bounds. Journal of Algorithms, 46(1), 27–53.CrossRef

Fowler, R., Paterson, M., & Tanimoto, S. (1981). Optimal packing and covering in the plane are NP-complete. Information Processing Letters, 12(3), 133–137.CrossRef

Grandoni, F., Ingala, S., & Uniyal, S. (2013). Improved approximation algorithms for unsplittable flow on a path with time windows. In Proceedings of the 13th workshop on approximation and online algorithms (pp. 25–36).

Khanna, S., Muthukrishnan, S., & Paterson, M. (1998). On approximating rectangle tiling and packing. In Proceedings of the ninth annual ACM-SIAM symposium on discrete algorithms, SODA (pp. 384–393).

Kolliopoulos, S. (2007). Edge-disjoint paths and unsplittable flow. In T. Gonzalez (Ed.), Handbook of approximation algorithms and metaheuristics. London: Chapman and Hall.

Panconesi, A., & Sozio, M. (2010). Fast primal-dual distributed algorithms for scheduling and matching problems. Distributed Computing, 22(4), 269–283.CrossRef

Spieksma, F. (1999). On the approximability of an interval scheduling problem. Journal of Scheduling, 2, 215–227.CrossRef

Ye, Y., & Borodin, A. (2012). Elimination graphs. ACM Transactions on Algorithms, 8(2), 14.CrossRef

Title: Improved algorithms for resource allocation under varying capacity
Authors: Venkatesan T. Chakaravarthy
Anamitra R. Choudhury
Shalmoli Gupta
Sambudha Roy
Yogish Sabharwal
Publication date: 16-02-2017
Publisher: Springer US
Published in: Journal of Scheduling / Issue 3/2018
Print ISSN: 1094-6136
Electronic ISSN: 1099-1425
DOI: https://doi.org/10.1007/s10951-017-0515-3

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 3/2018

An implicit model for multi-activity shift scheduling problems

New strategies for stochastic resource-constrained project scheduling

Algorithms for a special class of state-dependent shortest path problems with an application to the train routing problem

A survey on makespan minimization in semi-online environments

The triangle scheduling problem

Flexible bandwidth assignment with application to optical networks

Premium Partner