article

Complexity of scheduling parallel task systems

Authors:

J. Du,

J. Y.-T. LeungAuthors Info & Claims

SIAM Journal on Discrete Mathematics, Volume 2, Issue 4

Pages 473 - 487

https://doi.org/10.1137/0402042

Published: 01 November 1989 Publication History

Abstract

No abstract available.

Cited By

View all

Goponenko ALamar KAllan BBrandt JDechev D(2024)Job Scheduling for HPC Clusters: Constraint Programming vs. Backfilling ApproachesProceedings of the 18th ACM International Conference on Distributed and Event-based Systems10.1145/3629104.3666038(135-146)Online publication date: 24-Jun-2024
https://dl.acm.org/doi/10.1145/3629104.3666038
Jansen KRau MTutas MAgrawal KPetrank E(2024)Hardness and Tight Approximations of Demand Strip PackingProceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3626183.3659971(479-489)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3626183.3659971
Abdi SAshjaei MMubeen S(2024)Cost-aware workflow offloading in edge-cloud computing using a genetic algorithmThe Journal of Supercomputing10.1007/s11227-024-06341-080:17(24835-24870)Online publication date: 1-Nov-2024
https://dl.acm.org/doi/10.1007/s11227-024-06341-0
Show More Cited By

Index Terms

Complexity of scheduling parallel task systems
1. Theory of computation

Recommendations

Parameterized complexity of a coupled-task scheduling problem

In this article, we investigate the parameterized complexity of coupled-task scheduling in the presence of compatibility constraints given by a compatibility graph. In this model, each task contains two sub-tasks delayed by an idle time. Moreover, a sub-...
Complexity of preemptive minsum scheduling on unrelated parallel machines

We show that the problems of minimizing total completion time and of minimizing the number of late jobs on unrelated parallel machines, when preemption is allowed, are both NP-hard in the strong sense. The former result settles a long-standing open ...
Complexity of preemptive minsum scheduling on unrelated parallel machines

We show that the problems of minimizing total completion time and of minimizing the number of late jobs on unrelated parallel machines, when preemption is allowed, are both NP-hard in the strong sense. The former result settles a long-standing open ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 November 1989

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

82
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 02 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Goponenko ALamar KAllan BBrandt JDechev D(2024)Job Scheduling for HPC Clusters: Constraint Programming vs. Backfilling ApproachesProceedings of the 18th ACM International Conference on Distributed and Event-based Systems10.1145/3629104.3666038(135-146)Online publication date: 24-Jun-2024
https://dl.acm.org/doi/10.1145/3629104.3666038
Jansen KRau MTutas MAgrawal KPetrank E(2024)Hardness and Tight Approximations of Demand Strip PackingProceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3626183.3659971(479-489)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3626183.3659971
Abdi SAshjaei MMubeen S(2024)Cost-aware workflow offloading in edge-cloud computing using a genetic algorithmThe Journal of Supercomputing10.1007/s11227-024-06341-080:17(24835-24870)Online publication date: 1-Nov-2024
https://dl.acm.org/doi/10.1007/s11227-024-06341-0
Fotakis DMatuschke JPapadigenopoulos O(2024)A constant-factor approximation for generalized malleable scheduling under -concave processing speedsMathematical Programming: Series A and B10.1007/s10107-023-02054-z206:1-2(515-539)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1007/s10107-023-02054-z
Xing MMao HYin SPan LZhang ZXiao ZLong JSingh ASun YAkoglu LGunopulos DYan XKumar ROzcan FYe J(2023)A Dual-Agent Scheduler for Distributed Deep Learning Jobs on Public Cloud via Reinforcement LearningProceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3580305.3599241(2776-2788)Online publication date: 6-Aug-2023
https://dl.acm.org/doi/10.1145/3580305.3599241
Wu FJiang ZZhang RZhang X(2023)Approximation algorithms for scheduling monotonic moldable tasks on multiple platformsJournal of Scheduling10.1007/s10951-022-00774-226:4(383-398)Online publication date: 25-Jan-2023
https://dl.acm.org/doi/10.1007/s10951-022-00774-2
Wang BWei J(2023)Particle Swarm Optimization with Genetic Evolution for Task Offloading in Device-Edge-Cloud Collaborative ComputingAdvanced Intelligent Computing Technology and Applications10.1007/978-981-99-4761-4_29(340-350)Online publication date: 10-Aug-2023
https://dl.acm.org/doi/10.1007/978-981-99-4761-4_29
Grage KJansen KOhnesorge F(2023)Improved Algorithms for Monotone Moldable Job Scheduling Using Compression and ConvolutionEuro-Par 2023: Parallel Processing10.1007/978-3-031-39698-4_34(503-517)Online publication date: 28-Aug-2023
https://dl.acm.org/doi/10.1007/978-3-031-39698-4_34
Jansen KKahler K(2023)On the Complexity of Scheduling Problems with a Fixed Number of Parallel Identical MachinesSOFSEM 2023: Theory and Practice of Computer Science10.1007/978-3-031-23101-8_13(192-206)Online publication date: 15-Jan-2023
https://dl.acm.org/doi/10.1007/978-3-031-23101-8_13
Rajak NRajak RPrakash S(2022)A Workflow Scheduling Method for Cloud Computing PlatformWireless Personal Communications: An International Journal10.1007/s11277-022-09882-w126:4(3625-3647)Online publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1007/s11277-022-09882-w
Show More Cited By

View Options

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.

Abstract

Cited By

Index Terms

Recommendations

Parameterized complexity of a coupled-task scheduling problem

Complexity of preemptive minsum scheduling on unrelated parallel machines

Complexity of preemptive minsum scheduling on unrelated parallel machines

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Get Access

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations