Decentralized Online Scheduling of Malleable NP-hard Jobs

DOI10.1007/978-3-031-12597-3_8MaRDI QIDQ6487361zbMATH OpenFDO

Authors Peter Sanders, Dominik Schreiber

Publication date 9 December 2022

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/978-3-031-12597-3_8

Mathematics Subject Classification ID

Distributed systems (68M14) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distributed algorithms (68W15) Online algorithms; streaming algorithms (68W27)

Recommendations

• Online scheduling of malleable parallel jobs
• Online malleable job scheduling for m 3
• Decentralization and Mechanism Design for Online Machine Scheduling
• Competitive online scheduling of perfectly malleable jobs with setup times
• Improved upper bounds for online malleable job scheduling
• Online scheduling of moldable parallel tasks
• Online scheduling of malleable parallel jobs with setup times on two identical machines
• Mechanism design for decentralized online machine scheduling
• Improved algorithms for online scheduling of malleable parallel jobs on two identical machines
• Online Scheduling with Hard Deadlines on Parallel Machines

Cites work

• A high-performance, portable implementation of the MPI message passing interface standard
• Distributed cube and conquer with Paracooba
• Languages and Compilers for Parallel Computing
• Lilotane: a lifted SAT-based approach to hierarchical planning
• Logical cryptanalysis as a SAT problem: Encoding and analysis of the U. S. Data Encryption Standard
• ManySAT: a parallel SAT solver
• Robust massively parallel sorting
• SAT competition 2020
• Scalable SAT solving in the cloud
• Sequential and parallel algorithms and data structures. The basic toolbox
• Sorting in \(c \log n\) parallel steps
• The complexity of theorem-proving procedures

Cited in

(7)

• Online over time processing of combinatorial problems
• Decentralized online integer programming problems with a coupling cardinality constraint
• Decentralized job scheduling in the cloud based on a spatially generalized \textit{Prisoner's Dilemma} game
• Unsatisfiability proofs for distributed clause-sharing SAT solvers
• Trusted scalable SAT solving with on-the-fly LRAT checking
• Producing proofs of unsatisfiability with distributed clause-sharing SAT solvers
• Decentralized subcontractor scheduling with divisible jobs

This page was built for publication: Decentralized Online Scheduling of Malleable NP-hard Jobs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6487361)