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

article

Machine scheduling with resource dependent processing times

Authors:

Alexander Grigoriev,

Maxim Sviridenko,

Marc UetzAuthors Info & Claims

Mathematical Programming: Series A and B, Volume 110, Issue 1

Pages 209 - 228

Published: 01 June 2007 Publication History

Abstract

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 resource, e.g. workers. A given amount of that resource can be distributed over the jobs in process at any time, and the more of that resource is allocated to a job, the smaller is its processing time. This model generalizes the classical unrelated parallel machine scheduling problem by adding a time-resource tradeoff. It is also a natural variant of a generalized assignment problem studied previously by Shmoys and Tardos. On the basis of an integer linear programming formulation for a relaxation of the problem, we use LP rounding techniques to allocate resources to jobs, and to assign jobs to machines. Combined with Graham's list scheduling, we show how to derive a 4-approximation algorithm. We also show how to tune our approach to yield a 3.75-approximation algorithm. This is achieved by applying the same rounding technique to a slightly modified linear programming relaxation, and by using a more sophisticated scheduling algorithm that is inspired by the harmonic algorithm for bin packing. We finally derive inapproximability results for two special cases, and discuss tightness of the integer linear programming relaxations.

References

[1]

Blazewicz J., Lenstra J.K. and Rinnooy Kan A.H.G. (1983). Scheduling subject to resource constraints: Classification and complexity. Discr. Appl. Math. 5: 11---24

[2]

Chen Z.-L. (2004). Simultaneous job scheduling and resource allocation on parallel machines. Ann. Oper. Res. 129: 135---153

[3]

Gandhi, R., Khuller, S., Parthasarathy, S., Srinivasan, A.: Dependent rounding in bipartite graphs. In: Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, pp.323---332. (2002).

Digital Library

[4]

Garey M.R. and Johnson D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completenes. Freeman, W.H. New York

[5]

Graham R.L. (1966). Bounds for certain multiprocessing anomalies. Bell Syst. Tech. J. 45: 1563---1581

[6]

Graham R.L. (1969). Bounds on multiprocessing timing anomalies. SIAM J. Appl. Math. 17: 416---429

Digital Library

[7]

Graham R.L., Lawler E.L., Lenstra J.K. and Rinnooy Kan A.H.G. (1979). Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discr. Math. 5: 287---326

[8]

Grigoriev, A., Kellerer, H., Strusevich, V.A.: Scheduling parallel dedicated machines with the speeding-up resource, manuscript (2003). Extended abstract. In: Proceedings of the 6th Workshop on Models and Algorithms for Planning and Scheduling Problems, pp. 131---132 (2003)

[9]

Grigoriev A., Sviridenko M., Uetz M.: Unrelated parallel machine scheduling with resource dependent processing times. In: Integer Programming and Combinatorial Optimization, Jünger, M., Kaibel, V. (eds.) Lecture Notes in Computer Science, 3509, pp. 182---195. Springer, Berlin Heidelberg New York (2005)

[10]

Grigoriev, A., Sviridenko, M., Uetz, M.: LP Rounding and an almost harmonic algorithm for scheduling with resource dependent processing times. In: Approximation, Randomization and Combinatorial Optimization, Diaz, J., Jansen, K., Rolim, J.D.P., Zwick, U. (eds.) Lecture Notes in Computer Science, 4110, pp. 140---151. Springer, Berlin Heidelberg New York (2006)

[11]

Grigoriev, A., Uetz, M.: Scheduling parallel jobs with linear speedup. In: Approximation and Online Algorithms. Erlebach, T., Persiano, P. (eds.) Lecture Notes in Computer Science, vol. 3879, pp. 203---215. Springer, Berlin Heidelberg New York (2006)

[12]

Hochbaum D.S. and Shmoys D.B. (1987). Using dual approximation algorithms for scheduling problems: theoretical and practical results. J. ACM 34: 144---162

Digital Library

[13]

Jansen K. (2004). Scheduling malleable parallel tasks: an asymptotic fully polynomial time approximation scheme. Algorithmica 39: 59---81

Digital Library

[14]

Jansen K. and Mastrolilli M. (2004). Approximation schemes for parallel machine scheduling problems with controllable processing times. Comput. Oper. Res. 31: 1565---1581

Digital Library

[15]

Kellerer, H.: Personal Communication (2005)

[16]

Kellerer H. and Strusevich V.A. (2003). Scheduling parallel dedicated machines under a single non-shared resource. Euro. J. Oper. Res. 147: 345---364

[17]

Kellerer H. and Strusevich V.A. (2004). Scheduling problems for parallel dedicated machines under multiple resource constraints. Discr. Appl. Math. 133: 45---68

Digital Library

[18]

Kelley, J.E., Walker, M.R.: Critical Path Planning and Scheduling: An Introduction. Mauchly Associates, Ambler (PA) (1959)

[19]

Kumar, V.S.A., Marathe, M.V., Parthasarathy, S., Srinivasan, A.: Approximation algorithms for scheduling on multiple machines. In: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, pp. 254---263 (2005)

Digital Library

[20]

Lenstra J.K., Shmoys D.B. and Tardos É. (1990). Approximation algorithms for scheduling unrelated parallel machines. Math. Progr. Ser. A 46: 259---271

Digital Library

[21]

Mounie, G., Rapine, C., Trystram, D.: Efficient approximation algorithms for scheduling malleable tasks. In: Proceedings of the 11th ACM Symposium on Parallel Algorithms and Architectures, pp. 23---32 (1999)

