article

On an on-line scheduling problem for parallel jobs

Authors:

Edwin Naroska,

Uwe SchwiegelshohnAuthors Info & Claims

Information Processing Letters, Volume 81, Issue 6

Pages 297 - 304

https://doi.org/10.1016/S0020-0190(01)00241-1

Published: 01 March 2002 Publication History

Abstract

No abstract available.

Cited By

View all

Kononov AZakharova Y(2022)Speed scaling scheduling of multiprocessor jobs with energy constraint and makespan criterionJournal of Global Optimization10.1007/s10898-021-01115-x83:3(539-564)Online publication date: 1-Jul-2022
https://dl.acm.org/doi/10.1007/s10898-021-01115-x
Kononov AKovalenko Y(2020)Approximation algorithms for energy-efficient scheduling of parallel jobsJournal of Scheduling10.1007/s10951-020-00653-823:6(693-709)Online publication date: 1-Dec-2020
https://dl.acm.org/doi/10.1007/s10951-020-00653-8
Kell NHavill J(2015)Improved upper bounds for online malleable job schedulingJournal of Scheduling10.1007/s10951-014-0406-918:4(393-410)Online publication date: 1-Aug-2015
https://dl.acm.org/doi/10.1007/s10951-014-0406-9
Show More Cited By

Index Terms

On an on-line scheduling problem for parallel jobs
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

A simpler competitive analysis for scheduling equal-length jobs on one machine with restarts

We consider the online problem of scheduling jobs with equal processing times on a single machine. Each job has a release time and a deadline, and the goal is to maximize the number of jobs completed by their deadlines. Chrobak et al. (2007, SICOMP 36:6) ...
Single machine parallel-batch scheduling with deteriorating jobs

We consider several single machine parallel-batch scheduling problems in which the processing time of a job is a linear function of its starting time. We give a polynomial-time algorithm for minimizing the maximum cost, an O(n⁵) time algorithm for ...
Online scheduling of weighted equal-length jobs with hard deadlines on parallel machines

We consider the problem of scheduling a maximum profit selection of equal length jobs on m identical machines. Jobs arrive online over time and the goal is to determine a non-preemptive schedule which maximizes the total profit of the scheduled jobs. Let ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Information Processing Letters Volume 81, Issue 6

March 31, 2002

52 pages

ISSN:0020-0190

Issue’s Table of Contents

Publisher

Elsevier North-Holland, Inc.

United States

Publication History

Published: 01 March 2002

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 20 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Kononov AZakharova Y(2022)Speed scaling scheduling of multiprocessor jobs with energy constraint and makespan criterionJournal of Global Optimization10.1007/s10898-021-01115-x83:3(539-564)Online publication date: 1-Jul-2022
https://dl.acm.org/doi/10.1007/s10898-021-01115-x
Kononov AKovalenko Y(2020)Approximation algorithms for energy-efficient scheduling of parallel jobsJournal of Scheduling10.1007/s10951-020-00653-823:6(693-709)Online publication date: 1-Dec-2020
https://dl.acm.org/doi/10.1007/s10951-020-00653-8
Kell NHavill J(2015)Improved upper bounds for online malleable job schedulingJournal of Scheduling10.1007/s10951-014-0406-918:4(393-410)Online publication date: 1-Aug-2015
https://dl.acm.org/doi/10.1007/s10951-014-0406-9
Wu JChang HHo YLiu P(2012)Scheduling of variable-time jobs for distributed systems with heterogeneous processor cardinalityInternational Journal of Ad Hoc and Ubiquitous Computing10.1504/IJAHUC.2012.04826210:2(112-121)Online publication date: 1-Jul-2012
https://dl.acm.org/doi/10.1504/IJAHUC.2012.048262
Jansen KBlelloch GHerlihy M(2012)A(3/2+ε) approximation algorithm for scheduling moldable and non-moldable parallel tasksProceedings of the twenty-fourth annual ACM symposium on Parallelism in algorithms and architectures10.1145/2312005.2312048(224-235)Online publication date: 25-Jun-2012
https://dl.acm.org/doi/10.1145/2312005.2312048
Ramírez-Alcaraz JTchernykh AYahyapour RSchwiegelshohn UQuezada-Pina AGonzález-García JHirales-Carbajal A(2011)Job Allocation Strategies with User Run Time Estimates for Online Scheduling in Hierarchical GridsJournal of Grid Computing10.1007/s10723-011-9179-y9:1(95-116)Online publication date: 1-Mar-2011
https://dl.acm.org/doi/10.1007/s10723-011-9179-y
Tchernykh ASchwiegelshohn UYahyapour RKuzjurin N(2010)On-line hierarchical job scheduling on grids with admissible allocationJournal of Scheduling10.1007/s10951-010-0169-x13:5(545-552)Online publication date: 1-Oct-2010
https://dl.acm.org/doi/10.1007/s10951-010-0169-x
Chan WChin FYe DZhang GZhang Y(2008)On-line scheduling of parallel jobs on two machinesJournal of Discrete Algorithms10.5555/1346365.13466776:1(3-10)Online publication date: 1-Mar-2008
https://dl.acm.org/doi/10.5555/1346365.1346677
Ye DZhang G(2007)On-line scheduling of parallel jobs in a listJournal of Scheduling10.1007/s10951-007-0032-x10:6(407-413)Online publication date: 1-Dec-2007
https://dl.acm.org/doi/10.1007/s10951-007-0032-x
Epstein LStee R(2006)Online scheduling of splittable tasksACM Transactions on Algorithms10.1145/1125994.11259992:1(79-94)Online publication date: 1-Jan-2006
https://dl.acm.org/doi/10.1145/1125994.1125999
Show More Cited By

Abstract

Cited By

Index Terms

Recommendations

A simpler competitive analysis for scheduling equal-length jobs on one machine with restarts

Single machine parallel-batch scheduling with deteriorating jobs

Online scheduling of weighted equal-length jobs with hard deadlines on parallel machines

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations