Streaming algorithms for multitasking scheduling with shared processing

DOI10.1016/j.dam.2022.06.019zbMath1495.90071arXiv2204.01970MaRDI QIDQ2166248

Bin Fu, Hairong Zhao, Yumei Huo

Publication date: 24 August 2022

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2204.01970

zbMATH Keywords

makespan; parallel machine; approximation scheme; streaming algorithm; multitasking scheduling; shared processing

Mathematics Subject Classification ID

90B35: Deterministic scheduling theory in operations research

68M20: Performance evaluation, queueing, and scheduling in the context of computer systems

Related Items

Streaming approximation scheme for minimizing total completion time on parallel machines subject to varying processing capacity

Cites Work

• Unnamed Item
• Multitasking via alternate and shared processing: algorithms and complexity
• Parallel machines scheduling with nonsimultaneous machine available time
• Decentralized subcontractor scheduling with divisible jobs
• Probabilistic counting algorithms for data base applications
• Scheduling on machines with variable service rates
• Selection and sorting with limited storage
• The space complexity of approximating the frequency moments
• Shared multi-processor scheduling
• Shared processor scheduling of multiprocessor jobs
• Sequencing independent jobs with a single resource
• Single Machine Scheduling Problem When the Machine Capacity Varies Stochastically
• Exact and Approximate Algorithms for Scheduling Nonidentical Processors
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Bounds for Certain Multiprocessing Anomalies
• Bounds on Multiprocessing Timing Anomalies
• Streaming algorithms for bin packing and vector scheduling