More Web Proxy on the site http://driver.im/

research-article

Approximation Schemes for Machine Scheduling with Resource (In-)dependent Processing Times

Authors:

Malin RauAuthors Info & Claims

ACM Transactions on Algorithms (TALG), Volume 15, Issue 3

Article No.: 31, Pages 1 - 28

https://doi.org/10.1145/3302250

Published: 07 May 2019 Publication History

Abstract

We consider two related scheduling problems: single resource-constrained scheduling on identical parallel machines and a generalization with resource-dependent processing times. In both problems, jobs require a certain amount of an additional resource and have to be scheduled on machines minimizing the makespan, while at every point in time a given resource capacity is not exceeded. In the first variant of the problem, the processing times and resource amounts are fixed, while in the second the former depends on the latter.

Both problems contain bin packing with cardinality constraint as a special case, and, therefore, these problems are strongly NP-complete even for a constant number of machines larger than three, which can be proven by a reduction from 3-Partition. Furthermore, if the number of machines is part of the input, then we cannot hope for an approximation algorithm with absolute approximation ratio smaller than 3/2.

We present asymptotic fully polynomial time approximation schemes (AFPTAS) for the problems: For any ε > 0, a schedule of length at most (1+ε) times the optimum plus an additive term of O(p_max log (1/ε)/ε) is provided, and the running time is polynomially bounded in 1/ε and the input length. Up to now, only approximation algorithms with absolute approximation ratios were known. Furthermore, the AFPTAS for resource-constrained scheduling on identical parallel machines directly improves the additive term of the best AFPTAS for bin packing with cardinality constraint so far.

References

[1]

Peter A. Beling and Nimrod Megiddo. 1998. Using fast matrix multiplication to find basic solutions. Theor. Comput. Sci. 205, 1 (1998), 307--316.

Digital Library

[2]

Marin Bougeret, Pierre-François Dutot, Klaus Jansen, Christina Robenek, and Denis Trystram. 2011. Approximation algorithms for multiple strip packing and scheduling parallel jobs in platforms. Discrete Math., Alg. Appl. 3, 4 (2011), 553--586.

[3]

Marin Bougeret, Pierre-François Dutot, Klaus Jansen, Christina Robenek, and Denis Trystram. 2011. Approximation algorithms for multiple strip packing and scheduling parallel jobs in platforms. Discrete Math., Alg. and Appl. 3, 4 (2011), 553--586.

[4]

Wenceslas Fernandez de la Vega and George S. Lueker. 1981. Bin packing can be solved within 1+epsilon in linear time. Combinatorica 1, 4 (1981), 349--355.

[5]

Leah Epstein and Asaf Levin. 2010. AFPTAS results for common variants of bin packing: A new method for handling the small items. SIAM J. Optimiz. 20, 6 (2010), 3121--3145.

Digital Library

[6]

Michael R. Garey and Ronald L. Graham. 1975. Bounds for multiprocessor scheduling with resource constraints. SIAM J. Comput. 4, 2 (1975), 187--200.

Digital Library

[7]

Michael R. Garey and David S. Johnson. 1975. Complexity results for multiprocessor scheduling under resource constraints. SIAM J. Comput. 4, 4 (1975), 397--411.

Digital Library

[8]

Michael D. Grigoriadis, Leonid G. Khachiyan, Lorant Porkolab, and Jorge Villavicencio. 2001. Approximate max-min resource sharing for structured concave optimization. SIAM J. Optimiz. 11, 4 (2001), 1081--1091.

Digital Library

[9]

Alexander Grigoriev, Maxim Sviridenko, and Marc Uetz. 2007. Machine scheduling with resource dependent processing times. Math. Program. 110, 1 (2007), 209--228.

[10]

Alexander Grigoriev and Marc Uetz. 2009. Scheduling jobs with time-resource tradeoff via nonlinear programming. Discrete Optimiz. 6, 4 (2009), 414--419.

