extended-abstract

Optimally Scheduling Jobs with Multiple Tasks

Authors:

Ziv Scully,

Guy Blelloch,

Mor Harchol-Balter,

Alan Scheller-WolfAuthors Info & Claims

ACM SIGMETRICS Performance Evaluation Review, Volume 45, Issue 2

Pages 36 - 38

https://doi.org/10.1145/3152042.3152055

Published: 11 October 2017 Publication History

Get Access

Abstract

We consider optimal job scheduling where each job consists of multiple tasks, each of unknown duration, with precedence constraints between tasks. A job is not considered complete until all of its tasks are complete. Traditional heuristics, such as favoring the job of shortest expected remaining processing time, are suboptimal in this setting. Furthermore, even if we know which job to run, it is not obvious which task within that job to serve. In this paper, we characterize the optimal policy for a class of such scheduling problems and show that the policy is simple to compute.

References

[1]

S. Aalto, U. Ayesta, and R. Righter. On the Gittins index in the M/G/1 queue. Queueing Systems, 63(1):437--458, 2009.

Digital Library

Google Scholar

[2]

N. Dragoni et al. Microservices: yesterday, today, and tomorrow. 2016. arXiv:1606.04036.

Google Scholar

[3]

J. Gittins, K. Glazebrook, and R. Weber. Multi-armed bandit allocation indices. John Wiley & Sons, 2011.

Crossref

Google Scholar

[4]

J. C. Gittins and D. M. Jones. A dynamic allocation index for the sequential design of experiments. In J. Gani, editor, Progress in Statistics, pages 241--266. North-Holland, Amsterdam, NL, 1974.

Google Scholar

[5]

A. Toumi et al. Design and optimization of a large scale biopharmaceutical facility using process simulation and scheduling tools. Pharmaceutical Engineering, 30(2):1--9, 2010.

Google Scholar

[6]

J. D. Ullman. NP-complete scheduling problems. Journal of Computer and System Sciences, 10(3):384--393, 1975.

Digital Library

Google Scholar

[7]

P. Whittle. Multi-armed bandits and the Gittins index. Journal of the Royal Statistical Society. Series B (Methodological), pages 143--149, 1980.

Crossref

Google Scholar

[8]

M. Zaharia et al. Resilient distributed datasets: A faulttolerant abstraction for in-memory cluster computing. In NSDI '12. USENIX Association, 2012.

Digital Library

Google Scholar

Cited By

View all

Chen XTian YWallach HLarochelle HBeygelzimer Ad'Alché-Buc FFox E(2019)Learning to perform local rewriting for combinatorial optimizationProceedings of the 33rd International Conference on Neural Information Processing Systems10.5555/3454287.3454851(6281-6292)Online publication date: 8-Dec-2019
https://dl.acm.org/doi/10.5555/3454287.3454851
Alnooh AAbdullah D(2018)Investigation and Analysis of Google Cluster Usage Traces: Facts and Real-Time Issues2018 International Conference on Engineering Technology and their Applications (IICETA)10.1109/IICETA.2018.8458082(60-65)Online publication date: May-2018
https://doi.org/10.1109/IICETA.2018.8458082
Berg BDorsman JHarchol-Balter M(2017)Towards Optimality in Parallel SchedulingProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/31544991:2(1-30)Online publication date: 19-Dec-2017
https://dl.acm.org/doi/10.1145/3154499

Index Terms

Optimally Scheduling Jobs with Multiple Tasks
1. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
      1. Scheduling algorithms
    2. Online algorithms
      1. Online learning algorithms
        Scheduling algorithms
  2. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning
        Sequential decision making

Recommendations

On Scheduling Unit-Length Jobs with Multiple Release Time/Deadline Intervals

We consider the problem of scheduling n unit-time jobs with multiple release time/deadline intervals, which are intervals of time in which the job can be scheduled. A feasible schedule is one in which each job is run in its entirety within one of its ...
Scheduling jobs under decreasing linear deterioration

This paper considers the scheduling problems under decreasing linear deterioration. Deterioration of a job means that its processing time is a function of its execution start time. Optimal algorithms are presented respectively for single machine ...
Scheduling of deteriorating jobs with release dates to minimize the maximum lateness

In this paper, we consider the problem of scheduling n deteriorating jobs with release dates on a single (batching) machine. Each job's processing time is a simple linear function of its starting time. The objective is to minimize the maximum lateness. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGMETRICS Performance Evaluation Review

ACM SIGMETRICS Performance Evaluation Review Volume 45, Issue 2

Setember 2017

131 pages

ISSN:0163-5999

DOI:10.1145/3152042

Editor:
Nidhi Hegde
Bell Labs, Nokia, Nozay, France

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 October 2017

Published in SIGMETRICS Volume 45, Issue 2

Check for updates

Qualifiers

Extended-abstract

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
126
Total Downloads

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

Reflects downloads up to 01 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Chen XTian YWallach HLarochelle HBeygelzimer Ad'Alché-Buc FFox E(2019)Learning to perform local rewriting for combinatorial optimizationProceedings of the 33rd International Conference on Neural Information Processing Systems10.5555/3454287.3454851(6281-6292)Online publication date: 8-Dec-2019
https://dl.acm.org/doi/10.5555/3454287.3454851
Alnooh AAbdullah D(2018)Investigation and Analysis of Google Cluster Usage Traces: Facts and Real-Time Issues2018 International Conference on Engineering Technology and their Applications (IICETA)10.1109/IICETA.2018.8458082(60-65)Online publication date: May-2018
https://doi.org/10.1109/IICETA.2018.8458082
Berg BDorsman JHarchol-Balter M(2017)Towards Optimality in Parallel SchedulingProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/31544991:2(1-30)Online publication date: 19-Dec-2017
https://dl.acm.org/doi/10.1145/3154499

View Options

Get Access

Login options

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

Cited By

Index Terms

Recommendations

On Scheduling Unit-Length Jobs with Multiple Release Time/Deadline Intervals

Scheduling jobs under decreasing linear deterioration

Scheduling of deteriorating jobs with release dates to minimize the maximum lateness