Digital Library

[22]

Mounie, G., Rapine, C., Trystram, D.: A 3/2-dual approximation algorithm for scheduling independent monotonic malleable tasks. Manuscript. Retrieved from http://citeseer.csail.mit.edu/558879.html

[23]

Shmoys D.B. and Tardos É. (1993). An approximation algorithm for the generalized assignment problem. Math. Progr. Ser. A 62: 461---474

Digital Library

[24]

Skutella M. (1998). Approximation algorithms for the discrete time-cost tradeoff problem. Math. Oper. Res. 23: 909---929

Digital Library

[25]

Turek, J., Wolf, J.L., Yu, P.S.: Approximate algorithms for scheduling parallelizable tasks. In: Proceedings of the 4th ACM symposium on parallel algorithms and architectures, pp. 323--332 (1992)

Digital Library

Cited By

Jansen KMaack MRau M(2019)Approximation Schemes for Machine Scheduling with Resource (In-)dependent Processing TimesACM Transactions on Algorithms10.1145/330225015:3(1-28)Online publication date: 7-May-2019
https://dl.acm.org/doi/10.1145/3302250
Villa FVallada EFanjul-Peyro L(2018)Heuristic algorithms for the unrelated parallel machine scheduling problem with one scarce additional resourceExpert Systems with Applications: An International Journal10.1016/j.eswa.2017.09.05493:C(28-38)Online publication date: 1-Mar-2018
https://dl.acm.org/doi/10.1016/j.eswa.2017.09.054
Jansen KMaack MRau M(2016)Approximation schemes for machine scheduling with resource (in-)dependent processing timesProceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms10.5555/2884435.2884539(1526-1542)Online publication date: 10-Jan-2016
https://dl.acm.org/doi/10.5555/2884435.2884539
Show More Cited By

Index Terms

Machine scheduling with resource dependent processing times

Recommendations

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 ...
Single machine scheduling with a variable common due date and resource-dependent processing times

The problem of scheduling n jobs with a variable common due date on a single machine is studied. It is assumed that the job processing times are non-increasing linear functions of an equal amount of a resource allocated to the jobs. The due date and ...
Scheduling jobs with agreeable processing times and due dates on a single batch processing machine

In this paper we study the problems of scheduling jobs with agreeable processing times and due dates on a single batch processing machine to minimize total tardiness, and weighted number of tardy jobs. We prove that the problem of minimizing total ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Mathematical Programming: Series A and B

Mathematical Programming: Series A and B Volume 110, Issue 1

June 2007

240 pages

ISSN:0025-5610

Issue’s Table of Contents

Copyright © Copyright © 2007 Springer-Verlag.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 June 2007

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Jansen KMaack MRau M(2019)Approximation Schemes for Machine Scheduling with Resource (In-)dependent Processing TimesACM Transactions on Algorithms10.1145/330225015:3(1-28)Online publication date: 7-May-2019
https://dl.acm.org/doi/10.1145/3302250
Villa FVallada EFanjul-Peyro L(2018)Heuristic algorithms for the unrelated parallel machine scheduling problem with one scarce additional resourceExpert Systems with Applications: An International Journal10.1016/j.eswa.2017.09.05493:C(28-38)Online publication date: 1-Mar-2018
https://dl.acm.org/doi/10.1016/j.eswa.2017.09.054
Jansen KMaack MRau M(2016)Approximation schemes for machine scheduling with resource (in-)dependent processing timesProceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms10.5555/2884435.2884539(1526-1542)Online publication date: 10-Jan-2016
https://dl.acm.org/doi/10.5555/2884435.2884539
Chen XYe D(2016)Approximation algorithms for scheduling on multi-core processor with shared speedup resourcesDiscrete Optimization10.1016/j.disopt.2016.02.00220:C(11-22)Online publication date: 1-May-2016
https://dl.acm.org/doi/10.1016/j.disopt.2016.02.002
Hsieh PYang SYang D(2015)Decision support for unrelated parallel machine scheduling with discrete controllable processing timesApplied Soft Computing10.1016/j.asoc.2015.01.02830:C(475-483)Online publication date: 1-May-2015
https://dl.acm.org/doi/10.1016/j.asoc.2015.01.028
Niemeier MWiese A(2015)Scheduling with an Orthogonal Resource ConstraintAlgorithmica10.1007/s00453-013-9829-571:4(837-858)Online publication date: 1-Apr-2015
https://dl.acm.org/doi/10.1007/s00453-013-9829-5
Megow NMöhring RSchulz J(2011)Decision Support and Optimization in Shutdown and Turnaround SchedulingINFORMS Journal on Computing10.5555/2398290.239829323:2(189-204)Online publication date: 1-Apr-2011
https://dl.acm.org/doi/10.5555/2398290.2398293
Chen LLuo WZhang G(2011)Approximation algorithms for unrelated machine scheduling with an energy budgetProceedings of the 5th joint international frontiers in algorithmics, and 7th international conference on Algorithmic aspects in information and management10.5555/2021911.2021940(244-254)Online publication date: 28-May-2011
https://dl.acm.org/doi/10.5555/2021911.2021940
Kumar VMarathe MParthasarathy SSrinivasan A(2009)A unified approach to scheduling on unrelated parallel machinesJournal of the ACM10.1145/1552285.155228956:5(1-31)Online publication date: 21-Aug-2009
https://dl.acm.org/doi/10.1145/1552285.1552289

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents