Fast approximation algorithms for job scheduling with processing set restrictions
From MaRDI portal
Publication:410716
DOI10.1016/j.tcs.2010.08.008zbMath1234.68046MaRDI QIDQ410716
Publication date: 3 April 2012
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2010.08.008
polynomial-time approximation algorithm; NP-hard; makespan minimization; inclusive processing set; nested processing set; nonpreemptive scheduling; tree-hierarchical processing set
90B35: Deterministic scheduling theory in operations research
68M20: Performance evaluation, queueing, and scheduling in the context of computer systems
Related Items
Multiple subset sum with inclusive assignment set restrictions, Makespan minimization in online scheduling with machine eligibility, Makespan minimization in online scheduling with machine eligibility, On some special cases of the restricted assignment problem
Cites Work
- Unnamed Item
- Unnamed Item
- Approximation algorithms for scheduling unrelated parallel machines
- Scheduling parallel machines with inclusive processing set restrictions and job release times
- Parallel machine scheduling under a grade of service provision
- Parallel machine scheduling with nested job assignment restrictions
- An optimal rounding gives a better approximation for scheduling unrelated machines
- Scheduling unit length jobs with parallel nested machine processing set restrictions
- Parallel machine scheduling with nested processing set restrictions
- On-Line Load Balancing in a Hierarchical Server Topology
- Scheduling parallel machines with inclusive processing set restrictions
- Task Scheduling on a Multiprocessor System with Independent Memories
- Parallel machine scheduling with job assignment restrictions