A simple linear time approximation algorithm for multi-processor job scheduling on four processors

DOI10.1007/s10878-006-9011-yzbMath1112.90024MaRDI QIDQ867026

Jianxin Wang, Jingui Huang, Songqiao Chen, Jian'er Chen

Publication date: 14 February 2007

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-006-9011-y

zbMATH Keywords

Approximation algorithm; NP-hard problem; Multi-processor job scheduling

Mathematics Subject Classification ID

90C60: Abstract computational complexity for mathematical programming problems

90B35: Deterministic scheduling theory in operations research

90C59: Approximation methods and heuristics in mathematical programming

68W25: Approximation algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Scheduling multiprocessor tasks on three dedicated processors
• Complexity of scheduling multiprocessor tasks with prespecified processors allocations
• Efficiency and effectiveness of normal schedules on three dedicated processors
• Current trends in deterministic scheduling
• An approximation algorithm for scheduling on three dedicated machines
• Scheduling multiprocessor tasks on a dynamic configuration of dedicated processors
• A Polynomial Time Approximation Scheme for General Multiprocessor Job Scheduling
• Scheduling Multiprocessor Tasks to Minimize Schedule Length
• Simultaneous Resource Scheduling to Minimize Weighted Flow Times
• General Multiprocessor Task Scheduling: Approximate Solutions in Linear Time
• Bounds for Certain Multiprocessing Anomalies
• Scheduling independent multiprocessor tasks