Digital Library

[11]

Klaus Jansen. 2004. Scheduling malleable parallel tasks: An asymptotic fully polynomial time approximation scheme. Algorithmica 39, 1 (2004), 59--81.

Digital Library

[12]

Klaus Jansen, Marten Maack, and Malin Rau. 2016. Approximation schemes for machine scheduling with resource (in-) dependent processing times. In Proceedings of the 27th ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 1526--1542.

Digital Library

[13]

Narendra Karmarkar and Richard M. Karp. 1982. An efficient approximation scheme for the one-dimensional bin-packing problem. In Proceedings of the 23rd Symposium on Foundations of Computer Science (FOCS’82). 312--320.

Digital Library

[14]

ShanXue Ke, BenSheng Zeng, WenBao Han, and Victor Y. Pan. 2008. Fast rectangular matrix multiplication and some applications. Science in China Series A: Mathematics 51, 3 (2008), 389--406.

[15]

Hans Kellerer. 2008. An approximation algorithm for identical parallel machine scheduling with resource dependent processing times. Op. Res. Lett. 36, 2 (2008), 157--159.

Digital Library

[16]

Claire Kenyon and Eric Rémila. 2000. A near-optimal solution to a two-dimensional cutting stock problem. Math. Op. Res. 25, 4 (2000), 645--656.

Digital Library

[17]

Peter Kling, Alexander Mäcker, Sören Riechers, and Alexander Skopalik. 2017. Sharing is caring: Multiprocessor scheduling with a sharable resource. In Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA’17). 123--132.

Digital Library

[18]

Eugene L. Lawler. 1979. Fast approximation algorithms for knapsack problems. Math. Op. Res. 4, 4 (1979), 339--356.

Digital Library

[19]

Monaldo Mastrolilli and Marcus Hutter. 2006. Hybrid rounding techniques for knapsack problems. Discrete Appl. Math. 154, 4 (2006), 640--649.

Digital Library

[20]

Martin Niemeier and Andreas Wiese. 2015. Scheduling with an orthogonal resource constraint. Algorithmica 71, 4 (2015), 837--858.

Digital Library

[21]

Maxim Sviridenko. 2012. A note on the Kenyon-Remila strip-packing algorithm. Inf. Process. Lett. 112, 1--2 (2012), 10--12.

Digital Library

Cited By

Jaykrishnan GLevin A(2024)Scheduling with cardinality dependent unavailability periodsEuropean Journal of Operational Research10.1016/j.ejor.2024.02.038316:2(443-458)Online publication date: Jul-2024
https://doi.org/10.1016/j.ejor.2024.02.038
Deppert MJansen KMaack MPukrop SRau M(2023)Scheduling with Many Shared Resources2023 IEEE International Parallel and Distributed Processing Symposium (IPDPS)10.1109/IPDPS54959.2023.00049(413-423)Online publication date: May-2023
https://doi.org/10.1109/IPDPS54959.2023.00049
Jaykrishnan GLevin A(2023)EPTAS for the dual of splittable bin packing with cardinality constraintTheoretical Computer Science10.1016/j.tcs.2023.114202979(114202)Online publication date: Nov-2023
https://doi.org/10.1016/j.tcs.2023.114202
Show More Cited By

Index Terms

Approximation Schemes for Machine Scheduling with Resource (In-)dependent Processing Times
1. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
    2. Mathematical optimization
      1. Discrete optimization

Recommendations

Machine scheduling with resource dependent processing times

We consider machine scheduling on unrelated parallel machines with the objective to minimize the schedule makespan. We assume that, in addition to its machine dependence, the processing time of any job is dependent on the usage of a discrete renewable ...
Single machine batch scheduling with deadlines and resource dependent processing times

We consider the problem of scheduling n jobs on a single machine where each job has a deadline and a processing time that is a linear decreasing function of the amount of a common discrete resource allocated to the job. Jobs may be combined to form ...
Approximation schemes for parallel machine scheduling problems with controllable processing times

