Fast approximation algorithms for job scheduling with processing set restrictions

DOI10.1016/j.tcs.2010.08.008zbMath1234.68046OpenAlexW2113497279MaRDI QIDQ410716

Yumei Huo, Joseph Y.-T. Leung

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

zbMATH Keywords

polynomial-time approximation algorithmNP-hardmakespan minimizationinclusive processing setnested processing setnonpreemptive schedulingtree-hierarchical processing set

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items (14)

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 ⋮ Multiple subset sum with inclusive assignment set restrictions ⋮ Parallel batch scheduling with nested processing set restrictions ⋮ Mixed coordination mechanisms for scheduling games on hierarchical machines ⋮ Scheduling uniform machines with restricted assignment ⋮ Makespan minimization in online scheduling with machine eligibility ⋮ 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 ⋮ Makespan minimization in online scheduling with machine eligibility ⋮ Scheduling jobs with release and delivery times subject to nested eligibility constraints ⋮ Parallel machine scheduling with nested processing set restrictions and job delivery times ⋮ Greedy is optimal for online restricted assignment and smart grid scheduling for unit size jobs ⋮ Heuristics for online scheduling on identical parallel machines with two GoS levels

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

This page was built for publication: Fast approximation algorithms for job scheduling with processing set restrictions