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, Greedy is optimal for online restricted assignment and smart grid scheduling for unit size jobs, Parallel batch scheduling with inclusive processing set restrictions and non-identical capacities to minimize makespan, Fast approximation algorithms for uniform machine scheduling with processing set restrictions, Parallel machine scheduling with nested processing set restrictions and job delivery times, Scheduling jobs with release and delivery times subject to nested eligibility constraints, Heuristics for online scheduling on identical parallel machines with two GoS levels, Parallel batch scheduling with nested processing set restrictions, Effective heuristics for makespan minimization in parallel batch machines with non-identical capacities and job release times, On some special cases of the restricted assignment problem, Scheduling uniform machines with restricted assignment
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