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

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

Jianxin Wang, Songqiao Chen, Jingui Huang, 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 algorithmNP-hard problemMulti-processor job scheduling

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59) Approximation algorithms (68W25)

Related Items (1)

The consecutive multiprocessor job scheduling problem

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

This page was built for publication: A simple linear time approximation algorithm for multi-processor job scheduling on four processors