We consider the problem of scheduling n independent jobs on m identical machines that operate in parallel. Each job has a controllable processing time. The fact that the jobs have a controllable processing time means that it is allowed to compress (a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Algorithms

ACM Transactions on Algorithms Volume 15, Issue 3

July 2019

392 pages

ISSN:1549-6325

EISSN:1549-6333

DOI:10.1145/3331056

Editor:
Aravind Srinivasan
University of Maryland, USA

Issue’s Table of Contents

Copyright © 2019 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 May 2019

Accepted: 01 December 2018

Revised: 01 November 2018

Received: 01 January 2018

Published in TALG Volume 15, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

German Research Foundation (DFG)

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
280
Total Downloads

Downloads (Last 12 months)18
Downloads (Last 6 weeks)1

Reflects downloads up to 05 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Jaykrishnan GLevin A(2024)Scheduling with cardinality dependent unavailability periodsEuropean Journal of Operational Research10.1016/j.ejor.2024.02.038316:2(443-458)Online publication date: Jul-2024
https://doi.org/10.1016/j.ejor.2024.02.038
Deppert MJansen KMaack MPukrop SRau M(2023)Scheduling with Many Shared Resources2023 IEEE International Parallel and Distributed Processing Symposium (IPDPS)10.1109/IPDPS54959.2023.00049(413-423)Online publication date: May-2023
https://doi.org/10.1109/IPDPS54959.2023.00049
Jaykrishnan GLevin A(2023)EPTAS for the dual of splittable bin packing with cardinality constraintTheoretical Computer Science10.1016/j.tcs.2023.114202979(114202)Online publication date: Nov-2023
https://doi.org/10.1016/j.tcs.2023.114202
Ma XLi Z(2022)Balanced Scheduling Method of Network Information Resources for Cloud StorageInternational Journal of Information Security and Privacy10.4018/IJISP.31051416:2(1-17)Online publication date: 7-Oct-2022
https://dl.acm.org/doi/10.4018/IJISP.310514
Ma XLi Z(2022)Balanced scheduling method of network information resources for cloud storageJournal of Control and Decision10.1080/23307706.2022.2078435(1-11)Online publication date: 16-Jun-2022
https://doi.org/10.1080/23307706.2022.2078435
Yim SHong SPark MChung Y(2022)Inverse interval scheduling via reduction on a single machineEuropean Journal of Operational Research10.1016/j.ejor.2022.02.046303:2(541-549)Online publication date: Dec-2022
https://doi.org/10.1016/j.ejor.2022.02.046
Zhang AZhen TChen YChen G(2022)An improved algorithm for parallel machine scheduling under additional resource constraintsOptimization Letters10.1007/s11590-022-01928-z17:3(753-769)Online publication date: 12-Sep-2022
https://doi.org/10.1007/s11590-022-01928-z
Maack M(2022)Approximation Schemes for Machine SchedulingOperations Research Proceedings 202110.1007/978-3-031-08623-6_4(21-26)Online publication date: 30-Aug-2022
https://doi.org/10.1007/978-3-031-08623-6_4
Naruszko APrzybylski BRządca K(2021)A Log-Linear -Approximation Algorithm for Parallel Machine Scheduling with a Single Orthogonal ResourceEuro-Par 2021: Parallel Processing10.1007/978-3-030-85665-6_10(151-166)Online publication date: 1-Sep-2021
https://dl.acm.org/doi/10.1007/978-3-030-85665-6_10
Damerius CKling PLi MSchneider FZhang R(2020)Improved Scheduling with a Shared Resource via Structural InsightsCombinatorial Optimization and Applications10.1007/978-3-030-64843-5_12(168-182)Online publication date: 11-Dec-2020
https://dl.acm.org/doi/10.1007/978-3-030-64843-5_12

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View Issue’s Table of Contents